K¨onigsberg bridges The K¨onigsberg bridge puzzle is universally accepted as the problem...

K¨onigsberg bridges The K¨onigsberg bridge puzzle is universally accepted as the problem that gave birth to graph theory. It was solved by the great Swiss-born mathematician Leonhard Euler (1707–1783). The problem asked whether one could, in a single stroll, cross all seven bridges of the city of K¨onigsberg exactly once and return to a starting point. Following is a sketch of the river with its two islands and seven bridges:

a. State the problem as a graph problem.

b. Does this problem have a solution? If you believe it does, draw such a stroll; if you believe it does not, explain why and indicate the smallest number of new bridges that would be required to make such a stroll possible.