Four-Color Theorem

Date: 4/13/96 at 3:36:38
From: Roger Williams
Subject: Four-coloring the plane

Dear Dr. Math,

Say you make (for instance) a map, and you wish to color in each 
"country" or "space" on the map in such a way that no two 
contiguous contries or spaces have the same color. What is the 
minimum number of colors you can use?

It seems that the minimum number of colors is always four.

Has anyone proved this?  If so, what is the proof?  If not, what work 
has been done on this and where can I find out about it?

If you are coloring in a three-dimensional space, there is no limit to 
the number of colors you may have to use. Is this right?

Hope you enjoy this question, even if it is very simple.

Yours,
              Roger

Date: 4/14/96 at 0:47:55
From: Doctor Patrick
Subject: re: Four-coloring the plane

Hi Roger!  

Actully, four colors are the MOST that you will need in order to 
correctly color a map.  In fact, in some cases you can color the 
map with only two colors.  For example, if you make a map by 
drawing a closed loop without lifting your pen from the page, you 
should be able to color it with only two colors. This will work 
even if you draw multiple loops on top of the first one.

As for proof, map makers have used this principle for a very long 
time, but until 1976 there was no real proof for it. Since then it 
has been proven using a computer and mathematicians are working to 
check the program used in the proof. You can find out more about 
it at another cool web site called MegaMath. Its address is 

http://www.c3.lanl.gov/mega-math/    

Look under "The most colorful math of all".  It has a lot of great 
information and backround on map coloring, and other areas of 
geometry.  There is also a more detailed description at 

http://www.math.gatech.edu/~thomas/FC/fourcolor.html   

I'm not sure what to tell you about three-dimensional space.  The 
four color theorem is only for 2D maps.  I wasn't able to find any 
references that dealt with maps in 3D space, but maybe some of the 
above sites can give you some more ideas of where to look.

Hope this helps,

-Doctor Patrick,  The Math Forum