FOUR - COLOR LESSON

In the "Solving Problems" section of the Beyond Numbers exhibit, visitors use four different color pieces to color flat maps and graphs.

Why four colors? Because the map can be represented as a planar graph. Planar graphs can be drawn on a plane or on a sphere without crossing lines. Any planar graph can be colored with just four colors so that no two points joined by a line are ever the same color. This is called the Four-Color Theorem. Non-planar graphs may need more than four colors.

In 1976 Kenneth Appel and Wolfgang Haken reduced the Four-Color Problem to checking whether 2,000 special maps had certain mathematical properties. About 1,200 hours of computer time were needed to complete this last step of their proof. Since that time, the computer's role relative to human insight has been the subject of an on-going debate about how math will be practiced in the future.

On a flat surface like the map, only four colors are needed to color it so that no regions with the same color ever touch. But on a donut, it takes seven. The hole means that colors are needed.

NCTM Standards and/or AAAS Benchmarks addresses:

Mathematical Connections:
Students can apply mathematical thinking and modeling to solve problems that arise in other disciplines, such as art, music, psychology, science and business.

Mathematics, Science and Technology:
Students know that developments in science or technology often stimulate innovations in mathematics by presenting new kinds of problems to be solved. In particular, the development of computer techonology (which itself relies on mathematics) has generated new kinds of problems and methods of work in mathematics.

VOCABULARY

vertex (vertices) - point or corner where edges meet

edge - a line or border

graph - in this lesson, a network of vertices connected by edges

INTRODUCTION

Students explore vertex coloring in the following lesson. They begin with a game of graphs and then explore map coloring with the November 1990 Student Math Notes published by the National Council of Teachers of Mathematics (NCTM).

OBJECTIVES

Students will use graph theory, the study of networks, to describe the coloring of a map.

MATERIALS

Colored chalk, paper, pencils, scratch paper, packets reproduced from the NCTM materials attached, four different colored crayons and game rules for each student pair.

PROCEDURE

Point out that, in this lesson, "graph" has a meaning that may be new to the students. Distribute the game rules to the children. Model the rules of the vertex coloring game at the chalkboard. Then use the Student Math Notes (click on this link) that is reprinted in this manual with permission of the National Council of Teachers of Mathematics.

EXTENSION

Present this challenge: Elizabeth Wilmer, a New York City high school student, won second prize in the nation in the Westinghouse Science Talent Search for her work analyzing maps that could be colored with three colors. Can you color this map with only three colors? What if Oregon were added to the map? Could you still color the map with only three colors?

Class Management Tip:

Before doing the NCTM materials, young students may practice identifying which regions share a border.

ASSESSMENT

Have students find your state or province on a map of your country. Then have them choose six other surrounding states. States do not have to border your state as long as they are all linked to a bordering state. Have students draw a vertex in each state. Then have them link, with an edge, every pair of states that shares a common border so that vertices joined by an edge have different colors. Have them redraw this graph separately and color the vertices.

RULES

Vertex Coloring Game:

vertex (vertices) - a dot
edge - a line
graph - a network of vertices connected by edges

Object:
1) Be the last player to draw an edge, and
2) find the fewest colors for the graph.

PLAYER 1 - Draw between four to eight vertices as small circles anywhere on your paper.

PLAYER 2 - Connect any two vertices with an edge (a line).

PLAYER 1 - Find two vertices that have not been connected and join them with an edge, but don't cross any of the edges already drawn.

Continue taking turns until no more edges can be drawn.

As an extra challenge to pick up the match, the player who draws the last edge wins the match AFTER she colors the vertices in 4, 3, or 2 colors so that no two connected vertices have the same color. (It will always be possible)

last revised 2/06/01

Link to the main Beyond Numbers Table of Contents
Link to Teacher Manual Table of Contents
Link to Eisenhower Consortium
Cathy Brady's home site
cathysfiddle@yahoo.com