By showing that each unavoidable configuration is “reducible” in this way, you’ve demonstrated that your minimal graph is four-colorable after all — your original assumption was wrong. The four-color theorem must be true.
Unfortunately, 11 years after Kempe announced his proof, the mathematician Percy John Heawood discovered a subtle flaw in his color-swapping procedure: In the case where the vertex you remove has five neighbors, Kempe’s method could lead to the same colors ending up next to one another. Heawood was initially reluctant to report the error, in part because Kempe’s approach was so elegant. And indeed, despite Kempe’s error, his swapping procedure — today known as a Kempe chain — would remain at the core of future solutions to the problem. “Isn’t it interesting that you make a mistake which is so interesting that it’s named after you?” Thomassen said.
In the end, no one was able to show that the last configuration in Kempe’s unavoidable set was reducible. It turned out that a correct proof would instead require identifying a much larger, more complicated set of 8,900 configurations — and showing that all of them are reducible. The task was impossible to deal with by hand. It needed computers.
In 1976, the mathematicians Kenneth Appel and Wolfgang Haken figured out a clever way to lower the number of possibilities first to 1,936 configurations, and then to 1,482. They then used the supercomputers at the University of Illinois to properly reduce each one. At last, they said, the four-color theorem was settled.
The British mathematician Augustus De Morgan sought to stir up broader interest in the four-color problem. “A student of mine asked me today to give him a reason for a fact which I did not know was a fact — and do not yet,” he wrote in an 1852 letter to the prolific mathematician and physicist William Hamilton.
They met a skeptical audience. Computers at the time were scary, technically unknowable. Appel and Haken were using core memory, storing information on magnetic material that was 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?”
Still, most people grew to eventually accept that “four colors suffice,” as the University of Illinois later announced on their postal meter stamps. And in 1997, a team of mathematicians put the matter to bed by simplifying Appel and Haken’s approach, using a computer to identify and check just 633 configurations. This time, the mathematical community accepted the result immediately.
But the story was far from over.
The latest chapter started on a Danish beach in 2015.
Ken-ichi Kawarabayashi, a graph theorist at Japan’s National Institute of Informatics, was at a conference with Thorup, his longtime collaborator. The pair had recently published a major paper together (which would later win them the prestigious Fulkerson Prize, also awarded decades earlier to Appel and Haken for their four-color work). They now stood on the white sand of Nyborg, wondering what to do next. “We can’t really work on a small project,” Kawarabayashi recalled thinking.
The four-color theorem had been a huge influence throughout their careers. It had inspired them, in part, to become graph theorists in the first place. Yet they remained dissatisfied with one aspect of the 1997 result: It had given mathematicians a recipe for coloring any graph with four colors, but that recipe was inefficient. For a graph with n vertices, the coloring process would require n2 steps.
The problem was that if you were handed some large graph and wanted to color it, you would have to search through it for one configuration, remove it, then search for another configuration, remove that, and so on — until you’d reduced your graph to something that was clearly four-colorable.