= Solution
A <decision problem> is in <NP> if every yes-instance has a <complexity certificate> of length bounded by a polynomial in the input length, and a deterministic verifier can check that certificate in <polynomial time>. More precisely, for some polynomial $p$ and verifier $V$,
$$
w\in L\quad\Longleftrightarrow\quad\exists z,\ |z|\leq p(|w|),\quad V(w,z)=1,
$$
where $V$ runs in <polynomial time>. Equivalently, a nondeterministic machine decides the problem in <polynomial time>. A problem is <NP-complete> if it belongs to <NP> and is <NP-hard>: every problem in <NP> has a <polynomial-time many-one reduction> to it. Such a reduction maps instances $w$ to instances $r(w)$ with $w\in L$ if and only if $r(w)$ is a yes-instance of the target problem.
For <3-SAT>, the <complexity certificate> is one truth value for each <Boolean variable>. Check every <Boolean literal>, negate its variable's truth value when appropriate, evaluate the disjunction in each <Boolean clause>, and check their conjunction. This takes time linear in the encoded <Boolean formula>, apart from equally polynomial bookkeeping for variable names. A satisfying assignment passes; an unsatisfiable <Boolean formula> has no passing assignment. Thus \b[<3-SAT> belongs to <NP>].
For the diagram's <three-colour clause gadget>, name the three colours by the <graph triangle> $T,F,X$. Each input $a,b,\bar c$ is adjacent to $X$, so each has colour $T$ or $F$. Suppose that none has colour $T$. Then all three have colour $F$. Because $x_1$ is adjacent to $a$ and $x_2$ to $b$, neither has colour $F$. The <edge> $x_1x_2$ forces these two colours to be $T$ and $X$ in some order. The <graph triangle> $x_1,x_2,x_3$ now forces $x_3$ to have colour $F$. Since $x_4$ is adjacent to $x_3$ and $T$, it must have colour $X$. The <graph triangle> $x_4,x_5,T$ forces $x_5$ to have colour $F$. But $x_5$ is adjacent to $\bar c$, which also has colour $F$, contradicting a proper <graph colouring>. Therefore \b[at least one input has colour $T$].
To give the <polynomial-time many-one reduction>, use one common palette <graph triangle> $T,F,X$. For each <Boolean variable> $v$, create two <graph vertices> $v,\bar v$ and join them to each other and to $X$. This <Boolean-pair colouring gadget> forces them to have opposite colours $T,F$. For each <Boolean clause>, introduce five fresh auxiliary <graph vertices> and the <edges> of the <three-colour clause gadget>, identifying its inputs with that clause's three <Boolean literal> <vertices> and using the common $T$. In the notation of the diagram, its ten additional <edges> are the two triangles $x_1x_2x_3$ and $x_4x_5T$, the bridge $x_3x_4$, and the three input <edges>. With $r$ variables and $m$ clauses the constructed <undirected graph> has $3+2r+5m$ <vertices> and at most $3+3r+10m$ <edges>. Repeated literals do not affect the argument. Its construction takes <polynomial time>.
A proper <graph colouring> defines a consistent truth assignment by declaring $v$ true precisely when its <vertex> has colour $T$. The only-if result just proved makes every clause true. Conversely, a satisfying assignment colours every literal <vertex> consistently, and the supplied if-direction extends each satisfied clause's colours to its fresh auxiliary <vertices>. These extensions do not conflict, since different clauses share only already-coloured palette and literal <vertices>. Thus the <Boolean formula> is satisfiable exactly when the constructed <undirected graph> is three-colourable. Since <3-SAT> is <NP-complete>, composition of reductions proves <NP-hardness> of the <three-colourability problem>.
Finally, a list of three colour labels, one for each <graph vertex>, is a <complexity certificate> for the <three-colourability problem>. Checking all <edges> takes $O(|V|+|E|)$ time. Hence this problem is in <NP> as well, and \b[the <three-colourability problem> is <NP-complete>].
Back to article page
