The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Four-Color Map Problem: Some History

Date: 12/10/97 at 19:57:56
From: Inoka Perera
Subject: The Four colour Problem

I need a description about the above topic. Could you please help me 
out? Thanks.


Date: 12/11/97 at 05:50:23
From: Doctor Anthony
Subject: Re: The Four colour Problem

The subject was first raised by a part-time mathematician, Francis 
Guthrie, in 1852. He was colouring in a map of the counties of Britain 
and 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 that 
required five colours but neither could he prove that no such map 

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 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 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!   
Associated Topics:
High 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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.