Color the following “map” by first modeling it with a graph and then coloring the graph, a...

Color the following “map” by first modeling it with a graph and then coloring the graph, as we did in Example.

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.

Graph model of map of South America.

Coloring of graph of South America.

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.

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.

There are several ways to color the graph in Figure. However, unlike tracing graphs, there is no particular procedure for accomplishing this coloring except trial and error. One possible coloring for the graph appears in Figure. You may want to color this graph in a different way; however, notice that you cannot do it using fewer than four colors.