Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School History/Biography
Middle School History/Biography

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search