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