GoKawiilBy 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. Public Domain
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.
Searching No-Man’s Land
The latest chapter started on a Danish beach in 2015.
... continue reading