home *** CD-ROM | disk | FTP | other *** search
/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / sci-math-faq / fourcolour < prev    next >
Encoding:
Internet Message Format  |  2000-02-18  |  3.8 KB
  1. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!news-peer.gip.net!news.gsl.net!gip.net!news.maxwell.syr.edu!sunqbc.risq.qc.ca!News.Dal.Ca!torn!watserv3.uwaterloo.ca!undergrad.math.uwaterloo.ca!neumann.uwaterloo.ca!alopez-o
  2. From: alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz)
  3. Newsgroups: sci.math,news.answers,sci.answers
  4. Subject: sci.math FAQ: The Four Colour Theorem
  5. Followup-To: sci.math
  6. Date: 17 Feb 2000 22:52:04 GMT
  7. Organization: University of Waterloo
  8. Lines: 65
  9. Approved: news-answers-request@MIT.Edu
  10. Expires: Sun, 1 Mar 1998 09:55:55
  11. Message-ID: <88hu2k$qu6$1@watserv3.uwaterloo.ca>
  12. Reply-To: alopez-o@neumann.uwaterloo.ca
  13. NNTP-Posting-Host: daisy.uwaterloo.ca
  14. Summary: Part 17 of 31, New version
  15. Originator: alopez-o@neumann.uwaterloo.ca
  16. Originator: alopez-o@daisy.uwaterloo.ca
  17. Xref: senator-bedfellow.mit.edu sci.math:347398 news.answers:177518 sci.answers:11226
  18.  
  19. Archive-name: sci-math-faq/fourcolour
  20. Last-modified: February 20, 1998
  21. Version: 7.5
  22.  
  23.  
  24.    
  25.                             The Four Colour Theorem
  26.                                        
  27.    Theorem 2 [Four Colour Theorem] Every planar map with regions of
  28.    simple borders can be coloured with 4 colours in such a way that no
  29.    two regions sharing a non-zero length border have the same colour.
  30.    
  31.    An equivalent combinatorial interpretation is
  32.    
  33.    Theorem 3 [Four Colour Theorem] Every loopless planar graph admits a
  34.    vertex-colouring with at most four different colours.
  35.    
  36.    This theorem was proved with the aid of a computer in 1976. The proof
  37.    shows that if aprox. 1,936 basic forms of maps can be coloured with
  38.    four colours, then any given map can be coloured with four colours. A
  39.    computer program coloured these basic forms. So far nobody has been
  40.    able to prove it without using a computer. In principle it is possible
  41.    to emulate the computer proof by hand computations.
  42.    
  43.    The known proofs work by way of contradiction. The basic thrust of the
  44.    proof is to assume that there are counterexamples, thus there must be
  45.    minimal counterexamples in the sense that any subset of the graphic is
  46.    four colourable. Then it is shown that all such minimal
  47.    counterexamples must contain a subgraph from a set basic
  48.    configurations.
  49.    
  50.    But it turns out that any one of those basic counterexamples can be
  51.    replaced by something smaller, while preserving the need for five
  52.    colours, thus contradicting minimality.
  53.    
  54.    The number of basic forms, or configurations has been reduced to 633.
  55.    
  56.    A recent simplification of the Four Colour Theorem proof, by
  57.    Robertson, Sanders, Seymour and Thomas, has removed the cloud of doubt
  58.    hanging over the complex original proof of Appel and Haken.
  59.    
  60.    The programs can now be obtained by ftp and easily checked over for
  61.    correctness. Also the paper part of the proof is easier to verify.
  62.    This new proof, if correct, should dispel all reasonable criticisms of
  63.    the validity of the proof of this theorem.
  64.    
  65.       References
  66.       
  67.    K. Appel and W. Haken. Every planar map is four colorable. Bulletin of
  68.    the American Mathematical Society, vol. 82, 1976 pp.711-712.
  69.    
  70.    K. Appel and W. Haken. Every planar map is four colorable. Illinois
  71.    Journal of Mathematics, vol. 21, 1977, pp. 429-567.
  72.    
  73.    N. Robertson, D. Sanders, P. Seymour, R. Thomas The Four Colour
  74.    Theorem Preprint, February 1994. Available by anonymous ftp from
  75.    ftp.math.gatech.edu, in directory /pub/users/thomas/fcdir/npfc.ps.
  76.    
  77.    The Four Color Theorem: Assault and Conquest T. Saaty and Paul Kainen.
  78.    McGraw-Hill, 1977. Reprinted by Dover Publications 1986.
  79. -- 
  80. Alex Lopez-Ortiz                                         alopez-o@unb.ca
  81. http://www.cs.unb.ca/~alopez-o                       Assistant Professor    
  82. Faculty of Computer Science                  University of New Brunswick
  83.