Four-Color Map Problem

Date: Tue, 6 Dec 1994 07:18:51 -0500
From: Timothy Gorry
Subject: Four color Map Problem 

Hi. My name is Tim and I'm a student at John W. Dodd,
Jr. High in Freeport, NY and I'm working on a math project.
Other than trial and error is there any scientific or 
mathematical way to solve the Four Color Problem? How about 
even explaining it in layman's terms? Most books I've read are 
written on a *very* high level. Thank's for any help you can 
give me.

Tim G.

Date: Tue, 6 Dec 1994 17:02:08 -0500
From: Dr. Math (Margaret Patterson)
Subject: Re: Four color Map Problem

Hi Tim -

Thanks for writing to us.  The Four Color Problem is one of my favorites 
because it is the first unsolved (it was at the time) problem that I was 
ever introduced to. It is also great because it can be very accessible 
to people at different levels.

The Problem:  Does there exist a 2-D map that cannot be colored by 
using only four colors? I.e. Is there a map that you must have at least 
five colors to color?

To color a map, you must assign each region a color and no two regions 
may have the same color if they share a side (one point doesn't count).  

For example:

        |                                         |                     
  red   |  blue                         red       |  blue
        |                                _________|
________|_________  is OK, but                    |___________ is not
        |                                         |
  blue  |   red                           blue    |   red
        |                                         |

It has been proved that four colors is sufficient for any map. It was
controversial because they used a computer to generate all of the possible 
types of maps and then colored them. Of course they had to prove that 
they had generated _all_ of the possibilites. This is not the usual way of 
proving a theorem. I think that many people would have preferred a proof 
that offered an explanation for  why you only need four colors.
           
Try drawing some maps and coloring them. Can you find some maps for which 
you only need three colors? What happens if you drew the maps on a 3-D object?

I hope this answers your question. Let us know if you have more.

-Margaret, Math Doctor on call

Date: Thu, 8 Dec 1994 22:03:40 -0500
From: Stephen Weimar
Subject: Re: Four color Map Problem

The four-color map theorem was proved by Appel and Haken at the
University of Illinois at Urbana-Champaign in 1976.

For some more info, including references, see

http://www.cs.uu.nl/wais/html/na-dir/sci-math-faq/fourcolour.html   

According to the article, an error was discovered in the original proof 
in 1981. The proof was revised.