The GraphThreeColoring problem is basically this:
**0**, **1** and *****. Here's a graph to color:
**0**, **1** and ***** in that order, like this:
***** because they are joined to the vertex labelled *****. This trick means that we can draw graphs to be three colored and put in them vertices that are already forced. The simple way of drawing that second graph would then be this:
**Not** gate.
TheInterestedReader may choose to confirm that the following graph is a logical **And** function.
**0** and **1** gives us a logical **Or** function.
We can now create any logical function we choose by stringing together these graphs, having the output vertex of one be the same vertex as the input vertex of one or more others. We can even create a graph that will multiply two binary numbers together, or one that acts as a TuringMachine. To do that we create a graph that can represent the current state, duplicate it as many times as we require steps for the computation, and then connect each graph to the next with the logic that converts this state into the next state.
So, how do we prove that GraphThreeColoring is NpComplete?
Take any NP problem. We want to show that under the assumption that we can three-color any graph in unit time, we can solve the given NP problem in polynomial time.
It's more-or-less true that, because the problem is NP, there is a polynomial-time process that takes the problem and a purported solution, and checks whether it really is a solution. It's also more-or-less true that this checking process can be encoded in a TuringMachine.
Build the graph that corresponds to this specific TuringMachine. When you force the colorings on the input nodes and then color the graph, the output node will be colored **1** for **Yes, this is a solution** or **0** for **No, this is not a solution**.
Leave the input nodes corresponding to the purported solution unforced, force the output to be **1**, and now make use of our assumption and color it. This, under our assumption, takes unit time, and will give us a coloring of the input nodes from which we can read out our solution. Thus we have solved the original problem.
Is it in polynomial time? Only if the graph is polynomial in the size of the problem, which requires checking but is in fact true.
So that's an outline of a proof. Convinced? Maybe not. There are a lot of details to check, and actually understanding the processes involved is tricky, but it's pretty much all there.

Comments welcome.*It seems to me that you reduce CircuitSatisfiability? to GraphThreeColoring. I would first show the NpCompleteness of the first, and then explicitly give the reduction.*
The purpose of this page is to show NpCompleteness of a problem - that's the hard bit. Showing equivalence is then fairly easy. Your suggested path is certainly one way to show NpCompleteness of Three Coloring, but the method given here is direct and complete, and therefore perhaps more enlightening.
*Also, the ***and** gate and the **not** gate are sufficient to get any circuit, so it's unnecessary to implement the **or** gate (directly).
True, and most people here will know that. The FullAdder graph can be synthesized from these gates too, but there is a much smaller graph that accomplished the same end. These were examples to show the principles, and as such the comment about the **Or** gate has its place.
And ThankYou for the comments - they are helpful.

MarkJasonDominus demonstrated a polynomial-time reduction from GraphThreeColoring to PerlLanguage RegularExpression matching (using BackReferences?): -- GregBacon

- Here's a graph. Using only three colors, can you color the vertices such that adjacent vertices have different colors?

Comments welcome.

MarkJasonDominus demonstrated a polynomial-time reduction from GraphThreeColoring to PerlLanguage RegularExpression matching (using BackReferences?): -- GregBacon

EditText of this page (last edited September 4, 2009) or FindPage with title or text search