02/03/2018

Four colors are enough to color any map.

In a scene from Mark Twain's book "Tom Sawyer Abroad," friends Tom and Huck are lost while flying over the United States in a balloon. "We're in Illinois, we haven't seen Indiana yet," Huck insists, explaining, "I know by the color."

"Because of the color?" Tom exclaimed in surprise. "What does the color have to do with it?"

“It all makes sense!” Huck replies. “Indiana is pink and Illinois is green. And down there it’s all green.”

"Indiana is pink?! What nonsense!", Tom exclaimed indignantly.

“Nonsense, sir,” Huck retorted, “I saw it on the map, it is pink!”

In a bad mood, Tom tries to explain that the color on the map doesn't mean anything, but Huck won't be convinced…

The basic rule when coloring a map is that adjacent regions, that is, those that share a common border segment, should be marked with different colors to distinguish them. In 1852, the South African mathematician and botanist Francis Guthrie (1831-1899) was coloring a map of the counties of England and noticed that three colors were not enough, but four colors were. He became curious to know if every map, natural or invented, could be colored with only four colors.

Intrigued, he took the question to the great British logician Augustus De Morgan (1806-1871), who was unable to answer and even believed that there was no mathematical answer: "I am fully convinced that it is not susceptible of demonstration and must be accepted as a postulate."

The problem was popularized by De Morgan and Guthrie, becoming known as the "four-color conjecture".

A few years later, it seemed the matter was going to be settled. In 1879, the British mathematician Alfred Kempe (1849-1922) published a mathematical proof that four colors are indeed sufficient for any map, and the following year, the Scotsman Peter Tait (1831-1901) provided an alternative proof.

However, in 1890, the British economist Percy Heawood (1861-1955) found a serious flaw in Kempe's argument, and the Dane Julius Petersen (1839-1910) did the same with Tait's proof the following year. Back to square one!

Fortunately, Heawood managed to salvage something. He proved that five colors are sufficient to color any map, and this proof is correct. But since no one has been able to produce a map that truly requires all five colors, the situation was very unsatisfactory. Thus, the four-color conjecture remained an intriguing challenge for decades.

In 1905, the German Hermann Minkowski (1864-1909) declared to his students that the problem remained unsolved "only because only third-rate mathematicians were interested in it," adding confidently, "I think I know how to solve it."

But, at the end of the class, he still hadn't succeeded and continued to fail for weeks, until he gave up. "The heavens are angry with my arrogance, my test is also wrong," he confessed.

The situation changed in 1976, when mathematicians Kenneth Appel (1932-2013, American) and Wolfgang Haken (born in Germany in 1928) published the first correct proof of the four-color conjecture.

To read the full text, visit the newspaper's website.

Folha allows each reader access to ten articles per month even without a subscription.