In this assignment we will look into the question of how many colors does it take to color a given map. To make this question meaningful, we make the following restriction on how we can color a map: no two regions that share an edge can have the same color. We do allow two regions to have the same color if they only share a corner but no edge. For example, in a map of the United States, we can color New Mexico and Utah the same color, but we cannot color New Mexico and Texas the same color. The map above was colored with six colors. While it was long felt that any map drawn in the plane (or on a globe) could be colored with at most four colors, this was not proven to be true until the 1970's.
Problem 1. Color the following pictures with the coloring rule above. As you do this, think about how many colors you use, and if you could use fewer colors than you used. However, you may use as many colors as you wish.
Now we will see how the problem of coloring a map can be put into graph theoretic language. To associate a graph with a map we draw a graph whose vertices are the regions to be colored, and we connect two vertices if the are edges that share a common edge. For example, the picture below shows a map and the corresponding graph.
 |
 |
In the next problem we will look into what is the smallest number of colors needed to color a given map. For example, consider a map whose graph is the following.
To color this we need three colors. To see why, suppose we color the top vertex red. We need another color, say blue, to color the left vertex. We cannot use red to color the remaining vertex since then two adjacent regions will be colored red. Nor can we color it blue, so we need a third color, say green, to color it. Thus, we need three colors.
Problem 2. Color the following parts of the United States map. In each case determine what is the smallest number of colors you need to color the map and explain why your number is indeed the smallest number of colors that can be used.
 |
 |
Problem 3. Draw the graph associated to the three maps of the previous problem.
Problem 4. Suppose that you have a graph that consists of a vertex in the middle and n vertices surrounding it. We will refer to these as circular graphs. They need at least three colors. Determine, in terms of n, if the graph needs 3 or 4 colors. To help you do this, first answer the question if n = 3, n = 4, and n = 5 and then try to find a pattern.
Problem 5. Find occurrences of circular graphs inside the United States Map. What numbers of outside vertices did you find in these circular graphs? Try to find all possible sizes of circular graphs occurring in the United States Map. A larger copy of a U.S. map can be found by clicking here
Problem 6. If you draw a map on a surface other than a plane or a globe, you may need more than 4 colors. How many colors does it take to color the following map?
