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.
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:
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:
Try to be systematic. Start at one edge of the country and work across the country. Or start along the Mississippi and have different kids work east and west.
In the neighborhood of which states are you having trouble? Color that state and then try to color all the states surrounding it. So is that state really a problem? Why or why not? The answer is below the SPOILER ALERT.
Can there ever be a problem with a state on the edge of the country, i.e on one of the oceans or bordering Canada or Mexico.? The answer is below the SPOILER ALERT.
Four Corners is the point in the US where the four states of Utah, Colorado, New Mexico and Arizona meet at a point. Can there ever be a problem with one of the Four Corners states? The answer is below the SPOILER ALERT.
If a state has a problem, what is the property of the surrounding states which leads to the problem? The answer is below the SPOILER ALERT.
!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.
Missouri in US Map
North Dakota in US Map
Utah in US Map
Most states do not have a problem. For example, if you think there is a problem with Missouri, color Missouri - red, then color the surrounding 8 states in order, alternating colors: Arkansas - blue, Tennessee - green, Kentucky - blue, Illinois - green, Iowa - blue, Nebraska - green, Kansas - blue, Oklahoma - green. This shows Missouri is not a problem.
A border state cannot be a problem. For example, if you think there is a problem with North Dakota, color North Dakota - red, then color the surrounding 3 states in order, alternating colors: Montana - blue, South Dakota - green, Minnesota - blue. There is no problem with Minnesota and Montana both being blue because they don't touch. This shows North Dakota (or any border state) is not a problem.
A Four Corners states cannot be a problem. For example, if you think there is a problem with Utah, color Utah - red, then color the surrounding 5 states in order, alternating colors: Colorado - blue, Wyoming - green, Idaho - blue, Nevada - green, Arizona - blue. There is no problem with Colorado and Arizona both being blue because they only touch at a corner, not an edge. This shows Utah (or any Four Corners state) is not a problem. Note: New Mexico is not considered to be a surrounding state because it ony touches Utah at a corner.
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.
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
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
You should find that your map can be colored with just 2 colors (like a checker board).
Why?
Will it always be 2 colors no matter how the 4 lines are drawn?
Will it still be 2 colors if you add more lines?
First state a conjecture.
!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:
Why can't every map be colored with just 2 colors?
Do the lines need to be straight?
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
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
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:
Map Requiring 3 Colors
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.
