A Complete Proof of the Five Color Theorem

The Five Color Theorem

A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. The five color theorem says that every planar graph can be colored using at most five colors. Its proof is a useful combination of induction and planar structure: remove a vertex that has at most five neighbors, color what remains, and then extend that coloring. The only difficult case is when the removed vertex has five neighbors, all with different colors.

A planar graph is a graph that can be drawn in the plane with edges meeting only at common endpoints. When a planar graph is drawn in this way, the edges incident with any vertex have a cyclic order around it. We will use this order in the degree-five case.

We also use the low-degree vertex lemma established in the earlier material on planar graphs: every nonempty finite simple planar graph has a vertex of degree at most five. Here “simple” means that there are no loops or multiple edges. Deleting a vertex and its incident edges leaves a simple planar graph, so the lemma can be applied at each induction step.

Coloring After Deletion

The induction works by coloring a smaller graph first. If the deleted vertex has at most four neighbors, at most four colors are forbidden there, so one of the five colors is available. If it has five neighbors but some two already share a color, the same counting argument applies. We need an additional argument only when all five neighbor colors are different.

Proof. Consider an edge \(xy\). If neither endpoint is in the component being swapped, its colors do not change. If both endpoints are in the component, their colors are interchanged, and because their original colors were different, their new colors are different. If exactly one endpoint is in the component, the other endpoint cannot have color \(i\) or \(j\): otherwise it would be a vertex of \(G_{ij}\) adjacent to the component and therefore in the same component. Thus the unchanged endpoint has a color outside \(\{i,j\}\), which remains different from the changed endpoint’s new color. Every edge remains properly colored. \(\square\)

This lemma explains why the entire component must be swapped. A change to just one vertex need not preserve properness: on a single edge \(xy\) colored \(1,3\), changing only \(x\) from \(1\) to \(3\) makes both endpoints color \(3\).

Why Planarity Resolves the Degree-Five Case

Suppose a vertex \(v\) has five neighbors \(v_1,v_2,v_3,v_4,v_5\) in cyclic order around it, and these neighbors have colors \(1,2,3,4,5\), respectively. If \(v_1\) and \(v_3\) are in different components of \(G_{13}\), swapping the component containing \(v_1\) changes its color to \(3\) without changing \(v_3\). Color \(1\) is then absent from the neighbors of \(v\), so \(v\) can receive color \(1\).

If \(v_1\) and \(v_3\) are connected in \(G_{13}\), planarity ensures that \(v_2\) and \(v_4\) are not connected in \(G_{24}\). The separation argument is the key point.

Proof. Suppose there is a path in \(G_{13}\) from \(v_1\) to \(v_3\), and choose one with no repeated vertices. In the plane embedding, combine this path with the edges \(vv_1\) and \(vv_3\). The result is a simple closed curve: the path lies in \(G-v\), and its endpoints are \(v_1,v_3\), so it meets the two edges at their endpoints and does not pass through \(v\). By the Jordan curve theorem, a simple closed curve separates the plane into two sides. At \(v\), the two edges \(vv_1\) and \(vv_3\) divide a small neighborhood into two sectors. Since the neighbors occur in cyclic order \(v_1,v_2,v_3,v_4,v_5\), the edge toward \(v_2\) lies on one side of the closed curve and the edge toward \(v_4\) lies on the other. Any path from \(v_2\) to \(v_4\) must therefore meet the curve. A path in \(G_{24}\) cannot meet the \(G_{13}\) path: their vertex colors belong to disjoint sets, and edges in a planar embedding do not cross. It cannot meet either edge \(vv_1\) or \(vv_3\), since it lies in \(G-v\), and its vertices have colors \(2\) or \(4\), not \(1\) or \(3\). Thus no path in \(G_{24}\) joins \(v_2\) to \(v_4\), as claimed. \(\square\)

The Jordan curve theorem is the standard planar-topology result used here: a simple closed curve separates the plane into two regions, and a continuous path between the two regions must meet the curve. The graph-theoretic argument uses only this separation property.

Theorem and Proof

Proof. We use induction on the number \(n=|V(G)|\) of vertices. If \(n=0\), the empty function is a proper coloring. Now let \(n\ge1\), and assume that every simple planar graph with fewer than \(n\) vertices is five-colorable. By the low-degree vertex lemma, choose a vertex \(v\) with \(\deg(v)\le5\). The graph \(G-v\) is simple and planar and has \(n-1\) vertices, so the induction hypothesis gives it a proper coloring with colors from \(\{1,2,3,4,5\}\). If \(\deg(v)\le4\), at most four colors occur on its neighbors, so at least one of the five colors is absent there; assign that color to \(v\). The same conclusion holds if \(\deg(v)=5\) but two neighbors have the same color, because then at most four distinct colors occur among the neighbors. It remains to consider \(\deg(v)=5\) with five distinct neighbor colors. In a planar embedding, label the neighbors \(v_1,\ldots,v_5\) in cyclic order and, by renaming the colors, assume \(v_i\) has color \(i\). If \(v_1\) and \(v_3\) lie in different components of \(G_{13}\), swap colors \(1\) and \(3\) on the component containing \(v_1\). The swap is proper by the lemma, it changes the color of \(v_1\) but not \(v_3\), and color \(1\) is now absent from all five neighbors of \(v\); give \(v\) color \(1\). Otherwise, \(v_1\) and \(v_3\) are connected in \(G_{13}\). The planar separation claim shows that \(v_2\) and \(v_4\) are in different components of \(G_{24}\). Swap colors \(2\) and \(4\) on the component containing \(v_2\). This changes \(v_2\) from color \(2\) to color \(4\) and leaves \(v_4\) at color \(4\). The swap is proper, and none of the other three neighbors has color \(2\). Thus color \(2\) is absent from the neighbors of \(v\); give \(v\) color \(2\). In every case we have extended the coloring of \(G-v\) to a proper five-coloring of \(G\). This completes the induction. \(\square\)

Worked Applications of the Proof

Common Pitfalls and Why the Proof Matters

Do not assume a swap works without checking the component. If the \(1,3\)-component containing \(v_1\) also contains \(v_3\), swapping that component changes both neighbor colors and does not make color \(1\) available. The proof first checks whether the two vertices are connected, then uses the planar separation claim to find a different pair of neighbors that can be separated.

Do not swap just one endpoint of a Kempe chain. For an edge colored \(1,3\), changing only its color-\(1\) endpoint to \(3\) creates an improperly colored edge. Swapping both colors on a whole connected component is what preserves every edge constraint.

Do not restrict the theorem to connected graphs. The induction and the low-degree vertex lemma apply to any nonempty simple planar graph, including disconnected graphs and graphs with isolated vertices. Deleting and coloring one vertex at a time handles all components; the empty graph is the induction base.

The five-color theorem is a strong consequence of two simple ingredients: a planar graph always has a low-degree vertex, and the cyclic order around a degree-five vertex imposes a separation constraint on Kempe chains. The second ingredient supplies exactly the extra flexibility needed when ordinary “one unused color” counting fails.