### The Seven Bridges of Koenigsburg

The city of Königsburg, which was the capital of Prussia, was
built on some islands as in the map below.

If possible, find a route through the city which traverses each
bridge exactly once. You may end at the same point from which you
started, but it is not necessary. All you have to do is to cross each
bridge once before you cross any bridge a second time. If it is not
possible, state why.

This problem was first discovered by the Swiss mathematician
Leonhard Euler (1707 - 1783) who was living in Königsburg
employed as the Imperial Mathematician by the Emperor of Prussia.
Euler wondered if it were possible to take a stroll through
Königsburg traversing each bridge exactly once. When he found
himself frustrated in his efforts, he came up with the solution the
problem which is stated in the solution for
problem 30. If we count the number of
bridges on each region,

we see that there are four regions all with an odd number of
bridges. This figure does not satisfy our

necessary conditions which we noted in the
solution of the last problem.

Legend has it that the residents of Königsburg, after
hundreds of years of failing to find an Eulerian path, built an
eighth bridge, in the position shown below, in order to make the
problem possible.

top

Groupwork