The Four-Color Theorem Gets a Rare New Proof

Some math problems continue to haunt researchers long after they’ve been solved. A proof emerges, is even celebrated, and yet dissatisfaction lingers. Perhaps the argument is too convoluted — the hunt persists for the elusive one-page paper — or perhaps it fails to give a deeper theoretical insight into why something is true.

Whatever the reason, mathematicians return, again and again, to a case that is otherwise considered closed. One of the most famous such cases is that of the four-color theorem, a problem that transformed how mathematicians think about their subject. The problem is simple to state, and even simpler to see: Given a contiguous map, is it possible to color each region with one of four colors such that no neighboring regions share a color?

In the mid-19th century, the question was of trifling interest to mapmakers, who had far more than four colors at their disposal and saw no particular reason to restrict their palette. But to mathematicians, both amateur and professional, the brain teaser quickly turned into an obsession. The first purported proof, announced in 1879, stood for 11 years before it was proved incorrect.

More wrong answers would follow, from lawyers and doctors and famous graph theorists, too. The status of the problem remained a source of debate until 1997, when the use of computers became more common and a simpler computer-assisted proof was found. Yet even today, the “four-color disease,” as Mikkel Thorup, a computer scientist at the University of Copenhagen, puts it, continues to circulate.

He and Thomassen count themselves among the afflicted. For such a simple statement, there must be a simpler reason why it is true. Or at least a more efficient way to demonstrate it.

After nearly a decade of work, Thorup, Thomassen, and four colleagues in Denmark, Canada, and Japan have produced yet another computer proof of the theorem.