Question 1.98

68. For the street network below, draw a graph that represents the sidewalks with meters. Find the minimum-length circuit that covers all sidewalks with meters. If you drew the graph as we recommended, you would find that the shortest circuit has length 18 (it reuses every edge).

image

But the meter checker comes to you and says, “I don’t know anything about your theories, but I have found a way to cover the sidewalks with meters using a circuit of length 10. My trick is that I don’t rule out walking on sidewalks with no meters.” Explain what he means and discuss whether his strategy can be used in other problems.