Kempe's proof attempt, Heawood's correction, and the five color theorem
Kempe chains are the central technique in both the failed and successful approaches to the four color theorem. Named after Alfred Kempe, who introduced them in his celebrated 1879 proof attempt, these structures capture a simple but powerful idea: if you have a valid coloring and you swap two colors along a connected component, the coloring remains valid.
Kempe's proof was widely accepted for eleven years before Percy Heawood discovered a subtle flaw in the argument for vertices of degree five. Yet the technique itself was not at fault -- Kempe chains remain indispensable in every known proof of the four color theorem, including the 1976 computer-assisted proof by Appel and Haken.
A Kempe chain for colors c1 and c2 starting at vertex v is the maximal connected subgraph of vertices colored c1 or c2 that contains v. Select a pair of colors, click a vertex of one of those colors, and watch the chain light up. Then swap the two colors along the chain and verify that the coloring remains valid.
Select a color pair above, then click a vertex of that color to highlight the Kempe chain containing it. Click "Swap Colors" to swap the two colors along the chain.
Key insight: A Kempe chain for colors c1 and c2 starting at vertex v is the maximal connected subgraph of vertices colored c1 or c2 that contains v. Swapping colors along a chain always preserves the validity of the coloring.
In 1879, Alfred Kempe published what he believed was a complete proof of the four color theorem. His inductive argument worked beautifully for vertices of degree at most 4, but the case of degree 5 contained a subtle error. Step through the argument to see where it breaks down.
We want to show that every planar graph can be properly 4-colored. We proceed by induction on the number of vertices.
Key insight: Kempe's proof worked perfectly for vertices of degree 4 but failed for degree 5 because two Kempe chain swaps can interfere with each other. Heawood found this flaw in 1890 -- eleven years later.
While Kempe's four-color proof was flawed, Heawood salvaged enough of the argument to prove the five color theorem: every planar graph can be properly colored with at most five colors. The key difference is that with five colors, a single Kempe chain swap always suffices -- no interference is possible.
By Euler's formula, every planar graph must have at least one vertex with 5 or fewer neighbors. We pick such a vertex v and proceed by induction.
Key insight: With five colors instead of four, the Kempe chain argument works cleanly because a degree-5 vertex has 5 neighbors using at most 5 colors, and a single chain swap always frees up a color.