Map Coloring: How Many Colors?

The Four-Color Theorem

A Mathematical Challenge

A basic rule for coloring a map is that no two regions that share a boundary can be the same color; otherwise, the map will be hard to read. (It is okay for two regions that only meet at a single point to be colored the same color, however.) If you look at a some maps or an atlas, you can verify that this is how all standard maps are colored.

Mapmakers have long held that any map showing distinctly colored regions—such as countries or states—may be colored using no more than four colors. This belief came about as a matter of practical experience, no mapmaker having encountered a map that actually required five colors. (Of course, for artistic or other reasons, a mapmaker may choose to use more than four colors.)

Unlike mapmakers, mathematicians want to have mathematical proof that a thing is true, so they asked questions. "Are you sure that four colors are enough? How do you know that no one can draw a map that requires five colors? What is it about the way that regions are arranged and touch each other in a map that would make such a thing true?"

For 100 years, mathematicians attempted unsuccessfully to solve what came to be known as the Four-Color Theorem. Finally, in 1976, the theorem was apparently proved by Wolfgang Haken and Kenneth Appel at the Univeristiy of Illinois using a computer program. Since then, other mathematicians have checked the program. So far, only minor errors have been found and have been easily fixed. Many mathematicians now accept the theorem as true.

Fun Map Coloring Activities

3 X 5 Grid Can you color this 3 x 5 grid using only two colors?
Complex Uneven Shapes How many colors do you think you will need to color this map?
Click here to see possible solutions to these coloring challenges.
Mathematics of Map Coloring For in-depth information on the mathematics of map coloring and for more coloring activities, visit MegaMathematics' Map Coloring: The Big Picture

Return to NASAexplores Maps Home