Graph Theory Lesson Extension Teacher Preparation Teachers will need: a large graph drawn on the floor or ground. markers or other colored drawing utensils. blank maps of any country or region (USA, Europe, North America). Graph Coloring Worksheet. Example Large Graphs. Lesson Outline Focus and Review Hand out a blank map of the United States (or another country/region). Give each student 4 markers/crayons. Let the students experiment with coloring the graph with only those 4 colors. Before the students begin coloring, inform them that no state can have the same color as its neighbors. Objectives Students will learn about the Four Color theorm and make real world connections. Teacher Input Discuss the maps students have been coloring. Define Chromatic Number and the Four Color Theorm. Explain the rules of Quibble, Crouch, Cornerstone, Quoink. Guided Practice Let the students play Quibble, Crouch, Cornerstone, Quoink on the large graph. Students can be divided up into smaller groups to play this game or students can play as a class. Teacher Input If you didn't already, go into more detail about Chromatic Number and the Four Color Theorm. Independent Practice Hand out the colorful houses and colorful sidewalks worksheet. Explain the directions for the worksheets. Let students work quitely at their desks. Closure Discuss some of the coloring schemes students used. Discuss methods that the students used to successfully color the houses and sidewalks. Talk about real world applications of graph coloring.

The Shodor Education Foundation, Inc.