 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