Four-Color Theorem Gets a New, More Efficient Proof

The four-color theorem is a famous puzzle in mathematics: on any contiguous map, can every region be colored with just four colors so that no two neighboring regions share a color? The question dates to 1852, when mathematician Francis Guthrie noticed he needed only four colors while coloring a map of English counties, and wondered if this was always true. His brother's adviser, Augustus De Morgan, took interest and helped popularize the puzzle.

In 1879, Alfred Bray Kempe announced a proof, celebrated at the time in an announcement carried by the journal Nature. His argument stood for 11 years before it was found flawed, and more incorrect proofs followed. The theorem was finally proved in 1976, using computer methods many mathematicians considered scandalous, which reopened debate over what counts as a valid proof. That debate persisted until 1997, when a simpler computer-assisted proof was found.

Now a six-person team — including Carsten Thomassen of the Technical University of Denmark, Mikkel Thorup of the University of Copenhagen, Ken-ichi Kawarabayashi, Bojan Mohar and two more colleagues based in Denmark, Canada and Japan — has produced another computer-assisted proof after nearly a decade of work. It was posted online in March 2026 and will be presented in November at the Foundations of Computer Science conference.

The new proof is, in some ways, more complicated than earlier ones. But in building it, the team found a far more efficient way to color maps, and uncovered new insights into the structural properties of planar graphs — the point-and-line representations mathematicians use to turn maps into graph-coloring problems. Those insights could open the door to progress on other graph-theory problems.

Thomassen, a graph theorist at the Technical University of Denmark, said the puzzle's simplicity explains its pull. 'Here we have a problem that even a child can understand,' he said. 'I think that's the reason why it has been such a big challenge.'