Math 300

Groupwork

The Seven Bridges of Koenigsburg

Dr. Wilson

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