Hint for Section 11.2 Question 2

2. Since the first question does not require us to use all of the edges of the graph, we cannot apply our knowledge of Euler paths/circuits. Try to find a circuit that includes all the vertices.

The second question requires the salesman to use all the roads (edges) exactly once, but does not require him to end up where he started. Recall that an Euler path from v to w is a sequence of adjacent edges and vertices that starts at v, ends at w, passes through every vertex of G at least once, and traverses every edge of G exactly once. In order for a travelling salesman to use the roads shown exactly once to pass through each of the cities, the "graph" of roads and cities must have an Euler path.  Corollary 11.2.5 states that there is an Euler path from v to w in G if, and only if, G is connected, v and w have odd degree, and all other vertices have even degree. You might like to use this corollary to answer the second question.

Back to Section 11.2
Full solution