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.

Additional Exercises (solutions)

COMING SOON!!! (maybe)