Map Coloring


Henri Picciotto

These activities are based on lessons I used to teach decades ago in grades 4-5. They are presented here in a form suitable for high school or perhaps middle school.

Download the PDF: Map Coloring / The Two-Color Theorem
Alternate version

Read no further if you want to work through the worksheets yourself!

Teacher Notes

When I shared these with teachers recently, I was told they would work well in a high school discrete math class, as a way to introduce a graph theory unit.

The first activity in the packet introduces the idea of map coloring, and the second leads to the Two-Color Theorem. (Note that the word "line" is used informally, to mean any curve joining one vertex to another. The formal term is "edge".)

One possible statement of the theorem is:

A map is a two-color map if all its vertices are even.

You may prefer to use different terminology, either for consistency with a textbook, or to incorporate vocabulary suggested by your students. In any case, it is essential to define terms so that the theorem makes sense.

A clarifying discussion could include:
- What about vertices on the boundary of the map?
- Does the theorem apply to maps on the whole plane? (as opposed to the finite maps given in the worksheets)
- What can be said about a map created by (infinite, straight) lines?
- What can be said about a map created by drawing only (possibly intersecting) closed curves (e.g. circles, ellipses, polygons, figure eights, etc.)?
- What about combinations of the above two?

These activities can precede or follow a discussion of the Konigsberg Bridge problem. (If you are not familiar with it, a Web search should yield many links.)