(See also: The Mathematics Behind the Maps, The Most Colorful Math of All, and The Story of the Young Map Colorer.)

The Four Color Problem was famous and unsolved for many years. Has it been
solved? What do you think?

## The story of the problem

Since the time that mapmakers began making maps that show distinct regions
(such as countries or states), it has been known among those in that trade,
that if you plan well enough, you will never need more than four colors to
color the maps that you make.
The basic rule for coloring a map is that no two regions that share a
boundary can be the same color. (The map would look ambiguous from a
distance.) It is okay for two regions that only meet at a single point to
be colored the same color, however. If you look at a some maps or an
atlas, you can verify that this is how all familiar maps are colored.

Mapmakers are not mathematicians, so the assertion that only four colors
would be necessary for all maps gained acceptance in the map-making community over the years because no
one ever stumbled upon a map that required the use of five colors.
When mathematicians picked up the thread of the conversation, they began by asking questions like: Are you
sure that four colors are enough? How do you know that no one can draw a
map that requires five colors? What is it about the way that regions are
arranged and touch each other in a map that would make such a thing true?

When the question came to the European mathematics community at the end of
the 19th century, it was perceived as interesting but solvable.
Prominent and experienced mathematicians who tackled the problem were
surprised by their inability to solve it. Take for example, this account from *The Four Color Problem: Assaults and Conquesst* by Saaty and Kainen:

The great mathematician, Herman Minkowski, once told his students that the
4-Color Conjecture had not been settled because only third-rate
mathematicians had concerned themselves with it. "I believe I can prove
it," he declared. After a long period, he admitted, "Heaven is angered
by my arrogance; my proof is also defective."
(Saaty & Kainen , 1986,p.8)

## A Special Role for the Computer

In 1976, the conjecture was apparently proved by Wolfgang Haken and Kenneth
Appel at the Univeristiy of Illinois with the aid of a computer. The
program that they wrote was thousands of lines long and took over 1200
hours to run. Since that time, a collective effort by interested
mathematicians has been under way to check the program. So far the only
errors that have been found are minor and were easily fixed. Many
mathematicians accept the theorem as true.
The proof of the 4-Color-Theorem is a doorway to some interesting
questions about the role of human minds and computing machines in
mathematics. Is it ``fair'' to accept as true what a computer can verify,
even though no single person can? Does the nature or texture of what
humans can discover about their world change with the use of computers as
thinking tools? Computers are huge and powerful, but finite; will using
them as thinking tools be ultimately limiting? These issues are raised and
considered in *Ad Infinitum: The Ghost in Turing's Machine* by Brian Rotman, and *Pi in the Sky* by John Barrow.