Map Coloring

Arthur Hobbs & Philip B. Yasskin

Department of Mathematics
Texas A&M University
yasskin@math.tamu.edu

2015

This is the student version of this article.

Introduction

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.

Credits

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
You will be 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 you 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 you get to name the states without having the names on the map.)



Initially you can use any number of colors. (You should have 8 colors.) However, can you use fewer? What is the smallest number you can use?





!SPOILER ALERT! #1

Pause your reading if you want to figure out for yourself what is the smallest number of colors needed to color the US map.

You should easily be able to color the US map using 4 colors. In fact there is a famous theorem, called the Four Color Map Theorem, saying this is guaranteed to be possible:

    The Four Color Map Theorem:

4-Colored US Map
4-Colored US Map
Wikipedia US Map
    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.

However, some maps can be colored with fewer than 4 colors. For example, a checker board can be colored with only 2 colors. So can the US map be colored with 3 colors? If "Yes", do it. If "No", explain why not. The answer is below the next SPOILER ALERT.

As you attempt to color the US map with just 3 colors, here are several suggestions:

!SPOILER ALERT! #2

Pause your reading if you want to figure out for yourself if the US map can be colored with 3 colors.

Here are the answers to some of the questions listed above. There are several states which do have a problem. Can you find them?

!SPOILER ALERT! #3

Pause your reading if you want to figure out for yourself which states are a problem when you try to color the US map with 3 colors.

    Problem US Map
    Nevada in US Map
  • There are 3 states which do cause a problem: Nevada, Kentucky and West Virginia. For example, consider Nevada: Color Nevada - red. Then color the surrounding 5 states in order, alternating colors: California - blue, Arizona - green, Utah - blue, Idaho - green, Oregon - blue. There is a problem, because Oregon and California are both blue and they touch on an edge. No matter where you start coloring the surrounding states, the first and last will be the same color. This shows Nevada is a problem. The same thing happens with Kentucky and West Virginia.

So what is the property of Nevada, Kentucky and West Virginia that causes the problem? Or more correctly, what is the property of the surrounding states which causes the problem?
HINT: Count the number of surrounding states for Nevada, Kentucky and West Virginia as well as some interior states with no problem, like Missouri or Oklahoma.

!SPOILER ALERT! #4

This is your last chance to figure out for yourself why the US map cannot be colored with 3 colors.
  • The number of surrounding states is: Nevada - 5, Kentucky - 7 (be careful), West Virginia - 5, Missouri - 8 and Oklahoma - 6. What is the property of the numbers 5 and 7 which is different from 6 and 8 which leads to the problem? Answer: The states with a problem are surrounded by an odd number of other states. Thus if you color the center state red and the surrounding stated alternately blue and green, then two of the surrounding states which are adjacent will end up with the same color.
One final point you should notice:
  • Just because we have shown that if there is a state surrounded by an odd number of states then that state and its neighborhood cannot be colored by 3 colors, it does not mean that if all states were surrounded by an even number of states then the whole US could be colored by 3 colors. It only means we have not yet found an obstruction. That is why the Four Color Map Theorem was so hard to prove.



Part 2: Color Your Own Map

Uncolored 4 Line Map
Uncolored 4 Line Map
After you finish with the US map, get a blank piece of paper, a ruler and a pencil and draw 4 lines all the way across the paper at any angles, making your own map. What is the fewest number of colors that can color this map?

!SPOILER ALERT! #5

Postpone reading this section until you try to find the minimum yourself.

2-Colored 4 Line Map
2-Colored 4 Line Map
You should find that your map can be colored with just 2 colors (like a checker board).

!SPOILER ALERT! #6

State your conjecture before continuing.

A reasonable conjecture would be:

    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.

!SPOILER ALERT! #7

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


HINT: Start with one line and add one line at a time to see what changes. This method of proof is called "mathematical induction" but you don't need to use that terminology.


Here are the steps of an induction proof.
    Colored 1 Line Map Colored 2 Line Map
    Colored 1 Line Map     Colored 2 Line Map
  • If you draw 1 line on the page, you color one side red and one side blue.


  • If you draw 2 lines on the page which cross, you color the 4 regions clockwise red, blue, red, blue.
    If they don't cross, there are 3 regions colored red, blue, red.


  • Colored k Line Map Add (k+1)-st Line
    Colored k Line Map     Add (k+1)-st Line    
    Flip Colors Below Line
    Flip Colors Below (k+1)-st Line
  • If you have already drawn k lines and colored the map with just 2 colors, what happens when you add the (k+1)-st line?


    On each side of the new line everything is still properly colored with just 2 colors, but along the new line everything is wrong. Whenever the new line pass through a region, it splits it into 2 regions which now have the same color on both sides of this new edge.


    However, if you flip the color of ALL the regions on ONE side of the new line, then everything is still properly colored on each side of the new line, but now everything is also properly colored across the new line!


  • If you continue in this manner: adding new lines and flipping all colors on one side of the new line, you will be able use just 2 colors to color a map made with any number of lines.

  • Notice that there was no mention of the word "induction" anywhere in this proof, no definition of an abstract statement P(n) with an initiallization step P(1) and an induction step P(k) ⇒ P(k+1). However, if you would like to learn more about "Proof by Induction", see the Wikipedia article on Mathematical Induction.
And here are the answers to the final two questions:
    3 Colors Required
    Map Requiring 3 Colors
    Map with Curves
    Map with Curves
  • Why can't every map be colored with just 2 colors?
    Because we require every line to be drawn all the way across the page. If we allowed a line to stop in the middle of the paper with its end on some other line, then you would need 3 colors to color the regions surrounding that endpoint.



  • Do the lines need to be straight?
    No, as long as the wiggly lines go all the way across the page, it still splits the page into two parts and we can flip the colors of all regions on one side.




Summary

Notice that while looking at the US map you proved that it cannot be colored by just 3 colors, but while looking at your own map you proved 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