Chapter 4.1, Problem 39E

Represent the maps given in Exercises 37-40 by graphs as we did in Example 6. Recall that we join two vertices by an edge if and only if the states that they represent share a stretch of common border

Example 6 Solving the Four-Color Problem for South America

Model the map of South America by a graph and use this graph to color the map using at most four colors.

Solution: In this problem, we have a set of countries, some of which are related in that they share a common border. Therefore, we can model this situation by a graph.

We will represent each country by a vertex; if two countries share a common border, we draw an edge between the corresponding vertices. This graph appears in Figure 4.17 .

Note that we connect the vertices representing Peru and Colombia with an edge because they share a common boundary. We do not connect the vertices representing Argentina and Peru, because they have no boundary in common.

We can rephrase the map-coloring question now as follows: Using four or fewer colors, can we color the vertices of a graph so that no two vertices of the same edge receive the same color? It is easier to think about coloring a graph than it is to think about coloring the original map.

We show one coloring using four colors in Figure 4.18 and another coloring that I generated on my iPad using a graph theory app called Graphynx. Notice that Graphynx again had to use four colors to color the graph.

Figure 4.18 Coloring of graph of South America.

Graphynx coloring of graph of South America.