. 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? 2. Given an undirected graph G, does it has a path of length k or more so that all 3. Given a graph G(V, E), a number k and a number t. Is there a subset U of V of Hint add a new vertex that is connected to all of V the vertices are different? 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