This problem is remarkable for several reasons. The Koenigsberg bridge problem was a recreational mathematics problem that was solved by a young great Swiss mathematician, Leonhard Euler (1707 - 1783), in 1736. Euler's publication of his solution of this problem is recognized today as the first occurrence of Graph Theory. Seldom can the creation of a discipline be so clearly identified as the work of a specific person in a particular publication. It is of some interest to note, that Euler's original paper has been translated into English and after 250 years is both readily available and quite readable.

Koenigsberg was a Prussian city (no longer a German city since W.W.II) located on the river Pregel. There was an island at Koenigsberg, then called Kneiphof. The map of Koenigsberg is given below.

The problem apparently arose with Germany's well documented obsession with walking. On Sunday afternoon the good buerghers of Koenigsberg liked to walk through their town, and for some reason, it became fashionable to cross all of the seven bridges before returning home. Eventually someone, probably an ancestor of one of the troublesome children in your class, raised the question, "Why can I never complete my walk without crossing one of the bridges twice?". The more formal statement is: Is it possible to walk over the seven bridges and not cross any of the bridges twice?

Please explore this problem with a partner for the next few minutes. Your job is either to find a walk that crosses all the bridges once, but none of the bridges more than once. If you decide this is impossible, work with your partner to try to find an explanation why it is impossible.

A historical note on Euler: Euler was born in Switzerland, and became the leading and most prolific mathematician of his day. At this time - 40 years before the American Revolution - mathematics positions were exceptionally rare, and Euler moved from Switzerland to Russia, to Berlin, and back to Russia where he died at the age of 76. Euler is noted for having enriched all areas of mathematics, and for being a spectacularly successful calculator. He was noted for his humanity and warmth. He loved children and fathered 13. At the age of 28 he became blind in one eye, and at the age of 61, he lost the sight of the other eye. Without a noticeable loss of productivity, he continued to author volumes upon volumes of research until his death 15 years later.

The utility of graph theory was not widely recognized until this century. In fact, until midway through this century, graph theory was seldom mentioned in history of mathematics books. Today there are research journals devoted to the subject.

Euler made two well known contributions to graph theory: the seven bridges of Koenigsberg problem and his formula V - E + F = 2 relating the numbers of edges, faces, and vertices of a convex polyhedron.