Making a Two-Colorable Map

Description

Materials

Instructions

Ideas for discussion

Materials

• Pencil, paper and coloring tools
• String
• Two or more colors of marking pieces, such as unifix cubes or poker chips

Instructions

1. Have students draw a map by putting their pencil down on a clean sheet of paper and drawing a long curving line that goes anywhere on the page. The pencil cannot stop or be lifted off the page until it meets the point at which it started. The pencil line can cross itself any number of times and at any point.

2. Tell the students that it has been said that any map that is drawn this way can be colored with two colors. Ask them if they think this is true, and list their reasons why and why not.

3. Have the students work together and experiment with coloring the maps that they have made. They should all be two-colorable. If they find one that is not, check it together very carefully to see that it has been made properly. Be sure that students understand that drawing a map that is so complex it is hard to verify whether it can be two-colored or not is not the same as drawing a map that cannot be two-colored.

4. Using a large loop of string draw the maps in the picture below and color them.

   

   (The first map is a plain loop, the second one is a loop with a twist in it, etc. Instead of coloring the regions, you can use colored marking pieces to mark the colors that you would use.)

   Discuss what happens at each step and why the map remains two colorable. It is a good idea to write this down.

   Try to twist and cross the loop of string so that the resulting "map" will not be two-colorable. What is the relationship between the loop of string and the way that the students drew the maps on their paper?

5. Do the same thing using two loops of string, and allow the loops to overlap in any way that you like.

   .

   You can't make a map that isn't two colorable! (But why?)

   NOTE: It is important for students to think about these questions, to manipulate the string, and look for a relationship between the string and the maps that they drew. It is not important that the students become convinced that this technique will always produce a two-colorable map. (in fact, a student who can articulate clearly what is occurring here has reason to rejoice!)

Discussion

1. Invite the students to talk about what it means to be certain of something. What is the difference between doubting that something is true and knowing it is false?

2. What makes you certain that you can always make a map that you can color with two colors using this method? What makes you not so sure that this will always work?

3. At the foundation of this demonstration is the proof technique called induction. The idea behind induction is to begin with the simplest possible case (the closed loop that forms a circle) and build up incrementally to more and more complex cases. If you can explain why every "map" that you build up from that simple loop of string is always 2-colorable, then you have completed your proof.

What next?