A Colorful Problem

How many colors are needed to color any map so that no two neighboring countries are the same color? This well known application of graph theory is known as the map coloring problem. The problem may sound simple, but it confounded mathematicians until Appel and Haken used a computer to solve it conclusively in 1976.

Chris Caldwell has written a short tutorial which will help you to understand this problem and its connection to graph theory. You will find it helpful to print out pages from the tutorial, or at least copy the problems onto paper so that you can solve them.

And just for fun, you may want to view this site, which uses a Java applet to color in a map of the United States.

This activity contains 4 questions.

	Briefly explain how to make a graph which corresponds to a map. What do the vertices represent? What do the edges represent?   To create paragraphs in your essay response, type <p> at the beginning of the paragraph, and </p> at the end.

	Explain why a map in a plane will always correspond to a planar graph, that is, a graph which can be drawn on a plane without the edges crossing.   To create paragraphs in your essay response, type <p> at the beginning of the paragraph, and </p> at the end.

	Suppose a graph has 8 vertices, each of which is connected to all of the others. How many colors are necessary to color the vertices of this graph so that adjacent vertices have different colors? Explain why your answer does not violate the four color theorem.   To create paragraphs in your essay response, type <p> at the beginning of the paragraph, and </p> at the end.

	You can find a map of the counties in Vermont at http://www.lib.utexas.edu/Libs/PCL/Map_collection/states/Vermont.gif. Sketch a graph that corresponds to the map. Then show how to color the map (or your graph) using four colors. Why is it impossible to color this map with only three colors?   To create paragraphs in your essay response, type <p> at the beginning of the paragraph, and </p> at the end.

Copyright © 1995-2008, Pearson Education, Inc., publishing as Pearson Prentice Hall Legal and Privacy Terms