Answer to Question #309561 in Discrete Mathematics for Snave

Question

The country’s capital city of Kathmandu is located in the center of Province 3. You decide to visit Nepal and want to drive through all provinces, trying to avoid as much as possible to visit one province twice. You arrive at Kathmandu Airport and take a rental car. The trip can begin. But wait – let’s plan things a little bit first. You open your map and your laptop.

As an abstract thinker, you may decide to first formalize the map as a graph and use it to plan the trip.

1)   Formalize the map of Nepal as a graph , where the vertices are the provinces and edges connect vertices that represent different provinces with a common border. For example, {1,3} is in E because Provinces 1 and 3 share a border.

2)   What degree does each vertex of G have?

3)   Determine which province is adjacent to the most other provinces.

4)   Is G planar? If yes, provide a drawing as a justification, that is, draw G so that edges meet only at vertices. If the graph is planar, how many faces does it have?