Students should begin to recognize that they find a variety of strategies for solving problems on their own. They should be trying to articulate those strategies clearly, and finding out that the more they try to do so, the more adept they become. They should also be thinking about where their ideas come from--they might be flashes of insight, the result of careful plodding, things they discovered from listening to or watching others, or ideas that came to them while they were explaining something to someone else.
With all of this to discover, it is certainly not necessary for students to "learn" the best ways to color maps!
It is also not very important for students to understand the idea of induction as presented here, or even accept the proofs that rely on induction in the activities. It is a good idea to use the word induction, simply for the purpose of exposing students to it. What is really important, however, is that students be exposed to the idea that truth is central to mathematics, and how important it is for mathematicians of all ages to think about the methods that they use to find out if something is really true or not. The theme of thinking about how one thinks about problems pervades mathematics.
