# Map Coloring

 Colored US map National Atlas
 4-Colored US map Wikipedia US Map

Philip Yasskin took the lead in developing this circle session on Map Coloring for the 2011 Circle on the Road workshop.

Students will get to “color” a map of the United States and a map of their own making. They will prove in one case that something cannot be done and in the other case that something can always be done.

Each group of 3 students are given a large uncolored map of the continental United States and asked to color it using “mancala” stones. 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. Here is an uncolored map of the United States that you can enlarge.

The students are first allowed to use any number of 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 Theorem.) Finally, they are asked if it can be done with just 3 colors. If “Yes”, do it. If “No”, explain why not. The proof is a parity argument. If the students are running out of 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.

Credit goes to Arthur Hobbs from Texas A&M University for developing the United States map coloring activity.

As a second task, students are given a blank sheet of paper and told to draw 4 lines all the way across the paper in any direction, thereby making their own map. They can then color this map and find the smallest number of colors for this map. They will find that the map can be colored with 2 colors (like a checker board). They are then asked to prove any such map can always be colored with 2 colors, no matter how few or how many lines are added as long as each line goes all the way across the page. The proof is an induction on the number of lines, although the technical language of induction need not be used.

One of the benefits of these two activities is that students get to prove that something cannot be done and something can always be done.