= Solution
The <three-colourability problem> belongs to <NP>: a colour assignment is a polynomial-length <complexity certificate>, and all edges can be checked in $O(|V|+|E|)$ time.
For <NP-hardness>, reduce <3-SAT> to the <three-colourability problem>. Start with a palette <graph triangle> with vertices $T,F,B$. Its colours are necessarily distinct, and name them by these vertices. For each <Boolean variable> $u$, add vertices $u,\bar u$, join them to each other, and join each to $B$. The <graph triangle> $B,u,\bar u$ is the forcing component of the <Boolean-pair colouring gadget>, so the two literal vertices receive opposite colours $T,F$.
For each <Boolean clause>, attach a fresh copy of the <three-colour clause gadget>, identify its $t$ with the palette vertex $T$, and identify its three input vertices with the <Boolean clause>'s <Boolean literal> vertices. Copies share only palette or literal vertices. A <Boolean clause> with one or two <Boolean literals> is padded to three by repeating a literal; an empty <Boolean clause> can be mapped immediately to the uncolourable graph $K_4$.
Any <graph colouring> with three colours gives a truth assignment by reading colour $T$ as true. The <three-colour clause gadget> forbids three false inputs, so every <Boolean clause> is satisfied. Conversely, any satisfying truth assignment colours the literal pairs, and the extension property proved above independently colours the fresh auxiliary vertices of each clause. Thus the entire graph is three-colourable exactly when the formula is satisfiable.
There are $3+2n+5m$ vertices for $n$ variables and $m$ nonempty padded clauses, and $O(n+m)$ edges. The construction is a <polynomial-time many-one reduction>. Using the permitted <NP-completeness> of <3-SAT>, we obtain
$$
\boxed{\text{three-colourability is NP-complete}.}
$$
Back to article page
