Question 1.63

33. The company that distributes natural gas in a small town is located at vertex C in the accompanying graph G, which models the two-way streets for the town.

image
  1. Can an inspector for gas leaks travel along the street network and find a route that starts and ends at C and has no deadheads (repeated edges)?
  2. What is the minimum number of repeated edges in a shortest-length tour T, starting and ending at C, that looks for gas leaks?
  3. By duplicating existing edges in G, use tour T to modify graph G to obtain a new graph G*, which shows that T can be interpreted as an Euler circuit in G*.

33.

(a) No

(b) 4

(c) Answers will vary. One solution would involve duplicating edges CD, DE, FG, and AB in the accompanying graph.