Five color theorem

Assumptions and equivalent formulations

The usual formulation requires that each region is contiguous (no exclaves), and regions that meet only at a single point are not considered adjacent and may share a color. These map conditions correspond precisely to the standard definition of adjacency in planar graphs. Equivalently, the theorem says that the vertices of any planar graph can be colored with at most five colors so that adjacent vertices have different colors; this vertex-coloring perspective is the version most used in proofs and algorithms.

Key ideas in the proof and constructive method

Elementary proofs of the five color theorem proceed by induction on the number of regions or vertices. A basic combinatorial fact about planar graphs (derived from Euler's formula) ensures that every nontrivial planar graph has a vertex of degree at most five. One removes such a low-degree vertex, colors the remaining graph by the inductive hypothesis, and then attempts to extend the coloring to the removed vertex.

If the removed vertex has degree four or fewer, one can always assign an unused color. The only delicate case is degree five. The classical argument introduces the notion of a Kempe chain: a maximal connected path or component whose vertices use only two colors. By swapping colors along appropriate Kempe chains one can free a color and extend the coloring. A careful use of these swaps yields a complete, finite procedure that always succeeds and therefore a correct proof that five colors suffice.

Historical notes

The problem and related claims date from the late nineteenth century. An early, influential argument by Alfred Kempe introduced the chain method that remains central in the five-color proof, though Kempe's original attempt to prove the stronger four color statement contained a gap. Percy John Heawood analyzed that gap and adapted the method to produce a valid proof that five colors are enough. The four color theorem — the stronger claim that four colors always suffice — required substantially more advanced work and was settled only in the late twentieth century with the aid of computer-aided case analysis; for contrast see four color theorem.

Uses, algorithms, and significance

The five color theorem is important both theoretically and pedagogically. It is a standard illustration of inductive and constructive combinatorial reasoning and of the interaction between planar topology and graph structure. It also gives rise to simple, efficient coloring algorithms: a linear-time algorithm can produce a five-coloring of any planar graph by repeatedly removing low-degree vertices and applying Kempe-chain adjustments when necessary. This makes five-coloring practical for applications where a small fixed palette suffices.

Related distinctions and notable facts

• The five color theorem is weaker than the four color theorem but has much simpler, human-verifiable proofs.
• Its proof relies on basic planar graph facts, notably that planar graphs have vertices of degree at most five; this follows from Euler's formula and counting arguments.
• Algorithms based on the theorem avoid heavy computer case checking and provide constructive colorings; these algorithms are useful in practice for map coloring, frequency assignment, and similar problems where planarity arises.

For elementary introductions and proofs aimed at learners, many textbooks give a complete five-color proof using Kempe chains and induction; accessible overviews and examples of the map interpretation are available online and in survey articles on planar graph coloring, including discussions of map adjacency and exclaves such as those described at map and the notion of disconnected territories at exclave. For further general reading on planar graph coloring problems consult standard references and surveys in graph theory and combinatorics.