Fact-checked by Grok 2 weeks ago

Five color theorem

The Five Color Theorem states that the vertices of every planar graph can be properly colored using at most five colors, meaning no two adjacent vertices receive the same color.^[1] This result, first proved in 1890 by Percy John Heawood, is equivalent to the assertion that the regions of any map drawn on a plane can be colored with five colors such that no two adjacent regions share the same color.^[2] Heawood's proof salvaged a flawed 1879 attempt by Alfred Bray Kempe to prove the stronger Four Color Theorem, adapting Kempe's chain method while correcting its error.^[3] The theorem's proof proceeds by mathematical induction on the number of vertices in the graph.^[4] Euler's formula for connected planar graphs, V - E + F = 2 (where V is the number of vertices, E the number of edges, and F the number of faces), implies that every simple planar graph has a vertex of degree at most 5.^[5] Removing such a vertex allows the remaining graph to be 5-colored by the inductive hypothesis; reinserting it then permits coloring the vertex with an available color, or, in the case of degree 5 with all five colors used among neighbors, resolving conflicts via Kempe chains—alternating paths of two colors that can be swapped to free a color without violating planarity.^[4] This approach yields a contradiction if a minimal non-5-colorable planar graph is assumed to exist.^[6] As a foundational result in graph theory, the Five Color Theorem provides an accessible entry into map coloring problems and has influenced extensions, such as Carsten Thomassen's 1994 proof that planar graphs are 5-choosable (list-colorable from lists of five colors per vertex).^[2] It contrasts with the Four Color Theorem, proved in 1976 by Kenneth Appel and Wolfgang Haken via exhaustive computer case analysis of over 1,900 configurations, highlighting the computational challenges of the four-color bound.^[3] The theorem underscores the chromatic number of planar graphs being at most 5—a bound later tightened to 4 by the Four Color Theorem—with generalizations to higher-genus surfaces via the Heawood conjecture (now theorem).^[7]

Background Concepts

Graph Coloring Fundamentals

Graph coloring is the problem of assigning colors to the vertices of a graph such that no two adjacent vertices share the same color.^[8] This assignment ensures that each color class forms an independent set, meaning no edges connect vertices within the same color.^[9] The chromatic number, denoted \chi(G), of a graph G is the smallest number of colors required to achieve such a proper coloring.^[10] For instance, the complete graph K_n, where every pair of vertices is connected by an edge, has chromatic number n, as each vertex must receive a distinct color.^[10] In contrast, bipartite graphs, which consist of two disjoint sets of vertices with edges only between the sets, have chromatic number 2, allowing a simple two-color partitioning.^[10] The concept of graph coloring originated from the practical challenge of coloring maps so that adjacent regions receive different colors, providing a combinatorial framework for analyzing such problems.^[11] While vertex coloring focuses on vertices, a related but distinct problem is edge coloring, where colors are assigned to edges so that no two edges sharing a vertex have the same color; Vizing's theorem states that the edge chromatic number of a simple graph is either \Delta or \Delta + 1, where \Delta is the maximum degree.^[12]

Planar Graphs and Euler's Formula

