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 NPC 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 k so that the number of edges with both endpoints in U is at least t? size U ( k can depend on n ) Hint: Choose b wisely. 4. The k-coloring problem. Given a graph and an input k