In a message dated 3/13/01 8:09:36 AM EST, [log in to unmask] writes:

>  Anyhow, I seem to have a gazillion posts to read through, but none 
>  from Steve, to which I look forward.

    Ken: I do not want to present myself as an expert on the four color map 
theorem but I will tell you what I know. 

    First of all, as I said yesterday, I was taking a class from Ken Appel in 
1976 when he became somewhat of a celebrity in the math department at the U 
of I by announcing he and a colleague had solved the four color map problem. 
The course I was taking was NOT on topology, but Professor Appel took a class 
period to explain the algorithms he had used.  I had a pretty good memory 
then, but after 25 years I don't remember the details of the math, nor did 
Professor Appel bring in the actual computer code for us to verify.

   The gist of the problem can be easily explained: Draw a square. Then draw 
lines from the middle of each side, dividing the square into four parts 
(where each "part" is what a map-maker would call a "country"). In this 
example , each of the parts is itself a square. How many different colors 
would you need to make sure that no two parts ("countries") had the same 
color (and thus would run into each other, ruining the map). Obviously four, 
right? OK. So let's color the upper right part red, the upper left part blue, 
the lower left part green, and the lower right part yellow. So far, so good.

   Now start again with an uncolored version of the original square, and 
divide it again into four parts like you just did. Only now, draw a small 
circle in the middle of the square, making a fifth "country". Each of the 
parts look almost the same as before, except the four outer parts are not 
squares anymore (they are "squares minus a small arc"), and the fifth part is 
a small circle.  Now how many colors do you need? Well, one answer is five, 
that is, each of the parts from before are the same color (red, blue, green 
and yellow), and then we'll color the small circle orange. That works. But 
here's another solution. Make the upper left part red, the upper right part 
blue, the lower right part red, the lower left part blue, and make the circle 
green. That ALSO works, right? We solved it with only THREE colors, even 
though we had FIVE "countries" this time instead of FOUR.  So the number of 
required colors to make a map of all "distinct-color countries" is not the 
same as the number of countries, nor is the required number obvious.

   What map makers noticed is that no matter how the countries were shaped 
(such as the states in the continental US or the countries of Europe), they 
could always find a way to show each country in a color that did not run into 
another country using only four colors. It sounds impossible, but Tom Gray 
posted a URL showing a map of the US drawn this way using four colors (at 
http://www.math.gatech.edu/~thomas/FC/fourcolor.html.) . A map maker asked a 
mathematician friend if it was true that ANY map drawn in a plane could 
ALWAYS be made using only four colors, no matter WHAT the shape of each 
individual country was. That's when the "design" problem became a "math" 
problem. The problem was abstracted to read something like this:

    Take any closed curve in a plane. Divide the closed curve into regions of 
any arbitrary shape. Show that only four colors are needed to color in each 
region such that no two adjacent regions have the same color.

   Now it's not a "map design" problem. It's a topology (i.e., math) problem.

   The mathematicians approached the problem by considering how a closed 
curve could be subdivided into regions. They realized that certain patterns 
emerged (such as "the next subdivision creates one extra region that shares a 
common boarder with at most four other regions", "the next subdivision 
creates one extra region that shares a common boarder with at most one other 
region", etc). They reduced each of these cases to graphs connected by nodes. 
They showed that every single case was just a variation of a certain set of 
interconnected nodes. In 1976 it was believed that there were 1476 different 
patterns, and recently it has been shown that many of those cases can be 
recast into other cases, so that there are actually under 700 unique possible 
patterns.

   Each of the interconnected node patterns leads to complex graphs that must 
be separately considered. That's where the computer comes in. Appel 
programmed the computer to "color in" each of the cases of possible graphs. 
To give you an idea as to the complexity of the calculations, it took him 
1200 hours of computer time to compute the answer for each of the 1476 cases 
he had found, about an hour of computer time per case. In 1976, even a 
microprocessor  was running at over 2,000,000 instructions per second. So 
assuming they used nothing more than a lowly microprocessor, it took (at 
least) 7,200,000,000 operations to verify each of the 1476 node cases, for a 
total of (at least) 10,627,200,000,000 operations to check everything. That's 
a gazillion operations.

   If you want more details, Tom Gray's cited paper looks pretty good.

-- Steve --