Map Coloring Worksheet: Key

ACTIVITY 1
There are many ways to do this but it can be done correctly with 4 colors--but not fewer.

ACTIVITY 2
The goal of a map coloring problem is to color a map so that regions sharing a common border have different colors. (Regions that meet only in a point may share a common color.)
In the language of mathematics, we are assuming that each region is a closed curve. Simply put, this means that for a region it is not possible to move from inside the region to outside the region without crossing the border of the region and it is always possible to move from a point within a region to any other point within the region without crossing the border of the region. The chromatic number of a map is the mimimum number of colors required to color that map.

Brook's Theorem
If v is the largest degree (or valence) of any vertex in a connected graph, G, AND G is not a complete graph nor a circuit of odd length, then the chromatic number of G is less than or equal to v.

There are many correct ways of coloring both maps but, the S.E. Missouri map has a chromatic number of 4 while the S.E. United States map has a chromatic number of 3.

ACTIVITY 3
Brook's Theorem assures us that we can color the first graph with 3 or fewer colors. It turns out that you do need three colors to color this graph.
For the second map (the pie chart with 7 sectors), you need 3 colors. In general, any pie chart with an even number of sectors can be colored with 2 colors while any pie chart with an odd number of sectors (but more than one) requires 3 colors.

ACTIVITY 4
Your graphs are correct if the region representing each state was transformed into a vertex and any two vertices are connected by an edge if and only if they share a border. The chromatic number of each graph is 3.

ACTIVITY 5
There are many correct answers. One answer is AREA 1: Eagle, Panda; AREA 2: Rhino, Elephant, Tiger; AREA 3: Giraffe, Zebra, Oryx. Your answer is correct if you have animals in exactly 3 areas and no two animals in the same area are represented in the graph by vertices joined by an edge.

ACTIVITY 6
There are many correct answers. Your graph is correct if each of the 10 species was transformed into a vertex and any two vertices are connected by an edge if and only if the two species are incompatible (there is an X in the appropriate table cell).

Brook's Theorem guarantees that you will need 6 or fewer tanks
(Of course, the Four Color Theorem guarantees that we actually need no more than 4.)
In fact, this situation does require 4 tanks. One posible solution is Tank A: species 1, 6, 10; Tank B: species 2, 5, 7; Tank C: species 3, 8; Tank D: species 4, 9. There are many other correct solutions.