Map Coloring

Arthur Hobbs & Philip B. Yasskin

Department of Mathematics
Texas A&M University


This is the instuctor version of this article. For the student version, click here: MapColoring-Students.html


A map is properly colored if every pair of countries (or states), which have a common edge, have different colors. This Map Coloring activity allows students to use map coloring once to prove something never happens and once to prove something always happens. It also introduces them to the Four Color Map Theorem.


Art Hobbs designed the Color the US Map activity for use in Texas A&M Summer Educational Enrichment in Math (SEE-Math) program in 2003. Phil Yasskin added the Color Your Own Map acvtivity for SEE-Math in 2007.

Part 1: Color the US Map

Uncolored US Map
Uncolored US Map
Nations Online Project
6-Colored US Map
6-Colored US Map
National Atlas
4-Colored US Map
4-Colored US Map
Wikipedia US Map
Each group of 2-4 students are given a large uncolored map of the continental United Stated and asked to color it using "mancala" stones. (You can also use squares of colored paper.) Two states must have different colors if they touch along an edge; although they may have the same color if they touch only at a vertex (like Utah and New Mexico). Here is an uncolored map of the United States that you can enlarge. If the students are short on time, the map can be cut down to just west or east of the Mississippi. Here is a small map of the Western half of the US. (By the way this is a great Geography lesson as well, since the students get to name the states without having the names on the map.)

The students are first allowed to use any number of colors. (I give them 8 colors.) Then they are asked if they can use fewer and "What is the smallest number you can use?" The students quickly work it down to 4 colors. (Then they are told about the Four Color Map Theorem.)

    The Four Color Map Theorem:

    Every map in the Euclidean Plane can be colored with at most four colors.

This theorem was first conjectured in 1852 by Francis Guthrie and finally proven in 1976 by Kenneth Appel and Wolfgang Haken using computers. See the Wikipedia article on the Four Color Theorem.

Finally, the students are asked if the US map can be colored with just 3 colors. If "Yes", do it. If "No", explain why not.
Answer: It cannot be colored by 3 colors. But you don't want to just tell the students it cannot be done. You want the students to try to do it and in the process discover why it cannot be done. Try to ask leading questions and answer a question with a question. For this Socratic discussion, it is best to have a counselor working with each group of 2-4 students. Things a counselor might say include:


Stop reading this section if you want to figure out for yourself why the US cannot be colored with just 3 colors. Pick up again at Part 2: Color Your Own Map.

Here are the answers to the questions listed above, although not in the same order. One final point you should try to make with the students:

Part 2: Color Your Own Map

Uncolored 4 Line Map
Uncolored 4 Line Map
2-Colored 4 Line Map
2-Colored 4 Line Map
After the students finish the US map, they can be given a blank piece of paper, a ruler and a pencil and told to draw 4 lines all the way across the paper at any angles, making their own map. They are asked "What is the fewest number of colors that can color this map?" The students soon answer 2 colors (as on a checker board), but then you ask the students to explain why. Will it always be 2 colors no matter how the lines are drawn? Will it still be 2 colors if you add more lines? Try to get the students to state the conjecture:

    The Complete Line Map Theorem:

    If any number of lines are drawn all the way across a paper thereby producing a map, then that map may be colored with just 2 colors.

The proof follows the SPOILER ALERT.

Two more questions then arise:

Again the answers follow the SPOILER ALERT.


Postpone reading this section if you want to think about your own proof. First there is a hint about the method of proof.

HINT: The proof is best done using mathematical induction on the number of lines, but we don't necessarily use that terminology. Try to get the students to come up with the proof below by asking them to add one line at a time and see what changes.

Here are the steps of an induction proof. And here are the answers to the final two questions:


Notice that while looking at the US map the students prove that it cannot be colored by just 3 colors, but while looking at their own map they prove it can always be colored by 2 colors. One is a proof that something can never be done and the other is a proof that something can always be done.

Have fun.
Phil and Art

Last Updated: April 23, 2015, PBY
Copyright © 2005-15 Philip B. Yasskin