Engines of Our Ingenuity

No. 1961:
THE FOUR-COLOR PROBLEM

John H. Lienhard presents guest Andrew Boyd

Today, guest scientist Andrew Boyd colors maps. The University of Houston presents this series about the machines that make our civilization run, and the people whose ingenuity created them.

In 1852, Francis Guthrie found himself trying to color a map of the counties of England. It's very helpful to have a map where every bordering county is a different color, and Guthrie wondered how few colors he could use and still do this. Three colors wouldn't work, but he found he could make do with four. So he wondered, would four colors be enough for any map? Little did he realize that his question would lay its hold on generations of mathematicians.

The seeming simplicity of the four color problem led countless people to try their hand at it over the years, including some of the world's most renowned mathematicians. Hermann Minkowski once told his students the problem remained unsolved because third-rate mathematicians had worked on it, only to admit -- much later -- that, "heaven is angered at my arrogance; my proof is also defective."

The first would-be proof of the result was published in the American Journal of Mathematics in 1879, almost thirty years after Guthrie first posed the problem. One Alfred Bray Kempe, received great acclaim for it. He was made a Fellow of the Royal Society in England and was ultimately knighted.

Eleven years later, Percy John Heawood discovered an error in Kempe's proof. For an incorrect result to be published, much less unchallenged, for such a long time, is very rare, and helps us understand the special difficulties associated with the four color problem.

Unlike many mathematical problems that rely on weaving together a small number of ideas, all the attempted proofs of the four color problem reduce to checking many, many specially constructed maps. Determining which special maps need to be checked and then checking them leaves enormous room for mistakes.

Not until 1976 did Kenneth Appel and Wolfgang Haken develop the first proof of the four color problem that's withstood the test of time. But it wasn't met with open arms. They were able to reduce the number of special maps to something manageable, but still required a computer and 1200 hours of computing time to complete it.

In 1976, the thought of using a computer in a proof was considered outrageous. It evoked heated debate. Scientific American went so far as to publish an article entitled "The Death of Proof." As mathematicians have grown more comfortable with computers, the concern about their use in proofs has subsided. But debate about the proof of the four color problem lingers.

In 1996, four researchers set out to verify the Appel-Haken proof because, in their own words, "as far as we know, no one has yet verified it in its entirety. We have in fact tried to ... but soon gave up." Instead, they developed their own greatly simplified proof. It still relies on a computer, it still requires a mathematician to understand it, and it's certainly possible that there remain even simpler ways to prove what has been elevated from the four-color problem into the four-color theorem.

So the next time you look at a map, ask yourself how you might get away with only three colors. Or how you might convolute the map so it would require five. I think you'll find it really can be hypnotic.

I'm Andy Boyd, at the University of Houston, where we're interested in the way inventive minds work.

(Theme music)


Dr. Andrew Boyd is Chief Scientist and Senior Vice President at PROS, a provider of pricing and revenue optimization solutions. Dr. Boyd received his A.B. with Honors at Oberlin College with majors in Mathematics and Economics in 1981, and his Ph.D. in Operations Research from MIT in 1987. Prior to joining PROS, he enjoyed a successful ten year career as a university professor.

Robin Wilson, Four Colors Suffice, Princeton University Press, Princeton, NJ, 2002.

Two useful web sites on The Four-Color Theorem (all accessed on Dec. 10, 2007):
This is an instructional page.
or see this article by J J O'Connor and E F Robertson.

Play the game: Make your own map and try to beat The Four Color Theorem. (You'll become rich and famous if you do!)


The Engines of Our Ingenuity is Copyright © 1988-2004 by John H. Lienhard.