## Penn Alexander math club: map coloring

Today in math club I had the students explore map coloring. I tried to leave it as open-ended as possible to start—I just said that we were going to draw maps with countries, and try to give each country a color, so that no two adjacent countries have the same color. I was careful not to specify what a “country” is, or what it means for two countries to be “next to” each other!

Pretty much on their own, they figured out how to draw a map with four countries all touching each other, which therefore required four colors. When I challenged them to draw a map with five countries all touching each other, they came up with maps involving countries touching at a corner, and with “satellite” disconnected regions that had to be given the same color as the “mother country”. They also figured out that if we allow these things, we can draw maps requiring an arbitrary number of colors, and conjectured that without these things we can’t have five countries all touching each other. I then told them about the four-color theorem and we had fun trying to four-color a map of North America (including the US states).

Then I showed them how to interpret maps as graphs, why maps correspond to planar graphs, and how to turn the map-coloring question into a graph-coloring question. I showed them the complete graph on 5 vertices and how it would correspond to having five countries all touching each other. Then for fun I posed the three utilities problem, which after playing with for a while, they correctly guessed could not be solved within the given constraints. One student did come up with an ingenious solution involving a pair of “teleporters”, which (although I didn’t point this out to them at the time) corresponds to the fact that $K_{3,3}$ can be embedded on a torus! I then showed them how to interpret this also as a statement about graphs (specifically, the non-planarity of $K_{3,3}$), and then told them Kuratowski’s Theorem (which I still find rather amazing and magical).

To finish up, I had them explore the idea of dividing up a continent into countries only by drawing straight lines that went completely from one side of the continent to the other. They correctly figured out that such maps would always be two-colorable. We looked at some examples and their corresponding graphs (which, they noted, always consist of a bunch of quadrilaterals). When I showed them the inductive proof of two-colorability, one of the students noted that the proof generalized to non-straight boundaries, as long as the boundaries are drawn as continuous lines with both endpoints on the “coastline” of the continent (which I hadn’t realized)!

All in all, this was probably our most fun and engaging meeting yet! Now that the Mathcounts competition is over, I think we’ll have a lot of fun doing some more open-ended, exploratory things like this rather than practicing with problem sets.

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in geometry, pattern, puzzles, teaching and tagged , , , . Bookmark the permalink.

### 4 Responses to Penn Alexander math club: map coloring

1. Denise says:

“…one of the students noted that the proof generalized to non-straight boundaries, as long as the boundaries are drawn as continuous lines with both endpoints on the “coastline” of the continent…”

AND as long as the lines always cross in a single point (or one point at a time, if they wiggle back and forth). If the lines are allowed to run along each other for any section of the boundary, that will mess up your two-coloring system.

[From experience: the two-coloring of closed squiggles is one of my favorite mindless doodles, but one has to be careful in drawing the initial squiggle or the pattern will break down.]

2. Brent says:

Ah, good point Denise! At first I thought you also had to make sure that no more than two lines cross at a single point, but then I realized that’s actually OK.

3. Jonathan says:

Math is more fun when you can do it with kids…

All sorts of credit for pointing them in the right direction, and then allowing them to explore… Sounds like they enjoyed themselves (too!)

4. stefanutti says:

Hi Brent. I was looking for people interested in the four color theorem and I found your blog. Beautiful and interesting.

I was also playing with the four color theorem, trying to approach to it without using graph theory … or at least not switching to it from the beginning.

If you want, these is my blog:

http://4coloring.wordpress.com/

Bye, Mario