Students will find that there are many different strategies for deciding the best way to color a map. There are also very many ways to approach evaluating whether one way to color a map is "better" than another. In fact, there doesn't seem to be a single best way to approach coloring maps. The idiosyncracies of the map you are coloring will influence how you approach coloring it. There just doesn't seem to be any single way to describe how to approach coloring all maps. This is connected to the idea of computational complexity, a very profound topic in Computer Science.
How do you know that two colors is enough to color this map? How do you know that this map cannot be colored with fewer than four colors? When students articulate their answers to questions like that, they are communicating their reasoning. This is the purpose of mathematical proof. Induction is the proof technique at the foundation of the activity Making a Two-Colorable Map.
