Restate the Map Coloring problem from Student Activity 9 in terms of a Graph Coloring problem. You are the publisher of a new edition of the world atlas. As you prepare the different maps for printing, you need to make sure that countries adjacent to each other (sharing a common border) are given different colors. Create a graph that requires three colors. Create a graph that could be colored with two colors. What types of graphs can always be colored with two colors? EXTENSION: Create a graph that needs five colors, and then draw the associated map. REFLECTION: When might a graph not correspond to a map? The chromatic number of a graph is the minimum number of colors needed to color each vertex in such a way that any two vertices sharing an edge are a different color. Provide examples of graphs that have chromatic numbers of 3 and 4. Give an example of a graph with 20 vertices that has a chromatic number of 2. Does your graph have any cycles? (Recall: A cycle is a path through the graph that starts and ends at the same vertex and does not reuse any edges.)
Restate the Map Coloring problem from Student Activity 9 in terms of a Graph Coloring problem. You are the publisher of a new edition of the world atlas. As you prepare the different maps for printing, you need to make sure that countries adjacent to each other (sharing a common border) are given different colors. Create a graph that requires three colors. Create a graph that could be colored with two colors. What types of graphs can always be colored with two colors? EXTENSION: Create a graph that needs five colors, and then draw the associated map. REFLECTION: When might a graph not correspond to a map? The chromatic number of a graph is the minimum number of colors needed to color each vertex in such a way that any two vertices sharing an edge are a different color. Provide examples of graphs that have chromatic numbers of 3 and 4. Give an example of a graph with 20 vertices that has a chromatic number of 2. Does your graph have any cycles? (Recall: A cycle is a path through the graph that starts and ends at the same vertex and does not reuse any edges.)
AMDM%20SAS%20VII.C.10.docx