Graph Coloring

We are still trying to discover how to color the map of South America with the fewest number of colors. Now that we have created a model of the map of South America, we can color the model instead of the actual map.

A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.

Here are two simple graphs. Each one is repeated three times on your worksheet. Color each of the graphs according to the instructions below. Make sure that in each situation any vertices that are connected are not the same color.

1. Color each graph with as many colors as you can.
2. Then color each one in a different way.
3. Finally try to color the graph with the least number of colors possible.

Back: Mathematical Models
Next: Chromatic Number