Graph 3 Colouring Is NP Complete

	AllPages RecentChanges Links to this page Edit this page Search Entry portal
Advice For New Users

The proof that G3C is NP-Complete can be done directly, and not via reductions. In effect the outline is this.

By definition, it has a Turing Machine (TM) to check that a purported answer to an instance is correct.

A Turing machine can be constructed as a combinatorial network whose size is bounded by a quadratic in how long it takes the machine to run.

Since the problem is in NP, checking is done in polynomial time, so the network is polynomial in the size of the instance.

You can see some of the details of the technique in the description of Factoring via Graph Three Colouring.

We can construct graphs such that colouring the graphs emulates an AND gate, OR gate, or NOT gate.

Therefore any combinatorial network can be emulated by colouring a suitable graph.

So the TM to check an alleged answer/solution can be built as a combinatorial network

But that's all just checking an alleged solution and producing a Yes/No as to whether the solution is correct.

By so doing, any legal colouring of the graph corresponds to a calculation that gives the answer yes.

If we succeed in colouring the graph, the "input vertices" must now have a solution.

Thus

So if we can 3-colour graphs, we can solve any NP problem.