A planar graph is one that can be embedded in the plane such that no two edges intersect except possibly at their endpoints (vertices). This property allows the graph to represent geographical maps or other two-dimensional structures without crossings, forming the foundation for analyzing coloring problems in such contexts.^[13] The classical map coloring problem—assigning colors to regions so that adjacent regions (sharing a boundary of positive length) receive different colors—can be reformulated in graph-theoretic terms using the dual of a planar graph. In this dual graph, each face (region) of the original embedding becomes a vertex, and an edge connects two vertices if the corresponding faces share a boundary edge in the primal graph. Thus, properly coloring the vertices of the dual graph ensures no adjacent regions in the map share the same color, establishing a direct equivalence between map coloring and vertex coloring of planar dual graphs.^[14] A key structural relation for connected planar graphs is given by Euler's formula:
V - E + F = 2,
where V is the number of vertices, E the number of edges, and F the number of faces (including the infinite outer face). This formula, which holds for any connected plane graph, arises from inductive arguments on the number of faces or vertices; for instance, starting from a tree (where F = 1 and E = V - 1, satisfying the equation), adding edges that create new faces preserves the relation by increasing E and F equally.^[15] From Euler's formula, important bounds on the density of simple planar graphs (no loops or multiple edges) follow. In such graphs, each face is bounded by at least three edges, and each edge is incident to at most two faces, yielding the handshaking lemma for faces: $2E \geq 3F, or F \leq \frac{2E}{3}. Substituting into Euler's formula gives:
V - E + \frac{2E}{3} \leq 2 \implies V - \frac{E}{3} \leq 2 \implies E \leq 3V - 6
for V \geq 3. The average degree of vertices is then \frac{2E}{V} \leq \frac{2(3V - 6)}{V} = 6 - \frac{12}{V} < 6, implying every simple planar graph has a vertex of degree at most 5. This bound highlights the sparsity of planar graphs compared to denser non-planar ones.^[16] Planarity can also be characterized by forbidden substructures via Kuratowski's theorem: a graph is planar if and only if it contains no subgraph homeomorphic to (i.e., a subdivision of) the complete graph K_5 or the complete bipartite graph K_{3,3}. These minors serve as the minimal obstructions to planarity, as both K_5 and K_{3,3} violate the edge bound E \leq 3V - 6 or Euler's formula when embedded.^[17]

Theorem and History

Formal Statement

The five color theorem states that every planar graph G is 5-colorable, meaning its chromatic number satisfies \chi(G) \leq 5.^[18] This implies that the vertices of any planar graph can be properly colored using at most five colors such that no two adjacent vertices share the same color.^[18] An equivalent formulation applies to map coloring: any division of the plane into finitely many regions (such as countries on a map) can be colored with at most five colors so that regions sharing a boundary of positive length (rather than merely a point) receive different colors.^[19] As a corollary, no planar graph requires more than five colors for a proper vertex coloring. In contrast, non-planar graphs can require more; for example, the complete graph K_6 has chromatic number \chi(K_6) = 6.^[18]

Development and Key Figures

The origins of the five color theorem trace back to the four color conjecture, first proposed in 1852 by Francis Guthrie, a South African mathematician studying at University College London, who observed that four colors sufficed to color a map of England's counties without adjacent regions sharing the same color.^[20] Guthrie shared the idea with his brother Frederick, who conveyed it to their professor, Augustus De Morgan, prompting De Morgan to popularize the problem through correspondence, including a letter to William Rowan Hamilton on October 23, 1852.^[20] In 1879, Alfred Bray Kempe, a British mathematician and barrister, attempted a proof of the four color conjecture in his paper "On the Geographical Problem of the Four Colours," published in the American Journal of Mathematics.^[20] Although Kempe's argument for four colors contained a subtle flaw—later exposed in 1890—his methods were adapted by Heawood to successfully establish that five colors are sufficient for any planar map, providing the first rigorous bound beyond the trivial six-color result.^[20] This five-color outcome emerged as a byproduct of Kempe's inductive approach using what became known as Kempe chains, though the full four-color claim garnered widespread initial acclaim.^[20] The definitive proof of the five color theorem came in 1890 from Percy John Heawood, a British mathematician at Durham University, who critiqued Kempe's work in his paper "Map Colour Theorem," published in the Quarterly Journal of Pure and Applied Mathematics.^[20] Heawood demonstrated the error in Kempe's four-color proof by constructing a counterexample map requiring careful chain analysis, but adapted and corrected the techniques to rigorously prove that every planar graph is five-colorable, solidifying the theorem's status.^[20] Around the same time, in 1880, Scottish physicist and mathematician Peter Guthrie Tait reformulated the four color problem in graph-theoretic terms, linking map coloring to edge-coloring of cubic planar graphs in two papers presented to the Royal Society of Edinburgh.^[20] Tait's approach, while influential in bridging topology and graph theory, contained its own errors and did not directly advance the five color theorem but highlighted key equivalences.^[20] Following Heawood's proof, the five color theorem saw no major refinements, as it served primarily as a stepping stone to the stronger four color theorem, which remained open until 1976 when Kenneth Appel and Wolfgang Haken provided a computer-assisted proof using reducible configurations.^[21] Their work, published in the Bulletin of the American Mathematical Society, confirmed four colors suffice and underscored the five color result's foundational role in the broader problem.^[21] Key figures in the theorem's development include Guthrie and De Morgan for posing the conjecture, Kempe for the initial five-color insight, Heawood for the rigorous proof, and Tait for the graph reformulation.^[20]

