Title
Ink Shortage (Anne Smelker)
Goals
(1) Students will explore the concept of graph theory as it relates to coloring and planar graphs.
(2) Students will work in small groups to discuss, derive a process, and determine the least amount of colors needed to meet the criteria .
(3) Students will explain how they determined the least number of colors needed and justify their process and results.
Abstract
This activity focuses on applying graph theory to determine the least amount of colors needed and exploring the Four-color Theorem. Students will form groups, explore the problem, develop a hypothesis on the least amount of colors needed, and justify there hypothesis or solution. Each group will then present, explain, and justify their process, methods, and solution to the entire class. This activity could be used to introduce graph theory with coloring, planar graphs, topology and the Four-Color Theorem.
Problem Statement
Discuss with students attributes of maps they have seen. How are maps colored? How do they think the coloring of maps is determined? What determines the number of colors that needs to be used? In small groups, they are to determine the least amount of colors the Atlas Map Company needs to use to color the maps they are given. The requirement is that no region has the same color as a region that it borders. This activity will allow students to explore and apply graph theory, coloring and planar graphs specifically.
Instructor Suggestions
(1) As a class, discuss only the Problem Statement and what is expected of each group but not how to begin solving the problem. Offer several different maps for the groups to work with.
(2) Distribute the "Ink Shortage" activity sheet and have students work in groups to develop their own solutions and methods.
(3) When the groups are finished, have each group have a spokesperson share their methods and the processes they used to determine the least amount of colors needed to color any map.
(4) Discuss each of their methods and processes as it relates to graph theory.
Materials
"Ink Shortage" activity sheet
Time
Introduction of Problem Statement (5 minutes), Group Work (20 minutes), Presentations/Class Discussion (20 minutes)
Mathematics Concepts
Discrete Mathematics Concepts
Graph Theory, Coloring, Planar Graphs, Four-Color Theorem
Related Mathematics Concepts
Graphs and their Applications, Topology
NCTM Standards Addressed
Problem Solving, Communication, Reasoning, Connections (within mathematics and across disciplines), Geometry, Discrete Mathematics
Colorado Model Content Standards Addressed
Geometric Techniques (4), Problem Solving Techniques (5), Linking Concepts and Procedures (6)
Curriculum Integration
This activity could be integrated in a Algebra or Geometry class as the topic of graph theory or patterns.
Further Investigation
Extend the problem to determine the least amount of colors necessary to color any map.
Variations/Comments
Extending the problem to determine the least amount of colors necessary to color any map could be used as an assessment.
References/Resources
Crisler, N., Fisher, P., and Froelich, G. (1994). Discrete Mathematics Through Applications. New York: W.H. Freeman and Company.
Kenney, M. J., and Hirsch, C. R. (Eds.). (1991). Discrete Mathematics Across the Curriculum, K - 12. Reston, VA: National Council of Teachers of Mathematics.
National Council of Teachers of Mathematics. (1989). Curriculum and Evaluation Standards for School Mathematics. Reston, VA: Author.