The two pillars of the proof: reducible configurations and the discharging method
The proof of the four color theorem rests on two pillars -- reducibility and discharging. A configuration is reducible if any valid 4-coloring of its surrounding ring of vertices can be extended to include the interior vertices. The discharging method proves that an unavoidable set of reducible configurations must appear in every planar graph.
Together, these two ideas complete the proof: since every planar graph must contain at least one configuration from the unavoidable set, and every such configuration is reducible, any minimal counterexample to the four color theorem leads to a contradiction. There can be no smallest non-4-colorable planar graph.
A configuration is a small subgraph together with its surrounding ring of vertices. Browse through four classic reducible configurations below and watch how any valid 4-coloring of the ring can be extended to color the inner vertices.
A vertex of degree 4 surrounded by its ring of 4 neighbors. Because only 4 colors are used by the ring, the inner vertex can always find a valid color -- in fact, the ring vertices use at most 4 colors, but some must repeat since they are adjacent around the ring, leaving a color free for the center.
Ring vertices start pre-colored. Click "Play Animation" to watch the inner vertices get colored one by one, extending the ring coloring inward. Use Previous/Next to browse different reducible configurations.
Key insight: A configuration is reducible when every possible coloring of the ring of vertices surrounding it can be extended to a valid 4-coloring of the interior. If we know every graph contains a reducible configuration, we can always make progress in a coloring proof.
Discharging assigns each vertex an initial charge of 6 - degree. By Euler's formula, the total charge across all vertices is always exactly 12. Discharging rules redistribute charge between vertices without changing the total -- and by analyzing where positive charge ends up, we can prove that certain configurations must appear.
Each vertex starts with charge 6 - degree. Blue = positive charge, red = negative, gray = zero. Apply discharging rules to redistribute charge. The total charge always equals 12 (by Euler's formula), so positive charge must exist somewhere, forcing certain low-degree configurations to appear.
Key insight: Discharging assigns charges based on vertex degree and redistributes them. By Euler's formula, the total charge is always 12. Since positive charge must exist somewhere, the discharging rules force certain structures to appear.
An unavoidable set is a collection of configurations such that every planar graph must contain at least one member. The discharging method is the tool used to prove unavoidability. Below, explore several planar graphs and see which configuration from our unavoidable set appears in each.
Graph 1 of 6
Found: Vertex of degree 4 or less
Vertex 0 has degree 3. Any planar graph must contain a vertex of degree at most 5 -- and here we found one with degree 3 or less, which is even more constrained.
Every planar graph must contain at least one of these configurations. The highlighted vertices and edges show the detected configuration. Click "Try Another Graph" to see different examples -- in each one, at least one configuration from the unavoidable set is always present.
Key insight: An unavoidable set is a collection of configurations such that every planar graph contains at least one. If every configuration in an unavoidable set is also reducible, the four color theorem follows.