Proof Methods

Inductive Proof by Contradiction

The classical inductive proof of the five color theorem proceeds by contradiction and relies on the concept of Kempe chains to resolve coloring conflicts around a low-degree vertex. This approach was developed by Percy Heawood in 1890, adapting Alfred Kempe's earlier techniques from his attempted proof of the four color theorem.^[22]^[23] Assume, for the sake of contradiction, that there exists a planar graph that is not 5-colorable. Let G be a minimal counterexample, meaning a planar graph with the smallest number of vertices that requires more than five colors. Such a G must have minimum degree at least 5, because if it had a vertex of degree at most 4, removing that vertex would yield a smaller graph colorable with five colors by the induction hypothesis, and the coloring could be extended to the removed vertex using an unused color among its at most four neighbors, contradicting the minimality of G.^[22]^[24] By Euler's formula applied to planar graphs, G must contain a vertex v of degree at most 5.^[22] By the induction hypothesis—that every planar graph with fewer vertices than G is 5-colorable—the graph G − v admits a proper 5-coloring using colors 1 through 5. If the neighbors of v use at most four distinct colors in this coloring, then v can be assigned one of the missing colors, yielding a 5-coloring of G and a contradiction. Thus, the neighbors of v must use all five colors. Since the degree of v is at most 5, this situation arises precisely when the degree is exactly 5 and the five neighbors receive the five distinct colors. Label these neighbors u₁, u₂, u₃, u₄, u₅ in clockwise order around the face incident to v in a planar embedding of G − v, and suppose they are colored 1, 2, 3, 4, 5, respectively.^[24]^[23] To extend the coloring to v, Heawood's method employs Kempe chains, which are connected components in the subgraph of G − v induced by vertices of two specific colors a and b. A Kempe a-b chain containing a neighbor u_i is the maximal alternating path (or cycle) of colors a and b starting from u_i. Consider the Kempe 1-3 chain C_1,3 containing u₁. If C_1,3 does not contain u₃, then interchanging colors 1 and 3 along C_1,3 (a Kempe interchange) recolors u₁ with 3, freeing color 1 among the neighbors of v, which can then be assigned to v. This produces a proper 5-coloring of G, yielding a contradiction.^[22]^[24] Now suppose C_1,3 does contain u₃, so there is an alternating 1-3 path connecting u₁ and u₃. In the planar embedding, this path lies in one of the two regions bounded by the cycle formed by the path and the neighbor arc u₁–u₂–u₃. Consider the Kempe 2-4 chain C_2,4 containing u₂. If C_2,4 does not contain u₄, interchanging colors 2 and 4 along C_2,4 recolors u₂ with 4, freeing color 2 for v and again yielding a 5-coloring of G. The remaining possibility is that C_2,4 also contains u₄, implying an alternating 2-4 path connecting u₂ and u₄. However, since the color sets {1,3} and {2,4} are disjoint, these two paths are vertex-disjoint. In the planar embedding, the 1-3 path from u₁ to u₃ and the 2-4 path from u₂ (between u₁ and u₃) to u₄ (adjacent to u₃) must cross to both exist without sharing vertices, contradicting the planarity of G. Therefore, this case cannot occur, and at least one of the Kempe interchanges succeeds, allowing v to be colored and contradicting the assumption that G is not 5-colorable.^[22]^[24]^[23] This case analysis handles the degree-5 vertex, completing the induction and proving that no such counterexample exists, so every planar graph is 5-colorable. Heawood's adaptation avoids the complications that arose in Kempe's four-color attempt, where simultaneous interchanges for multiple pairs could fail due to nested or overlapping chains in more constrained color sets.^[22]^[23]

