The Four-Color Map problem

Date: 11/11/97 at 23:25:27
From: Lisa
Subject: The Four Color Map problem

I just need help on what it is and where I can find information on it. 
I am having trouble finding information on it over the Internet. 
Thanks a lot.

Date: 11/12/97 at 10:00:34
From: Doctor Anthony
Subject: Re: The Four Color Map problem

You can try Eric Weisstein's World of Mathematics, which will then 
refer you to a great deal of literature on the subject.
 
http://mathworld.wolfram.com/Four-ColorTheorem.html   

I have not found a good summary as such on the Web, so will provide a 
brief note on the subject below.

The subject was first raised in 1852 by a part-time mathematician, 
Francis Guthrie, who was colouring in a map of the counties of 
Britain.  He was intrigued by the fact that four colours appeared to 
be sufficient regardless of the complexity of boundary shapes or how 
many regions had a commom border. He passed the problem on to 
University College London to the eminent De Morgan, who in turn passed 
it to the great William Hamilton. Hamilton was unable to invent a map 
which required five colours, but neither could he prove that no such 
map existed. 

Like Fermat's Last Theorem this apparently trivial problem generated a 
great deal of interest and activity. In 1879 a British mathematician, 
Alfred Kempe, published a 'proof' that was accepted by the mathematics 
establishment until in 1890 Percy Heawood of Durham University showed 
that the so-called proof was fundamentally flawed. The search 
continued, and like Fermat's theorem led to great advances in number 
theory, so the four-colour problem gave a stimulus to the new and 
increasingly important topic of topology.

The first breakthrough in the four-colour problem came in 1922, when 
Philip Franklin ignored the general problem and settled for a proof 
which showed that any map containing 25 or fewer regions required only 
four colours. This was extended in 1926 to 27 regions, in 1940 to 35 
regions, and in 1970 to 39 regions. Then in 1976 two mathematicians at 
the University of Illinois, Haken and Appel, came up with a new 
technique which would revolutionise the concept of mathematical proof.

Haken and Appel used the ideas of Heinrich Heesch that the infinity of 
infinitely variable maps could be constructed from a finite number of 
finite maps. They reasoned that by studying these building-block maps 
it would be possible to attack the general problem.

This proved very difficult in practice to achieve, because the number 
of building block configurations could not be reduced below 1482. To 
crank through all the permutations that might occur with this number 
of configurations would take a lifetime. Enter the age of the 
computer. In 1975, after five years of working on the problem, they 
turned to the new number-cruncher and in 1976 after 1200 hours of 
computer time they were able to announce that all 1482 maps had been 
analysed and none of them required more than four colours.

The problem with this type of proof is that only another computer can 
carry out the customary check on its validity. Some mathematicians are 
most reluctant to accept it because no one, however patient, could 
work through the exposition line by line and verify that it is 
correct.  It has been disparagingly referred to as a 'silicon proof'.  
The fact is, however, that mathematicians will increasingly have to 
rely on such methods. The age of the purist of pure logic as the only 
acceptable technique in mathematics has probably passed.

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/