Kempe's Attempt and Heawood's Correction

Kempe Chains and the Four-Color Problem

The four-color theorem says that every planar graph has a proper vertex coloring with at most four colors. In map language, this is the assertion that four colors suffice to color regions that share a boundary segment. Kempe’s nineteenth-century proof attempt was influential because it used a simple and powerful operation: interchange two colors on a connected region of the graph. The argument failed at a subtle step. Heawood identified the gap and used a related chain argument to prove a nearby result: five colors always suffice.

All graphs in this tutorial are finite and simple unless stated otherwise. A proper vertex coloring assigns colors to vertices so that adjacent vertices have different colors. For two colors \(a\) and \(b\), the subgraph induced by the vertices of those colors has as its edges all graph edges with both endpoints colored \(a\) or \(b\). A Kempe chain is a connected component of this subgraph. Interchanging \(a\) and \(b\) on one such component gives another proper coloring: any edge from a vertex in the component to a vertex outside it cannot have its other endpoint colored \(a\) or \(b\), since that would put the endpoint in the same component.

For a plane graph, the cyclic order of the neighbors of a vertex is the order in which its incident edges occur around that vertex in the embedding. This order matters: paths joining alternating neighbors may be forced to cross. The argument below uses that planar separation fact, not a claim that all colorings of the neighbors are arranged like a cycle of edges.

The Attempt and Its Gap

The usual inductive setup is to remove a vertex \(x\), color the remaining graph, and then restore \(x\). If \(x\) has at most four neighbors, some one of four colors is absent from those neighbors. The difficult case is when \(x\) has five neighbors and all four colors occur among them. A tempting argument selects a repeated color at two neighbors and tries to interchange colors along a chain to free that color at \(x\).

Here is the precise issue with one such step. A Kempe interchange changes every vertex in the chosen component, not just the neighbor at which the interchange starts. If another neighbor has the repeated color but lies outside that component, it keeps that color; if it lies inside, it changes color too. Therefore, showing that one particular chain misses one particular neighbor does not by itself show that the repeated color has disappeared from all five neighbors.

This is the kind of logical gap that matters in reconstructing Kempe’s attempt: a chain interchange is valid as a coloring operation, but a proposed conclusion about which colors remain on the neighbors requires checking every neighbor. The four-color theorem itself is true; the problem is that this chain step does not establish it.

Heawood’s Correction: Five Colors

The five-color proof uses a different configuration. After removing a degree-five vertex, use five colors. If its five neighbors do not all have different colors, at most four colors occur among them and one is available for the removed vertex. If all five colors occur, label the neighbors \(v_1,\ldots,v_5\) in cyclic order and label their colors \(1,\ldots,5\), respectively.

Proof. We use induction on the number \(n\) of vertices. For \(n=0\), the empty coloring is proper. Suppose \(n\ge1\), and assume that every planar graph with fewer than \(n\) vertices is properly colorable with five colors. A planar graph has a vertex of degree at most five, by the low-degree vertex lemma for planar graphs. Choose such a vertex \(x\), and consider the planar graph \(G-x\), obtained by deleting \(x\) and all its incident edges. It has \(n-1\) vertices, so the induction hypothesis gives a proper coloring of \(G-x\) with colors from \(\{1,2,3,4,5\}\).

If \(x\) has at most four neighbors, their colors use at most four of the five colors. Assign an unused color to \(x\); this preserves properness because every edge incident with \(x\) then has differently colored endpoints.

It remains to treat the case that \(x\) has exactly five neighbors and all five colors occur on them. The neighbors must then have distinct colors. Write them \(v_1,\ldots,v_5\) in cyclic order around \(x\), and, by renaming colors, suppose \(v_i\) has color \(i\). Consider the subgraph induced by colors 1 and 3.

If \(v_1\) and \(v_3\) lie in different components of this subgraph, interchange colors 1 and 3 in the component containing \(v_1\). The color of \(v_1\) changes from 1 to 3, and \(v_3\) remains color 3 because it lies in another component. No other neighbor of \(x\) has color 1: the other neighbors had colors 2, 3, 4, and 5, and the interchange only changes colors 1 and 3. Hence color 1 is now absent from the neighbors of \(x\), and we assign color 1 to \(x\).

Otherwise, \(v_1\) and \(v_3\) lie in the same component of the subgraph induced by colors 1 and 3. Since that component is connected, it contains a path between them; choose a path with no repeated vertices. The path uses only vertices of colors 1 and 3. It cannot pass through any of \(v_2,v_4,v_5\), whose colors are 2, 4, and 5. Together with the edges \(xv_1\) and \(xv_3\), the path forms a simple closed curve in the plane. The cyclic order \(v_1,v_2,v_3,v_4,v_5\) places \(v_2\) and \(v_4\) on opposite sides of this curve. A path in the subgraph induced by colors 2 and 4 from \(v_2\) to \(v_4\) would have to cross the curve. It cannot cross the drawn graph in a plane embedding, and it cannot share a vertex with the 1-and-3 path because the two paths use disjoint sets of colors. Thus \(v_2\) and \(v_4\) are in different components of the subgraph induced by colors 2 and 4.

Interchange colors 2 and 4 in the component containing \(v_2\). Then \(v_2\) changes from color 2 to color 4, while \(v_4\) remains color 4. The other neighbors had colors 1, 3, and 5, so color 2 is now absent from all neighbors of \(x\). Assign color 2 to \(x\). In every case the coloring extends to \(G\). This proves the induction step and hence the theorem for all finite planar graphs. \(\square\)

What the Correction Does—and Does Not—Say

Heawood’s separation argument succeeds in the five-color setting because, when five distinct colors occur around a degree-five vertex, each color appears on exactly one neighbor. A swap that changes the color of \(v_2\) therefore removes color 2 from the entire neighborhood, provided \(v_4\) lies in a different 2-and-4 component. The planar separation argument proves exactly that disconnection when the 1-and-3 chain connects \(v_1\) to \(v_3\).

In the four-color attempt, a color can occur on more than one neighbor. The example above illustrates why changing the color of one neighbor is not enough: the repeated color may remain elsewhere. It is not valid to transfer the five-color proof’s conclusion to the four-color setting without proving that every neighbor of the repeated color is recolored or otherwise handled. Heawood’s theorem is a genuine correction yielding a valid result, but it does not prove the four-color theorem.

Finally, the dual language requires care. For a plane graph with no bridges, each edge has distinct faces on its two sides, and proper coloring of the dual vertices expresses the condition that those faces receive different colors. With bridges, the dual has loops, so proper coloring of the full dual is impossible. One can instead formulate face adjacency only between distinct faces across an edge; that convention does not impose a color difference across a bridge. The distinction is essential whenever map coloring is translated into dual vertex coloring.