Question 1.78

48. The following figure shows a river, some islands, and bridges connecting the islands and riverbanks. A charity is sponsoring a race in which entrants have to start at A, go over each bridge at least once, and end at A. Draw a graph that would be useful for finding a route that requires the least recrossing of bridges. Show what that route would be. (Historical note: This situation resembles the one that inspired Leonhard Euler’s 1736 “recreational mathematics” problem that resulted in the first work in graph theory.)

image