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 
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 ), 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.
