The graph to the right represents a map of the states Kansas, Missouri lowa, South Dakota, and North Dakota. Two vertices are joined by an edge if and only if the states share a stretch of common border. Find the smallest number of colors that can be used to color the map so that any two states sharing a stretch of common border are not colored with the same color The smallest number of colors that can be used to color the map whose graph is shown is square (Type a whole number.)

## Step 1: Understand the problem<br />### The problem involves determining the chromatic number of a graph, which is the smallest number of colors required to color the vertices such that no two adjacent vertices share the same color. Each vertex represents a state, and edges represent shared borders.<br /><br />## Step 2: Analyze the graph structure<br />### To solve this, we need to analyze the graph's structure and determine its maximum degree or any specific patterns (e.g., cycles). This will help us identify the minimum number of colors needed.<br /><br />## Step 3: Apply the Four-Color Theorem<br />### According to the Four-Color Theorem, any planar map can be colored using at most four colors. Since the graph represents a planar map, it can be colored with at most four colors.<br /><br />## Step 4: Verify if fewer colors suffice<br />### By examining the adjacency relationships in the graph, we check if fewer than four colors are sufficient. If the graph contains no vertex with more than three neighbors, three colors may suffice. However, if there are vertices with four or more neighbors, four colors are necessary.