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 Two.

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 vertex \(b\) is only not connected by an edge to vertex \(d\), thus we could assign these vertices the same color.

We also note that the two remaining vertices \(a\) and \(c\) are not connected by an edge, while they are connected to \(b\) and/or \(d\), thus we could assign \(a\) and \(c\) the same color (but different from the color of \(b\) and \(d\) ).

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

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

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