Kempe's proof attempt, Heawood's correction, and the five color theorem
Follow a connected run of just two colors and swap them: the coloring stays valid. That trick nearly proved the theorem in 1879.
Choose a pair of colors, click a vertex of one of them to light up its chain, then press Swap Colors. Notice the coloring stays valid and a color can free up next to the chain.
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.
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.
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.
Press Next Step to follow Kempe's argument. It works up to degree 4; watch how at degree 5 the two chain swaps get in each other's way.
We want to show that every planar graph can be properly 4-colored. We proceed by induction on the number of vertices.
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.
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.
Step through the five-color proof with Next. This time a single chain swap always frees a color for the last vertex.
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.
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.
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.
Spot a mistake or have an idea?