The Poor Cartographer—Graph Coloring

Curated and Reviewed by Lesson Planet
This The Poor Cartographer—Graph Coloring activity 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. 

21 Views 21 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