Key Terms and Definitions

Planar Graphs
A planar graph is a graph that can be drawn on a plane without any of its edges crossing. Each region of a map corresponds to a vertex, and shared borders between regions are represented as edges
Chromatic Number
The chromatic number of a graph is the smallest number of colors required to color its vertices so that no two adjacent vertices share the same color. For the Four Color Theorem, the goal is to show that the chromatic number of any planar graph is at most four
Adjacency and Regions
Two regions in a map are considered adjacent if they share a common boundary (more than just a point). In the corresponding graph, this means the vertices for these regions are connected by an edge. Non-adjacent regions can share the same color, simplifying the coloring problem
Euler's Polyhedral Formula
For any planar graph, Euler’s formula relates the number of vertices V, edges E, and faces F (regions, including the outer unbounded region): V−E+F=2. This formula helps constrain the structure of planar graphs and proves that certain configurations must always exist, like vertices with a low degree (number of edges)
Kempe Chains
A Kempe chain is a connected sequence of vertices in a graph, where only two colors alternate along the chain. For instance, if a vertex is red, and its neighbor is green, all adjacent red-green vertices form a Kempe chain
Reducible Configurations
A reducible configuration is a specific arrangement of regions or vertices in a planar graph that can always be colored using four colors, assuming the surrounding map is already four-colorable. Identifying reducible configurations allows mathematicians to simplify the problem by breaking it into smaller, more manageable pieces
Unavoidable Sets
Any planar graph (or map) must contain at least one configuration from a particular set of configurations, called an unavoidable set

Early and Modern Proofs of the Four-Color Theorem

Kempe's Proof

Kempe’s proof was the first notable proof, and while it was incorrect, it serves as a conceptual tool. His proof is outlined here:

Consider a map in which all regions except one, X, are colored using four colors: red, yellow, green, and blue. We need to find a valid color for X.

Case 1: X is not surrounded by regions of all four colors.

In this case, there is at least one color that is not used by any of the regions surrounding X. Assign that unused color to X, and the coloring is complete.

Case 2: X is surrounded by regions A, B, C, and D (in that order) colored red, yellow, green, and blue, respectively.

We must determine if we can modify the coloring of surrounding regions to allow X to be colored.

Subcase 2.1: There is no chain of adjacent regions alternately colored red and green connecting A and C.

If such a chain does not exist, we can change the color of A from red to green, then swap the colors of all red/green regions in the chain connecting A. Since C is not part of this chain, it remains green. Now, X can be colored red, as no adjacent region has this color.

Subcase 2.2: There is a chain of adjacent regions alternately colored red and green connecting A and C.

In this case, observe the regions colored yellow and blue.

Since the red/green chain connects A and C, there can be no chain of adjacent regions alternately colored yellow and blue connecting B and D. This follows because such a chain would need to cross the red/green chain, which is not possible in a planar graph.

Since no yellow/blue chain exists between B and D, we can now apply a similar recoloring process: change B’s color from yellow to blue, and swap the colors of all yellow/blue regions in the chain connected to B. This ensures that D remains blue, allowing us to color X yellow.

Kempe’s method of color-swapping using Kempe chains did not work in all cases. Specifically, there exist configurations where color-swapping introduces new conflicts rather than resolving them (Birkhoff et al., n.d.).

Kempe Chain Example

The Five Color Theorem by Percy Heawood

Claim: A planar graph G can be assigned a proper vertex k-coloring such that k≤5.

Note that planar graphs satisfy Euler’s formula: V−E+F=2

From Euler’s formula, it can be shown that every planar graph has at least one vertex of degree ≤5 (meaning it is connected to at most five other vertices).

Base Case: A graph with 5 or fewer vertices can be trivially colored with 5 colors.

Inductive Hypothesis: Assume that every planar graph with fewer than V vertices can be colored using at most five colors.

Inductive Proof: Consider a planar graph G with V vertices. By Euler’s formula, there exists at least one vertex v of degree ≤5. Remove v and its adjacent edges from the graph, leaving a subgraph G′ with V−1 vertices.

By the inductive hypothesis, G′ can be colored using at most five colors. Reintroduce v and its edges into the graph. Since v has at most 5 neighbors, it is connected to at most 5 differently colored vertices.

Now consider two cases:

Case 1: v is adjacent to fewer than 5 vertices.

In this case, there is at least one of the five colors not used by v’s neighbors. Assign this color to v, completing the coloring.

Case 2: v is adjacent to exactly 5 vertices, each colored with a different color.

It’s always possible to recolor some of these neighbors to free up one of the five colors for v:

Consider two of v’s neighbors that are colored red and green. If these two vertices are not connected by a red-green Kempe chain, we can swap their colors. This frees up red or green for v.

If a red-green Kempe chain exists, Heawood shows that a similar argument can be applied to the yellow-blue pair of vertices. Since the graph is planar, no two Kempe chains of different color pairs can intersect in a way that blocks all color swaps. This ensures that at least one color can be reassigned, allowing v to be colored.

In either case, v can be assigned a valid color, completing the 5-coloring of G.

By induction, any planar graph can be colored using at most five colors, proving the theorem.

Heawood’s work showed that five colors suffice for any planar graph, providing an important stepping stone toward proving that only four colors are actually necessary (Carter, 2017).

Heesch and the Discharging Method

Heesch refined the discharging method, a technique used to prove reducibility:

Initial Setup: Assign an initial "charge" (often related to the degree of vertices) to different parts of the graph based on Euler’s formula.

Redistribution: Use specific rules to redistribute charge among vertices and faces while preserving the total sum of the charges.

Outcome: Show that certain configurations cannot retain enough charge to exist, proving their reducibility.

This method became a key part of the Appel-Haken proof and is still used in graph theory.

Heesch was one of the first to suggest using computers to handle the vast number of configurations involved in the Four Color Theorem. He estimated that proving the theorem would require checking thousands of potential configurations for reducibility—a task too large for humans to perform manually. Although limited by the computational resources of his time, Heesch developed algorithms and strategies that later mathematicians could implement more effectively.

Heesch began compiling a comprehensive list of potential configurations that could appear in planar graphs. His work identified a significant number of reducible configurations, narrowing the problem to a finite (though large) set of cases. Appel and Haken directly built on Heesch’s methods in their 1976 proof. They used his ideas of reducibility and discharging, combined with computer verification, to systematically eliminate all possible counterexamples (Wilson, 2023).

Appel-Haken official proof of the 4-color theorem

The proof builds on earlier work, particularly the ideas of reducible configurations and the discharging method, developed by Heinrich Heesch. Appel and Haken’s key insight was to combine these techniques with computer verification to handle the vast number of configurations involved. The strategy was to identify a large, unavoidable set of configurations and then prove that each configuration in the set was reducible.

They used the discharging method to help them identify unavoidable sets of configurations. This process demonstrated that every planar graph contained one of the configurations in a preselected unavoidable set.

The most controversial and innovative aspect of the proof was the extensive use of computers to check the reducibility of configurations.

Key Steps:

Appel and Haken identified 1,482 reducible configurations. These configurations formed a large unavoidable set for any planar graph.

Using a computer, they checked that each of these configurations was reducible. This involved complex case analysis and detailed calculations that would have been impractical to perform by hand.

Since every planar graph contains at least one of the configurations in the unavoidable set, and since all these configurations are reducible, it follows that any planar graph can be four-colored (Wilson, 2023).



Back to main page ↑ Top