Question

Prove that 3-Coloring is NP Hard (starting with SAT as known NP hard problem)

Answer 1

Step 1: Prove 3-Coloring is in NP
We need to check whether each edge in graph G(V,E) connects two vertexes with two different colors. If we represent the graph using Adjacency Matrix A[1..n, 1..n] where A[i,j]=1 if (i,j) is an edge. Then we can check all of the edges in  O(n), which is absolutely a polynomial time complexity. Thus, 3-Coloring is in NP.

Step 2: Reduce  SAT as known NP hard problem to 3-Coloring

 I. Since there are 3 colors, saying a, b and c. There are only 3 situations for each edge to have different colors, the two vertexes an edge can be (a,b)(a,c)(b,c).

    II. If we can prove there exists assignments of two vertexes x i,y i for edge i (i:1..n)which make the boolean formula true (x 1 or y 1) and (x 2 or y 2) and...(x n or y n) be true.   (  according to (2) I,    we can know that (a or b) , (a or c), (b or c)  are the only three true situations )

    By now, we reduce 3-Coloring to SAT problem, which is a known NP hard problem. So we can get the conclusion that 3-Coloring is NP-Hard.

Answer 2

P.S. Click the link to see the whole picture