**KONIGSBERG BRIDGES PROBLEM**. Graph theory was born when a Swiss
mathematician named Leonhard Euler (pronounced "oiler") solved the problem of
the Konigsberg Bridges. It is said that the people of Konigsberg amused
themselves by trying to devise a walking path around their city which would
cross each of their seven bridges once and only once and return them to their
starting point. As it happened no one ever found such a path and so people
naturally suspected that no such path existed. This problem came to the
attention of Euler and he subsequently published his solution in *Commentarii
Academiae Scientarum Imperialis Petropolitanae*. In short, he was able
to prove that it was impossible to devise a path that crossed each of the
bridges only once. First he drew a sketch of the town labeling the four
land masses as A, B, C, and D and the seven bridges a, b, c, d, e, f, and g.
This is shown below.

Euler then simplified this picture by drawing a graph with the four land masses represented by points and the seven bridges by lines which connect the points. This produced the following graph.

At this point the Konigsberg Bridges problem is "set up" and ready for analysis. Euler started by representing the walking trip as a sequence of the land mass letters A, B, C, and D. Between adjacent letters, of course, a bridge is crossed. He then noted that land mass A has 5 bridges crossing into it or out of it and the other land masses 3 such bridges. The final question he asked himself was how many appearances of each land mass letter did there have to be in the sequence of letters. With this beginning you may now be able to complete a proof that the Konigsberg Bridges problem has no solution.

Adapted from "Problem Solving Across the Disciplines" by R. R. Kadesch, Prentice Hall, 1997.

Return to Honors PS1500 home page

*Last modified:
Tuesday, April 14, 2009 09:42 AM*