This is the instuctor version of this article. For the student version, click here:
MapColoring-Students.html
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.
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:
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! #1
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.
Missouri in US Map
North Dakota in US Map
Utah in US Map
Nevada in US Map
Most states do not have a problem. For example, if a student thinks there is a problem with Missouri, have the student 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 a student thinks there is a problem with North Dakota, have the student 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 a student thinks there is a problem with Utah, have the student 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 3 states which do cause a problem: Nevada, Kentucky and West Virginia. For example, if a student thinks there is a problem with Nevada but doesn't quite know why, have the student 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.
Ask the students why Nevada, Kentucky and West Virginia are problems but Missouri is not. As a leading question, ask: How many states they are surrounded by? Nevada - 5, Kentucky - 7 (be careful), West Virginia - 5, and Missouri - 8. What is the property of the numbers 5 and 7 which is different from 8 which leads to the problem. Hopefully, you can get the student to say it is because they are odd. Hopefully, you can get the student to recognize that if there is any state which is surrounded by an odd number of states then that state and its neighborhood cannot be colored by 3 colors.
One final point you should try to make with the students:
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
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:
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! #2
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.
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 to color a map made with any number of lines with just 2 colors.
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). At this age, the students do not need that level of abstraction. However, at the end you can and should tell them that this type of proof (doing it in steps) is called "Proof by 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 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.
