Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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.
```
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search