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

Suggested languages for you:

Americas

Europe

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.