- Rule of thumb: four colors are all you need to distinguish the countries on any map.
- But why? It's a simple question with a difficult answer, eluding scientists for a century.
- In the end, the four-color problem was the first theorem that was cracked by a computer.
Graffiti in Örs Vezér Square in Budapest by Hungary's Two-Tailed Dog Party, illustrating the four-color theorem. Credit: Szilas via public domain
Four colors: that is all you need for giving each country on a map a color distinct from all its neighbors. Perhaps for centuries, that has been a rule of thumb among cartographers. But halfway through the 19th century, people started wondering: Does that rule have some grounding in logic or reason?
A 19th century scramble
On 10 June 1854, an anonymous contributor only identified as F.G. wrote in The Athenaeum:
"In tinting maps, it is desirable for the sake of distinctiveness to use as few colours as possible, and at the same time no two coterminous divisions ought to be tinted the same. Now, I have found by experience that four colours are necessary and sufficient for this purpose — but I cannot prove that this is the case (…) I should like to see (or know where I can find) a general proof of this apparently simple proposition, which I am surprised never to have met with in any mathematical work."
That may have been the starting point for a good old 19th century scramble, in this case toward a four-color theorem — in other words, definite mathematical proof that four colors is sufficient to distinctively mark all countries on any map.
That theorem really ties the room together.Credit: Inductiveload via CC BY-SA 3.0
The late 19th century was an era of major scientific breakthroughs with huge societal consequences. To name but three: electricity, telephony, and photography. Yet even in that practical age, some scientists found time for this rather more esoteric topic.
On the face of it, the quest for the four-color theorem does not even sound like much of a scientific challenge, especially for mathematicians. But appearances are deceptive: some math problems are easier explained than solved. For a similar one, see Euler's perplexing Seven Bridges Problem (Strange Maps #536).
In 1879, Alfred B. Kempe published an article "On the Geographical Problem of the Four Colours" in the American Journal of Mathematics, in which he confidently stated:
"the experience of the map-makers has not deceived them, the maps they had to deal with, viz: those drawn on simply connected surfaces, can, in every case, be painted with four colours."
Kempe then developed a mathematical proof several pages long.
Weak link in the Kempe chain
Illustrative addendum to Kempe's article. Unfortunately, the journal was printed in black and white only, so the colors had to be named rather than applied. Credit: American Journal of Mathematics, Vol. 2, No. 3 (Sep 1879), via JSTOR / public domain
Proof delivered, theorem established? Not so fast. As mentioned above, the four-color theorem states that only four colors are needed to ensure adjacent regions have different colors — the point being to make sure that each is distinguishable from the other. But this means that there are a whole raft of special cases: for instance, enclaves and exclaves or where multiple regions touch at a single point (as in Fig. 6 on Kempe's illustration above).
As those examples show, where map theory meets map practice, things will get complicated. That is why, to prove his point, Kempe had to develop so-called "Kempe chains," logical tools that helped him analyze various possible map configurations. Unfortunately, Kempe made a mistake in building his tools, and it took longer than a decade to catch a particularly well hidden one.
Percy J. Heawood (1861-1955, nickname "Pussy") was a British mathematician who spent most of his life working on the four-color theorem. In 1890, writing in the Quarterly Journal of Pure and Applied Mathematics, he exposed the flaw in Kempe's proof. To remedy and salvage the original theory, he proposed a five-color theorem instead.
For almost a century, the four-color theorem was dead. It had been downgraded to a four-color conjecture, lingering in a kind of cartographic limbo between the everyday evidence that four colors do indeed suffice and the scientific inability to explain exactly why this is so.
A whole new branch of math
Over the decades, countless papers and articles were devoted to the four-color problem. It even proved instrumental in developing graph theory, a whole new branch of mathematics.
Five countries, four colors — and the graph structure underpinning the color scheme.Credit: GrandEscogriffe via CC BY-SA 4
The problem proved so popular that, in 1887, it was published as a "challenge" in the Journal of Education, attracting a host of replies, one penned by the Bishop of London. In 1980, Edward R. Swart published an article on "The philosophical implications of the four-color problem," proposing a new mathematical entity halfway between a conjecture and a theorem.
Even though Kempe's proof had been flawed, in the long run it turned out he had been right. However, he himself did not live long enough to see his name cleared. In 1976, Kenneth Appel and Wolfgang Haken, two researchers at the University of Illinois, published Every Planar Map is Four Colorable, in which they unveiled the final proof that four colors are enough to distinguish between all regions on a map.
Appel and Haken were one of several teams racing to find that proof using the raw calculating power of a computer, which was of course unavailable to either Kempe or Heawood. In fact, the four-color theorem was the very first theorem proved by a computer.
It took Appel and Haken a 742-page book to fully make their point. "One can never rule out the chance that a short proof of the Four-Color Theorem might some day be found, perhaps by the proverbial bright high-school student," they say in the introduction. "But it is also conceivable that no such proof is possible."
Still in search of an "elegant" proof
Just four colors are enough to clearly distinguish these countries in Central Europe. The topological diagram on the right shows how.Credit: Maths Is Fun
In fact, simpler proofs have been published — in 1997 and 2005 — but in both cases still relying on computers. Incidentally, these proofs do not convince everybody. Some people are still looking for the anti-Holy Grail: evidence that the four-color theorem is bogus.
For any proverbially bright high school student out there tickled by the four-color theorem, there is still plenty of glory to be had in devising a simple, elegant proof that fits on the back of an envelope. Or, barring that, by explaining the theorem's one enduring mystery, as summarized in The Mathematical Coloring Book: "Why four? was a great question. Even today (…) we still do not really know the answer to this innocent question."
Ironically, the search for the four-color theorem has proved more valuable and useful for mathematics and computing than for cartography itself. Mapmakers do not need to rely on theorems to color their maps. Rules of thumb tend to work just fine.
For more on this topic, see also The Four-Color Theorem on Cantors Paradise, a math periodical by Medium, and this article on Massive Science.
Strange Maps #1101
Got a strange map? Let me know at strangemaps@gmail.com.
Follow Strange Maps on Twitter and Facebook.
0 comments:
Post a Comment