The Poor Cartographer—Graph Coloring

This The Poor Cartographer—Graph Coloring activity & project also includes:

Color the town red. Demonstrate the concept of graph theory with a task that involves determining the least number of colors needed to color a map so that neighboring countries are not represented by the same color. Pupils make connections to determine the optimum solutions to the problem. 

7 Views 8 Downloads
Instructional Ideas

  • Lead a discussion using the What's it All About section before having the class perform the activity
  • Have advanced classes determine the number of combinations necessary to color a specified number of countries
Classroom Considerations

  • Younger classes may not use the least number of colors possible

  • Provides several practice pages
  • The reading provides a background that connects the activity to computer science

  • Some of the figures are not near where the topic is discussed in the text