Four Color Theorem Revisited: From Kempe to a New Fast Coloring Algorithm

The Quanta Podcast explores the Four Color Theorem, tracing its origins from mid‑19th century questions to modern computer assisted proofs and a new algorithmic advance. Host Samir Patel discusses with Greg Barber how mathematicians color graphs instead of countries, how Kempe’s early proof faltered, and how Appel and Hak en delivered the first computer aided proof. The conversation then moves to Robertson's formally verified proofs and the latest work by Kawarabayashi and Thorup which batch reduces thousands of configurations to achieve near linear time coloring. Finally, the speakers consider why researchers remain obsessed with a seemingly settled problem and what might come next in this rich area of graph theory.

Introduction

The podcast opens with a discussion of maps, colors, and the Four Color Theorem, reframing it as a graph coloring problem. The host and guest explain how maps can be abstracted into planar graphs where vertices represent countries and edges their borders, turning a geographic puzzle into a clean mathematical one.

Origins and Early Attempts

Tracing back to Francis Guthrie in the 19th century, the problem gained popularity as a minimal coloring question. The conversation covers the shift from a cartography puzzle to a pure math issue, with Leonhard Euler’s foundational graph theory ideas cited as background. Guthrie’s student Auguste de Morgan helped popularize the question, making it a focal point for mathematicians and amateurs alike.

The first major purported proof appeared in 1879 by Alfred Kempe, who argued by contradiction that any map colored with five colors could be recolored with four. Kempe’s approach built on a list of unavoidable configurations in planar graphs and suggested recoloring strategies to eliminate the fifth color.

The Kempe Problem and the 1970s Computer Proof

However, the proof had a flaw. John Heywood later identified a gap in Kempe’s method for certain five‑neighbor configurations, showing that Kempe’s recoloring could fail in some instances. This revealed that a correct four color proof would require a larger and more robust set of configurations and arguments beyond Kempe’s simple cases.

Nearly a century of incremental progress culminated in the 1976 computer-assisted proof by Kenneth Appel and Wolfgang Haken. They used a massive, hand‑proof–checked computer search to reduce the problem to more than a thousand reducible configurations that could be solved with four colors. The result was ground‑breaking but sparked skepticism about computer‑driven reasoning and concerns about reproducibility and elegance.

Formal Verification and Subsequent Refinements

The 1990s brought renewed scrutiny and a shift toward formal verification. A later proof by Neil Robertson and collaborators refined the approach and reduced the number of configurations, and the effort to formalize the proof in software made the result broadly trusted within the mathematical community. This period demonstrated how computational verification could coexist with rigorous human reasoning.

New Efficiency Frontiers

Today’s development, described in a new preprint by Kawarabayashi and Thorup, pushes the efficiency envelope further. The team sought to speed coloring by identifying and processing large batches of configurations simultaneously rather than one by one. They discovered more than 8,000 configurations that could be reduced in parallel, improving the asymptotic performance toward near-linear time with respect to the graph size. The technique still relies on discharging principles and flat portions of planar graphs but scales much more aggressively, aided by high‑performance computing and algorithmic ingenuity.

Beyond Planar Surfaces and Open Questions

The discussion also touches on how these ideas generalize to different topologies, such as coloring on a torus where the Four Color Theorem no longer applies, requiring more colors (seven for a torus). The speakers note that researchers hope to adapt these powerful techniques to broader questions in graph theory and algorithms, including a long‑sought non computerized proof that would offer a simple, elegant explanation of four‑colorability.

What Comes Next

The conversation closes with reflections on the enduring allure of a simple statement that yields deep mathematics and surprising computational complexity. While AI‑assisted proofs and formal verification have strengthened trust in results, many mathematicians still yearn for a concise, human‑readable proof. Greg Barber’s accompanying article on Quanta Magazine offers visualizations that help readers grasp the graph structures and recoloring ideas behind this enduring problem.