Question 5: Show that the following problems are NPC. Assume that The Hamilto- nian path question, The clique of size k question, and the 3 coloring problem are in N P C . 1. Can a graph be colored by 4 colors? Hint add a new vertex that is connected to all of V . 2. Given an undirected graph G , does it has a path of length k or more so that all the vertices are different? 3. Given a graph G ( V, E ), a number k and a number t . Is there a subset U of V of size | U | = k so that the number of edges with both endpoints in U is at least t ? ( k can depend on n ) Hint: Choose b wisely. 4. The k -coloring problem. Given a graph and an input k