3-COLOR Decision Problem The 3-COLOR problem takes as input a graph and decides whether it can be colored using only 3 colors so that no 2 adjacent nodes have the same color.
The reduction from 3-SAT to 3-COLOR uses the following gadget (see below) to represent a clause in the 3-SAT formula.
It is clear that a valid 3-coloring exists only when at least one of x, y, or z has the same color as T. Now, suppose all 3 literals are False. Then, if the x, y and z nodes are colored the same as the F node, there is no valid 3-coloring.
However, to the 3-color algorithm, the gadget is just a subgraph. Even if x, y and z are False, if we color them the same as the T node, there would be a valid coloring. It's not clear to me that you can specify in the input to the 3-color algorithm that if a literal is False/True, it should have the same color as F/T.
So, how is the reduction valid?


Actually, there is no 3-coloring if the 3 literals are colored as F.
This is because the node after the "merge" will be colored as F, while the blank below left of T will be as X. The remaining node (upper left of T) can have no valid color in this case.
