SoylentNews

hubie [soylentnews.org] writes:

By revisiting the famous problem mathematicians have gained important new insights into the nature of graphs [quantamagazine.org]:

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 [jstor.org], 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. "Here we have a problem that even a child can understand," said Carsten Thomassen [mat.dtu.dk], a graph theorist at the Technical University of Denmark. "I think that's the reason why it has been such a big challenge."

The theorem was finally proved nearly a century later [projecteuclid.org] — but with computer methods that were considered scandalous at the time, causing mathematicians to question what they considered a proof in the first place. 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 [sciencedirect.com] was found.

Yet even today, the "four-color disease," as Mikkel Thorup [hjemmesider.diku.dk], 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.

[...] In 1852, the mathematician Francis Guthrie was coloring in a map of English counties when he noticed that he needed only four colors. Was this always true, he wondered? He asked his brother Frederick, also a mathematician, whose adviser, Augustus De Morgan, took an interest in the question and decided to market it to a wider audience. In 1879, when a mathematician named Alfred Bray Kempe claimed to have a solution, a press release announced the achievement in Nature.

Kempe started by assuming the opposite of what he wanted to prove: that there is a map that can't be colored with only four colors. He then sought to show that this assumption would ultimately lead to a contradiction — meaning that no such map could exist. In that case, all maps would have to be four-colorable.

First, he said, imagine that the non-four-colorable map from your assumption is as "minimal" as possible: If you were to remove any country from it, the remaining map would be four-colorable. Next, do away with geography and other extraneous details by redrawing your map as what's known as a planar graph. Represent each country as a point (or vertex), and draw a line (or edge) between two points if those countries share a border. Your map-coloring problem is now a graph-coloring one, opening it up to the tools of graph theory.

With planar graphs, Leonard Euler showed that all such graphs will contain at least one vertex with five or fewer neighbors, meaning that all graphs must have at least one of six configurations of vertices, from a single node, a node connected to another node by a single vertex, all the way up to a node connected to five other nodes. (See TFA for a better as well as visual argument).

And because your graph is minimal, if you remove any of these configurations from it, you'll be left with a graph that can be recolored with four colors. Kempe's genius move was to show that no matter which of these configurations you remove, you can always find a way to swap the graph's colors around so that when you add your missing vertex back, it's possible to color all the vertices without needing a fifth color.

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 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.

Kawarabayashi and Thorup, soon joined by Thomassen and Bojan Mohar of Simon Fraser University, wanted to identify an unavoidable set of configurations that could be reduced in parallel, rather than one by one. To do so, they'd have to guarantee that they could reduce each configuration without interfering with the colorings of the other configurations getting reduced at the same time. That would give them a far faster way to recolor a graph with just four colors.

How to find these non-interfering configurations? By searching widely.

[...] The search for configurations in these regions would take two more minds — Kawarabayashi's graduate students, Yuta Inoue and Atsuyuki Miyashita — and months of computing time. "We were pretty naïve," Thorup said. "I don't think we had any clue it would take so long." But eventually they landed on a new unavoidable set. It was massive, consisting of 8,202 configurations. But as they'd hoped, it was possible to reduce many of those configurations at the same time in a given graph, turning what had once been many steps into just a few.

Once again, the four-color theorem had been proved. And the new proof gave a far more efficient coloring algorithm: For a graph with n vertices, it required n(log n) steps, a significant improvement over n².

[...] Meanwhile, the four-color disease lives on. While Thomassen is pleased with his recent result, he still has the same question that has dogged hobbyists and professionals alike for 150 years: Is there a simpler explanation for why four colors suffice for any planar graph? The mythical one-pager, the theoretical flourish that would make everyone go "aha"?

"What I would like is a proof without the use of a computer," Thomassen said. "And I will never stop thinking about that."

arXiv link: arXiv:2603.24880 [math.CO] https://doi.org/10.48550/arXiv.2603.24880 [doi.org]

Original Submission