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