Introduction

Since map makers have made maps, it has been known in the trade that if you plan well enough, you will never need more than four colors to color a map. Map makers are not mathematicians and this belief had never been proven mathematically.

When mathematicians picked up on the thread of the conversation, they began to ask 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?" and

"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 19^th century, it was perceived as interesting but solvable. However, prominent 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 Conquest by Saaty and Kainen:

The great mathematician Herman Minkowski once told his students that the four-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 with my arrogance; my proof is also defective."

In 1976, the conjecture was apparently proved by Wolfgang Haken and Kenneth Appel at the University 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 underway to check the program. So far the only errors that have been found are minor and were easily fixed. Many mathematicians now accept the result as true.

The proof of the four-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?"

We will study some map coloring strategies and its relation to things we have already learned about graphs.