The 3-colorability problem asks, for any given undirected graph G = (V, E), whether there is a way to color each vertex in V with one of the 3 given colors such that no two adjacent vertices have the...

The 3-colorability problem asks, for any given undirected graph G = (V, E), whether there is a way to color each vertex in V with one of the 3 given colors such that no two adjacent vertices have the same color. Show that the 3-colorability is in NP.