# Reduction of 3-SAT to 3-COLOR

The decision version of the 3-COLOR problem is the problem of deciding whether an input graph G(V, E) can be colored using only 3 colors so that no 2 adjacent vertices have the same color.

I had interpreted that to mean that we were looking for any coloring.

However, most proofs I have seen that reduce 3-SAT to 3-COLOR to prove that 3-SAT is NP-Complete use subgraph "gadgets" where some of the nodes are already colored.
But in this case, it would only show that a specific 3-coloring (i.e. some nodes on the input graph are pre-colored) does not exist.

It doesn't show that no 3-coloring exists. Can someone clarify why the reduction is valid?

An important part of these gadget schemes is that there is a 3-clique somewhere called the palette that arbitrates the logic roles of colors. In other words, there are 3 nodes all connected to each other, labeled $v_T$, $v_F$, and $v_R$. The palette can be arbitrarily colored, and whatever colors are chosen represent the 3 logic values. Then when a gadget has a fixed "true" node in it, arcs are extended from fixed $v_F$ and $v_R$ nodes to it, to compel its color to be the same as $v_T$.
• No, no colors are fixed. "$v_T$" is just a label on a node. Arcs are added so that other nodes are forced to be the same color as it, and can also be labeled "$v_T$". It is easy to prove then that all $v_T$ nodes must be the same color, not that they must be a particular color. – NovaDenizen Nov 21 '14 at 16:55