• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q3E

Expert-verified Found in: Page 733 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # 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.

The dual graph for the map given is: And the number of colors needed to color the given map so that no two adjacent regions have the same color is $$3$$.

See the step by step solution

## Step 1: Given data in the question.

In the question, a map is given. ## Step 2: Definition to be used.

According to the definition of dual graph, each map can be represented by a graph and in every graph each region of the map is represented by a vertex also two vertices are connected by a edge if and only if the region represented by these vertices have a common border, then the obtained graph is known as dual graph.

## Step 3: Construct the dual graph for given map.

Construct the dual graph of the given map by determining one vertex in each region as follows: ## Step 4: Find the number of colors needed to color the map.

Since, the vertex $$a$$ is connected to all the other vertices, thus the color of the vertex $$a$$ should be unique or different from all the other vertices and the vertices $$b$$ and $$d$$ are not directly connected to each other similarly vertices $$f,c$$ and $$e$$ are not directly connected to each other.

Therefore,

 Region Vertex Color A a Blue B b Green C c Red D d Green E e Red F f Red

Color the given map as shown: Hence, $3$ color are needed to color the given map. ### Want to see more solutions like these? 