Topological Proof Using Minors

In 1974, Paul C. Kainen presented a concise proof of the five color theorem that relies on the non-planarity of the complete graph K_6, which has chromatic number 6.^[25] The proof assumes a minimal counterexample H to the theorem—a planar graph with the smallest number of vertices and \chi(H) > 5. By Euler's formula, H has a vertex v of degree at most 5. Let H' = H - v, which is 5-colorable by minimality. If the neighbors of v use fewer than five colors, v can be colored easily. Otherwise, v has exactly five neighbors v_1, \dots, v_5, each with a distinct color 1 through 5. Since H is planar, it cannot contain K_6 as a subgraph. Thus, the set \{v_1, \dots, v_5\} cannot induce a complete graph K_5 (otherwise adding v would form K_6), so there exist at least two non-adjacent neighbors, say v_1 and v_2. Construct a new graph H'' from H' by identifying v_1 and v_2 into a single vertex v' (contracting them, with v' adjacent to all former neighbors of v_1 or v_2). The proof shows that H'' remains planar, as any potential crossing in the embedding can be resolved without violating planarity, using the non-planarity of K_6. Moreover, H'' has fewer vertices than H (specifically, two fewer), so it is 5-colorable by the induction hypothesis. A 5-coloring of H'' can be extended back to a 5-coloring of H', since v_1 and v_2 are non-adjacent and their common neighbors can be handled appropriately (noting they had different colors 1 and 2). Finally, this coloring of H' can be extended to v using the available color among its neighbors, yielding a 5-coloring of H and a contradiction.^[25] Kainen's approach generalizes: any graph that becomes planar after deleting at most two edges (skewness at most 2) is 5-colorable, as the proof extends by accounting for these limited defects without introducing a K_6 subgraph.^[25] This minor-based perspective (via contractions) relates to Hadwiger's conjecture, which posits that every graph without a K_k minor is (k-1)-colorable; the case k=6 would imply 5-colorability for K_6-minor-free graphs (including planar ones), but it remains open.

Constructive Algorithms

Algorithmic Approaches

The development of algorithmic approaches for five-coloring planar graphs transitioned from the existential inductive proofs of the theorem to practical, efficient constructions, adapting Kempe's color interchange ideas into computable procedures that avoid the full complexity of simultaneous chain manipulations. These methods emphasize identifying low-degree vertices or structural separators to recursively color subgraphs, ensuring the coloring can be extended without conflicts. Early algorithms simplified Kempe's approach by processing color swaps in batches rather than individually, enabling polynomial-time execution on graphs with n vertices.^[26] A seminal contribution came from Lipton and Miller in 1978, who devised an O(n log n)-time algorithm using a batching technique for Kempe chains. This method groups multiple potential color interchanges and resolves them collectively, leveraging the planar embedding to limit interference and achieve subquadratic performance. Their approach draws on planar separators, which partition the graph into components of roughly equal size, allowing recursive coloring of subproblems before integrating the separator vertices.^[27] Subsequent advancements reduced the time complexity to O(n). In 1981, Chiba, Nishizeki, Abe, and Ozawa introduced a linear-time algorithm that recursively removes vertices of degree at most 5, colors the reduced graph, and extends the coloring using local adjustments based on neighborhood colors. This relies on the guaranteed existence of such vertices in planar graphs and efficient embedding representations to track adjacencies.^[26] Further optimizations appeared in 1984 with Frederickson's work, which refined vertex selection strategies to identify degree-5 vertices adjacent to limited color sets more rapidly, ensuring the recursive reductions remain balanced and linear overall. These improvements build on strengthened structural lemmas for planar graphs, minimizing the depth of recursion.^[28] At the heart of these algorithms lies recursive decomposition via separators, which split the planar graph into independent subgraphs colorable with five colors, followed by careful merging along the O(√n)-sized separator to resolve any color clashes using available Kempe-like swaps. This divide-and-conquer paradigm exploits the planar separator theorem to maintain efficiency across recursion levels. Wernicke's theorem underpins several of these methods. It states that every simple connected planar graph with minimum degree 5 has a vertex of degree 5 adjacent to at most three other degree-5 vertices. This structural property is used during the merging phase or reductions to guarantee that, in a partial coloring of the rest of the graph (e.g., with four colors), a free color is available for the vertex or can be freed via simple swaps.

Linear-Time Implementation Details

Linear-time algorithms for five-coloring planar graphs, such as that developed by Chiba, Nishizeki, Abe, and Ozawa in 1981, build on the inductive structure of the theorem while ensuring efficient computation. This approach operates on a planar embedding of the input graph, computed in O(n) time using standard methods like those of Hopcroft and Tarjan. The algorithm proceeds by recursively reducing the graph: it identifies and removes vertices of degree at most 5 (guaranteed by Euler's formula), updates the degrees and adjacencies of remaining vertices, and colors the reduced graph by induction.^[26]^[29] For a removed vertex v of degree d ≤ 5, when reinserting it after coloring its neighbors, at least 5 - d + 1 ≥ 1 colors are available among the five, since the neighbors use at most d colors. If all five colors are used (only possible for d=5), local Kempe chain swaps or the structural guarantees from Wernicke's theorem ensure a color can be freed without global recomputation. Specifically, the algorithm checks for color conflicts in constant time per vertex, using the embedding to access neighbors efficiently. Reductions are managed via a queue or stack of low-degree vertices, with each update taking O(1) time on average due to the bounded degree in planar graphs.^[26] The base case is a graph with at most five vertices, which is trivially 5-colorable. The proof of correctness relies on the fact that planar graphs always admit such reductions without creating irreducible configurations, as per the five color theorem. The overall complexity is O(n), as each of the n vertices is processed a constant number of times, with amortized constant-time operations for degree updates and color assignments. This makes the algorithm practical and efficient for large planar graphs.^[26]

References

[1]
5.10 Coloring Planar Graphs
A planar graph can be drawn in the plane with no crossing edges. The Five Color Theorem states that every planar graph can be colored with 5 colors.
[2]
Colorful Mathematics: Part II - AMS :: Feature Column from the AMS
Planar graphs are 5-choosable. Thus, Thomassen provided a new proof of the Heawood theorem that plane graphs can be vertex-colored with five colors. Not only ...
[3]
5-Color Theorem - Wooster Physicists
Feb 5, 2023 · Every map is 5-colorable. The proof is by induction on the number of vertices of the corresponding graphs.Missing: theory | Show results with:theory
[4]
[PDF] Proof of the Five Color Theorem
The Five Color Theorem states every planar graph can be 5-colored. The proof uses induction, starting with a single vertex and then adding vertices.
[5]
[PDF] euler's formula and the five color theorem
Aug 24, 2012 · Euler's formula (V-E+F=2) is used to prove the Five Color Theorem, which is easier to prove than the Four Color Theorem.Missing: theory | Show results with:theory
[6]
5-Color Theorem
The 5-color theorem states that every planar graph is 5-colorable. The proof is by contradiction, assuming a graph that cannot be colored with five colors.
[7]
Heawood Conjecture -- from Wolfram MathWorld
Heawood, P. J. "Map Colour Theorem." Quart. J. Math. 24, 332-338, 1890. Ringel, G. Map Color Theorem. New York: Springer-Verlag, 1974. Ringel, G. and Youngs ...
[8]
Graph Coloring -- from Wolfram MathWorld
Graph coloring is the assignment of labels or colors to the edges or vertices of a graph. Common types are edge and vertex coloring.
[9]
Vertex Coloring -- from Wolfram MathWorld
A graph having a k -coloring (and therefore chromatic number chi(G)<=k ) is said to be a k-colorable graph, while a graph having chromatic number chi(G)=k ...
[10]
Chromatic Number -- from Wolfram MathWorld
The chromatic number of a graph is the smallest number of colors needed to color its vertices so that no two adjacent vertices share the same color.
[11]
Four Polynomials
Graph-coloring problems started in the form of coloring maps such that countries sharing a proper part of their boundaries get colored with differ- ent colors.
[12]
Vizing's Theorem -- from Wolfram MathWorld
Vizing's theorem states that a graph can be edge-colored in either Delta or Delta+1 colors, where Delta is the maximum vertex degree of the graph.
[13]
Planar Graph -- from Wolfram MathWorld
A graph is planar if it can be drawn in a plane without graph edges crossing (i.e., it has graph crossing number 0). The number of planar graphs with n=1 ...
[14]
[PDF] Planar Graphs and Graph Coloring
Dec 1, 2010 · A coloring of a graph G assigns a color to each vertex of G, with the restriction that two adjacent vertices never have the same color. The chro ...
[15]
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_(Morris)/03:_Graph_Theory/15:_Planar_Graphs/15.02:_Eulers_Formula
[16]
[PDF] Planar Graphs - Rutgers University
Taking this relation and substituting it into Euler's formula, we get: |E| ≤ 3|V | − 6. Corollary 3. The average degree of vertices in a planar graph is ...
[17]
[PDF] Math 228: Kuratowski's Theorem
Then G is nonplanar if and only if G contains a subgraph that is a subdivision of either K3,3 or K5. In order to prove this theorem, let's first walk through ...
[18]
[PDF] GRAPH THEORY WITH APPLICATIONS
The Five-Colour Theorem and the Four-Colour Conjecture 156. Nonhamiltonian ... can always properly colour the vertices of a planar graph with at most five.
[19]
Map‐Colour Theorem - London Mathematical Society (LMS) - Wiley
Volume s2-51, Issue 1 pp. 161-175 Proceedings of the London Mathematical Society. Papers. Full Access. Map-Colour Theorem. P. J. Heawood,. P. J. Heawood.
[20]
The four colour theorem - MacTutor History of Mathematics
On 17 July 1879 Alfred Bray Kempe announced in Nature that he had a proof of the Four Colour Conjecture. Kempe was a London barrister who had studied ...
[21]
Every planar map is four colorable - Project Euclid
Every planar map is four colorable. K. Appel, W. Haken. DOWNLOAD PDF + SAVE TO MY LIBRARY. Bull. Amer. Math. Soc. 82(5): 711-712 (September 1976).
[22]
None
### Summary of Heawood's Inductive Proof of the Five-Color Theorem
[23]
[PDF] Section 11.2. The Five-Colour Theorem
Jan 17, 2021 · Note. As discussed in the previous section, Alfred Kempe published an incorrect proof of The Four-Colour Theorem in 1879.<|separator|>
[24]
[PDF] 5-Color Theorem (7.3.1) Every planar graph is 5 ... - UCSD Math
▷ To 5-color a planar graph on k + 1 vertices, first color a k-vertex subgraph (induction hypothesis), then strategically. “switch” colors to free up a color ...
[25]
Proceedings of the American Mathematical Society - AMS
A generalization of the 5 -color theorem. HTML articles powered by AMS MathViewer. by Paul C. Kainen: Proc. Amer. Math. Soc. 45 (1974), 450-453: DOI: ...Missing: minors | Show results with:minors
[26]
A Linear 5-Coloring Algorithm of Planar Graphs - Semantic Scholar
A Batching Method for Coloring Planar Graphs · R. LiptonRaymond E. Miller. Mathematics, Computer Science. Inf. Process. Lett. 1978. 26 Citations. Add to Library.
[27]
Efficiently four-coloring planar graphs - ACM Digital Library
Efficiently four-coloring planar graphs. Authors: Neil Robertson.