2. Since the first question does not require us to use all of the edges of the graph, a
circuit which passes through all the cities exactly once is:
Well, Paris, Sirhc, Yllek, Dalc, Mardn, Rives, Rome, Well.
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. In order for a travelling salesman to use the roads shown exacly 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. However, in this graph there are four vertices with odd degree, so there is no Euler path. Hence the salesman cannot use all the roads exactly once to visit the cities.