Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

sci.math FAQ: The Four Colour Theorem


[ Usenet FAQs | Web FAQs | Documents | RFC Index | Zip codes ]
Archive-name: sci-math-faq/fourcolour
Last-modified: February 20, 1998
Version: 7.5

See reader questions & answers on this topic! - Help others by sharing your knowledge
                            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 aprox. 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.
-- 
Alex Lopez-Ortiz                                         alopez-o@unb.ca
http://www.cs.unb.ca/~alopez-o                       Assistant Professor	
Faculty of Computer Science                  University of New Brunswick

User Contributions:

Comment about this article, ask questions, or add new information about this topic:


[ Usenet FAQs | Web FAQs | Documents | RFC Index ]

Send corrections/additions to the FAQ Maintainer:
alopez-o@neumann.uwaterloo.ca




Last Update March 27 2014 @ 02:12 PM