Drexel dragonThe Math ForumDonate to the Math Forum

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

Four-Color Theorem - sci-math faq


Date: 8/21/96 at 7:2:31
From: Satyadeepcp
Subject: Four-Colour Theorem

Do we need more than 4 colors to color a 2-dimensional map?


Date: 8/27/96 at 20:40:27
From: Doctor Jodi
Subject: Re: Four-Colour Theorem

Here's an answer to your question from the sci-math faq
(http://daisy.uwaterloo.ca/~alopez-o/math-faq/math-faq.html   )

Enjoy!

The Four Colour Theorem

Theorem 2 [Four Colour Theorem] Every planar map with regions of 
simple borders can be coloured with 4 colours in such a way that no 
two regions sharing a non-zero length border have the same colour. 

An equivalent combinatorial interpretation is 

Theorem 3 [Four Colour Theorem] Every loopless planar graph admits a
vertex-colouring with at most four different colours. 

This theorem was proved with the aid of a computer in 1976. The proof 
shows that if approx. 1,936 basic forms of maps can be coloured with 
four colours, then any given map can be coloured with four colours. A 
computer program coloured these basic forms. So far nobody has been 
able to prove it without using a computer. In principle it is possible 
to emulate the computer proof by hand computations. 

The known proofs work by way of contradiction. The basic thrust of the 
proof is to assume that there are counterexamples, thus there must be 
minimal counterexamples in the sense that any subset of the graphic is 
four colourable. Then it is shown that all such minimal 
counterexamples must contain a subgraph from a set basic 
configurations. 

But it turns out that any one of those basic counterexamples can be 
replaced by something smaller, while preserving the need for five 
colours, thus contradicting minimality. 

The number of basic forms, or configurations has been reduced to 633. 

A recent simplification of the Four Colour Theorem proof, by 
Robertson, Sanders, Seymour and Thomas, has removed the cloud of doubt 
hanging over the complex original proof of Appel and Haken. 

The programs can now be obtained by ftp and easily checked over for 
correctness. Also the paper part of the proof is easier to verify. 
This new proof, if correct, should dispel all reasonable criticisms of 
the validity of the proof of this theorem. 

References:

K. Appel and W. Haken. Every planar map is four colorable. Bulletin of          
the American Mathematical Society, vol. 82, 1976 pp.711-712. 

K. Appel and W. Haken. Every planar map is four colorable. Illinois     
Journal of Mathematics, vol. 21, 1977, pp. 429-567. 

N. Robertson, D. Sanders, P. Seymour, R. Thomas The Four Colour 
Theorem Preprint, February 1994. Available by anonymous ftp from 
ftp.math.gatech.edu, in directory /pub/users/thomas/fcdir/npfc.ps. 

The Four Color Theorem: Assault and Conquest, T. Saaty and Paul 
Kainen. McGraw-Hill, 1977. Reprinted by Dover Publications 1986. 

-Doctor Jodi,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Discrete Mathematics

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-2013 The Math Forum
http://mathforum.org/dr.math/