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.