Question

1. The graph below represents five cities and the routes between them. An out-of-state road inspector is asked to fly into Pottsville (P). From Pottsville, the inspector must inspect each road on the map, making only one trip along each road, and then fly out of Tinkertown (T). a.) Will the road inspector be able to complete the inspection as described? Mathematically explain why or why not and, if such an inspection is possible, describe the route. b.) The inspector would prefer to fly into and out of the same town, but still drive each road only once. Would that be possible? Mathematically explain why or why not and, if such an inspection is possible, describe the route. c.) Below, the map has been expanded to show additional cities and routes. A trucker who lives in Jonesboro (J) needs to make deliveries in each town and then return home without passing through any of the towns more than once. What type of mathematical circuit is the trucker hoping to use? If the trucker can complete the circuit, describe the route.

Answer 1

Please see attached image for the graph.

a.       Yes, it is mathematically possible because the degree of vertices for P=3, T=3, M=2, C=4, and R=2 and in Euler’s theorem, the graph has to be connected, which in this case it is and the number of vertices in the graph whose vertices is odd, is 0 or 2. And in this case, we have 2 that have a degree of vertices that are odd, therefore mathematically this is possible for the driver. The route would be P > R > C > M > T > C > P > T.

 

b.       It is mathematically possible. The router would be P > C > R > T > M > C > T. Essentially, you travel each road once.

c.       The driver would use a Hamiltonian circuit. The route would be J > R > A > C > V > M > T > P > J.