A New Proof Opens a Fresh Chapter in the Four-Color Theorem

By proving that every unavoidable configuration can be reduced in this way, you show that the supposed minimal graph is actually four-colorable. The contradiction confirms that the original assumption was false and establishes the four-color theorem.

Eleven years after Kempe announced his proof, mathematician Percy John Heawood identified a subtle flaw in his color-swapping method: when the removed vertex has five neighbors, the procedure can allow adjacent vertices to receive the same color. Heawood was initially reluctant to publicize the error, partly because Kempe’s approach was so elegant. Despite the flaw, the technique—now known as a Kempe chain—remained central to later solutions. “Isn’t it interesting that you make a mistake which is so interesting that it’s named after you?” Thomassen asked.

Ultimately, no one was able to prove that the final configuration in Kempe’s unavoidable set was reducible. A correct proof would instead require a much larger and more complicated collection of 8,900 configurations, along with demonstrations that each one was reducible. The undertaking was far too large to complete by hand and required computers.

In 1976, mathematicians Kenneth Appel and Wolfgang Haken devised a way to reduce the number of possibilities to 1,936 configurations and then to 1,482. Using the University of Illinois’ supercomputers, they verified the reducibility of every configuration. The four-color theorem was finally settled.

The initial reception was skeptical. Computers were then viewed with suspicion and seemed technically inscrutable. Appel and Haken used core memory, which stored information in magnetic material hand-woven into a mesh of wires. “There were all kinds of arguments about how you can possibly trust this proof,” said Ellen Gethner, a mathematician at the University of Colorado, Denver. “What happens if there’s a surge of electricity and you miss that one configuration that would have invalidated the proof?”

Over time, most people came to accept that “four colors suffice,” a phrase the University of Illinois later used on its postal-meter stamps. In 1997, a team of mathematicians closed the remaining questions by simplifying Appel and Haken’s approach and using a computer to identify and verify just 633 configurations. This time, the mathematical community accepted the result immediately.

But the story was far from over.

Venturing Into Unexplored Territory

The latest chapter began on a Danish beach in 2015.

Ken-ichi Kawarabayashi, a graph theorist at Japan’s National Institute of Informatics, was attending a conference with Thorup, his longtime collaborator. They had recently published a major paper together, a work that would later earn them the prestigious Fulkerson Prize—a distinction also awarded decades earlier to Appel and Haken for their four-color research. Standing on the white sand of Nyborg, they considered what to do next. “We can’t really work on a small project,” Kawarabayashi recalled thinking.

The four-color theorem had profoundly influenced both of their careers and helped inspire them to become graph theorists. Nevertheless, they remained dissatisfied with one feature of the 1997 result. Although it provided a method for coloring any graph with four colors, the method was inefficient. For a graph with n² vertices, the coloring process would require n² steps.

Given a large graph, one would have to search for a reducible configuration, remove it, and then repeat the process—searching for another configuration, removing that one, and continuing until the graph was reduced to a form whose four-colorability was clear.

Source link