Motivation
A graph-coloring reduction must translate logical constraints into local edge constraints. Merely saying that a gadget “represents a clause” leaves the important question unanswered: which color assignments to its terminals can actually be extended to a proper coloring?
We build a small clause gadget and check all of its terminal cases. Combined with a triangle that names the three colors and a pair of vertices for each variable, it gives a complete polynomial reduction from 3-SAT to graph three-colorability.
Definitions
Definition 4.3.1
(Proper three-coloring)
A proper three-coloring assigns one of three colors to each vertex of an undirected graph so that adjacent vertices have different colors. The decision problem asks whether such a coloring exists.
Start from a 3-CNF formula with three literal occurrences per clause. Repeated literals are allowed, so clauses of one or two literals can be padded by repeating an existing literal without changing their truth value. An empty clause is an immediate unsatisfiable case and can be mapped to a fixed non-three-colorable graph. The NP-completeness of 3-SAT is an imported starting theorem.
Definition 4.3.2
(Palette triangle and variable pairs)
Create a triangle of palette vertices named . In any proper three-coloring these vertices receive three different colors. We use the names also for their colors; renaming the three physical colors does not affect colorability. For each variable , create vertices and , join them to each other and join both to . They must receive and in some order, encoding a truth value and its opposite.
Definition 4.3.3
(Clause gadget)
For a clause with literal vertices , add four fresh internal vertices and the nine edges
Each clause receives its own internal vertices. The three terminal names can refer to repeated or complementary literal vertices; the proof only uses the colors they actually receive.
Theorems
Theorem 4.3.4
(Clause-gadget property)
With each colored or , the four internal vertices can be properly colored if and only if at least one of has color .
Theorem 4.3.5
(Three-colorability is NP-complete)
The construction maps the formula to a graph that is three-colorable exactly when the formula is satisfiable. Consequently graph three-colorability is NP-complete.
Proof: the false clause cannot be colored
Proof
(The all-false pattern forces a contradiction)
Suppose . Since is adjacent to and , it must have color . Similarly . Vertex is adjacent to and , so . Vertex is adjacent to , and , and therefore has no available color. The gadget cannot be properly colored.
The three palette colors are distinct because of the triangle. The argument does not depend on their external names: after any proper coloring, call the color of the palette vertex the false color, and similarly for and .
Concept lensStructural
Coloring as a homomorphism to a triangle
A proper three-coloring of a graph is the same thing as an adjacency-preserving map from its vertices to the three vertices of a triangle: adjacent vertices must go to different, hence adjacent, triangle vertices. Seen this way, the palette triangle in the construction is a copy of the target, and joining a vertex to one palette vertex forbids that image, while joining it to two of them pins its image to the third. The clause gadget then imposes a relation on the images of its three terminals, and the theorem says that relation is "at least one is ".
Proof: every other terminal assignment extends
Proof
(Explicit extensions for the seven other patterns)
The following table gives one proper internal coloring for each assignment with at least one true terminal. Columns list colors of in that order.
| F | F | T | G | G | T | F |
| F | T | F | G | F | G | T |
| F | T | T | G | F | T | F |
| T | F | F | F | G | T | G |
| T | F | T | F | G | T | G |
| T | T | F | F | F | T | G |
| T | T | T | F | F | T | G |
Each row can be checked against the nine edges: and differ from ; differs from ; differ from respectively; and the three internal edges have differently colored endpoints. Together with the false-clause argument, the table proves the gadget property.
Proof X-ray
Where each gadget edge is used
In the all-false pattern the edges act as a forced chain. The edges and leave only the color when ; likewise and give . Then and force , and finally meets all three colors at once through , and . Each of the nine edges has a job: tie the gadget to the palette, attach the terminals, and link the internal vertices.
The non-obvious fact is that a single true terminal breaks the chain at exactly the vertex it touches: a true lets take , a true lets take , and a true lets take . The table checks that each such break leaves a consistent coloring. Without the table the argument would show only that the false clause is rejected, not that satisfied clauses are accepted.
Proof: formula and graph equivalence
Proof
(Satisfiability and three-colorability coincide)
Given a satisfying assignment, color the palette triangle with three distinct colors. For each variable, color its positive literal vertex or according to the assignment and its negative literal vertex with the opposite color. The variable edges are proper. Every clause has at least one true terminal, so choose the corresponding row of the table to color its four fresh internal vertices. Since different clause gadgets share only literal and palette vertices, these choices do not conflict. The whole graph is properly three-colored.
Conversely, suppose the graph has a proper three-coloring. The palette triangle uses three different colors. Each variable pair is adjacent to and to each other, so one literal vertex has color and the other . Set the variable true exactly when its positive vertex is colored . Every clause gadget has a proper internal coloring, so by the gadget property its terminals cannot all be . At least one literal in each clause is true under the resulting assignment. Thus the formula is satisfiable.
For variables and clauses, the graph has vertices and at most edges before any duplicate-edge removal. It is constructed in polynomial time from the explicit formula. A proposed three-coloring can be verified by checking the color of each vertex and comparing endpoints of every edge, so three-colorability belongs to NP. The reduction from 3-SAT proves NP-hardness, completing the NP-completeness argument.
Worked examples
Worked example 4.3.6
(One true terminal)
For terminal colors , the table assigns . In particular differs from , and , so all three of its incident constraints are satisfied.
Worked example 4.3.7
(All terminals false)
For , the forced colors are and . Vertex is adjacent to vertices of all three palette colors and cannot be colored. This is the exact logical situation the gadget must reject.
Worked example 4.3.8
(A repeated literal)
A unit clause can be written as . If , its three terminals are all false and the gadget is impossible. If , the row gives a proper extension. Reusing the same literal vertex for the three terminal roles does not change the argument.
Worked example 4.3.9
(A variable and its negation)
The literal vertices and are both adjacent to , so neither can use color . Their mutual edge forces one to use and the other . This is the graph constraint that makes the extracted truth assignment consistent.
Common mistakes
Counterexample mode
A gadget missing the edge CD accepts a false clause
Claim: the edge is redundant, so the gadget may be built with eight edges. Test the pattern . The forced colors are still (from ) and (from and ). Vertex is adjacent to and , so is allowed once is removed, even though as well. Every remaining edge is then proper, so a clause with three false terminals would be colorable. The graph built for the unsatisfiable formula would then be three-colorable, since the clause whose terminals are all the false literal vertex would no longer be rejected. The edge is what makes the all-false pattern fail.
Common mistake
(Fixing physical color names in advance)
The reduction does not assign fixed physical color names in advance. The triangle forces three distinct colors; we name them by the palette vertices after a coloring is chosen. A global permutation of all three colors gives another valid coloring and does not change the encoded truth assignment relative to the palette.
Common mistake
(Treating hardness and membership as one claim)
NP-hardness and NP membership are separate claims. The graph construction transfers hardness from 3-SAT; checking a proposed coloring in polynomial time establishes membership in NP. Neither claim alone is the full NP-completeness proof.
Reading the gadget table efficiently
The table need not be treated as seven unrelated guesses. If , the last four rows all use , and , except that the rows with use because is adjacent to . In each listed row, the terminal edges are checked separately from the internal edges. This organization makes it easier to see that the witnesses work even when some terminal roles refer to the same literal vertex.
For example, with , take . The terminal edges are proper: , , and . The palette edges are proper because and . Finally , and . No hidden constraint remains once these nine edges have been checked.
A witness table proves extension only because it covers all seven truth patterns other than . It is not necessary to list every possible internal coloring for each pattern. Conversely, proving that the all-false pattern fails does not alone prove that all satisfying patterns extend; both halves are used in the reduction.
A full small formula
Consider . Pad the unit clauses as and . The variable gadget forces exactly one of the two literal vertices to have color . The clause gadget attached three times to that false literal then has terminal pattern and cannot be colored. Hence the constructed graph is not three-colorable, matching the unsatisfiable formula.
For the formula , choose and . Give each opposite literal vertex the opposite truth color. The clause has terminal pattern , and the table supplies a proper internal coloring. This constructs a graph-coloring witness from the satisfying assignment without searching over all graph colorings.
Verifying size and certificates
The palette contributes three vertices and three edges. Each variable contributes two vertices and three edges: the pair edge and one edge from each literal vertex to . Each clause contributes four fresh vertices and nine listed edges. Even if a clause repeats a literal, these are still only a constant number of additions; representing the graph as a simple graph can remove duplicate edges without changing proper colorability.
A color certificate assigns one of three labels to every graph vertex. A verifier first checks that every label is valid, then scans the edge list and rejects if an edge has equal-colored endpoints. This takes time polynomial in the explicitly listed vertices and edges. The verifier need not know the satisfying assignment or reverse the reduction to check the certificate.
The reverse implication is nevertheless essential to the hardness proof. If the graph had a proper coloring for an unsatisfiable formula, a coloring algorithm could return yes on a false source instance. Extracting an assignment from the palette and variable gadgets, and then using the all-false impossibility for every clause, excludes that possibility.
Normalizing clause lengths
A clause with two literals can be replaced by , and a unit clause by . Repetition does not change the clause's truth value. The gadget table remains valid when terminal roles repeat, because it is applied only to terminal color patterns actually induced by the shared vertices.
If a formula contains an empty clause, it is unsatisfiable. One fixed no-instance is the complete graph on four vertices: every pair of vertices is adjacent, so four distinct colors would be required. If the formula has no clauses, it is satisfiable; the constructed palette and variable gadgets are colorable by assigning any truth values. These cases keep the mapping total on the stated input convention.
Adding universal vertices turns a three-coloring question into a k-coloring question.
A path to generalization
From three colors to k colors
Adding universal vertices turns a three-coloring question into a k-coloring question.
For , add new vertices to a graph , adjacent to each other and to every vertex of . The new vertices use different colors that no vertex of may use, so the enlarged graph is -colorable exactly when is three-colorable. Hence -colorability is NP-complete for every fixed . What changes is only the palette; the clause gadget is not reused.
Summary
A palette triangle gives truth colors, variable pairs enforce opposite truth values, and the four-vertex clause gadget is colorable exactly when at least one terminal is true. Combining the gadgets gives a polynomial 3-SAT reduction and a verifiable coloring certificate.
Exercises
Quick check
(Why can neither literal vertex in a variable pair receive color ?)
Look at the palette vertex .
Solution · Answer
Both are adjacent to the palette vertex , so a proper coloring forbids color at either endpoint.
Quick check
(In the clause gadget with terminal colors , why must ?)
Which vertices are adjacent to and besides the terminals?
Solution · Answer
Each is adjacent to the palette vertex and to a terminal of color , leaving only .
Quick check
(Verify the edges incident to in the table row .)
Read the row of the table for the colors of .
Solution · Answer
That row has . Vertex differs from , and , satisfying its three incident edges.
Quick check
(Why does a proper coloring of the constructed graph yield a satisfying assignment?)
Use the variable pairs and the gadget property.
Solution · Answer
Every variable pair uses opposite truth colors, defining a consistent assignment. Each clause gadget is colorable only if at least one terminal is , so every clause is true.