A small 3SAT instance and its three-colourability gadget graph

Under the given assignment, both NAE clauses are satisfied: $(x,y,s)=(1,0,0)$ is not all equal, and $(\mathrm{\neg }s,z,w)=(1,0,0)$ is not all equal.

Define the graph directly: take a distinguished vertex $\nu$; for each variable $u\in \{x,y,z,w,s\}$ add the triangle $(u,\mathrm{\neg }u,\nu )$; for each of the two ordered NAE clauses add a triangle of three position vertices and join its $r$th vertex to the literal vertex in position $r$. Colour $\nu$ by $2$. In the variable triangles, colour each literal vertex by its Boolean value, so $x,\mathrm{\neg }x$ receive $1,0$, $y,\mathrm{\neg }y$ receive $0,1$, $z,\mathrm{\neg }z$ receive $0,1$, $w,\mathrm{\neg }w$ receive $0,1$, and $s,\mathrm{\neg }s$ receive $0,1$.

For the clause triangle for $N_1$, the literals $x$ and $y$ have different truth values, so colour their two position vertices by the opposite colours $0$ and $1$, and colour the remaining position vertex by $2$. Do the same for $N_2$. Every clause triangle then uses $0,1,2$, and each clause vertex differs from the colour of its adjacent literal vertex. Thus the explicitly defined graph is properly three-coloured.

This worked instance shows concretely how the theorem's NAE assignment is converted into a proper three-colouring.