Konigsberg bridges The Konigsberg bridge puzzle is universally accepted as the problem that gave birth to graph theory. It was solved by tbe great Swiss-born mathematician Leonhard Euler XXXXXXXXXXThe...

Konigsberg bridges The Konigsberg bridge puzzle is universally accepted as the problem that gave birth to graph theory. It was solved by tbe 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 Konigsberg 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.