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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.