Question

Construct the dual graph for the map shown. Then find the number of colors needed to color the map so that no two adjacent regions have the same color.

Short answer

The number of colors need to color the map is four

Step-by-step solution

In the problem given

The graph is:

The definition and the formula for the given problem

Dual Map: In the plane, each map is represented by a graph and in the map every region is represented by a vertex.

Two vertices are connected by edge. If the region represented by these vertices with a common border then, the obtained graph is known as dual graph.

Determining the sum in expanded form

The dual graph of the shown map can be determined by placing one vertex in each region.

Vertex \(a\) is placed in \(A\), vertex \(b\) is placed in \(B\), vertex \(c\) is placed in \(C\) and so on.

We draw an edge between two vertices if the regions of the two vertices are connected.

Next, we remove the given map from the region.

We assign a color to each vertex. If vertices are connected (directly), then the two vertices need to be assigned a different color).

Note that the only vertices that are not connected by an edge are \(c\) and \(e\), thus we can assign these two vertices the same color.

\(\begin{array}{*{20}{r}}{{\rm{ Region }}}&{{\rm{ Vertex }}}&{{\rm{ Color }}}\\A&a&{{\rm{ Blue }}}\\B&b&{{\rm{ Red }}}\\C&c&{{\rm{ Green }}}\\D&d&{{\rm{ Orange }}}\\E&e&{{\rm{ Green }}}\end{array}\)

We then note the we need 4 colors to color the map.

Hence, the number of colors need to color the map is four.