Four Color Theorem

(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.