Euler's Bridges

By Aussiegirl

Have you ever wondered if you could traverse a series of bridges and return to your starting point without having crossed any bridge more than once? Well, I never have, but the worthy inhabitants of 18th century Königsberg used to wonder this about their seven bridges (see the illustration), and this puzzle interested one of the greatest mathematical geniuses of all time -- and certainly the most prolific -- Leonhard Euler (pronounced as if written "oiler"). Not only did he prove that the seven bridges couldn't be so traversed, but, to quote from the article, Euler's paper arguably marks the beginning of topology and graph theory.
In addition to the article posted below, you might also be interested in Wikipedia's articles on Euler and the Seven Bridges problem.
I couldn't find Euler's solution (anyway, it was probably in Latin), but I found this easy-to-understand solution:
Euler recognized that in order to succeed, a traveler in the middle of the journey must enter a land mass via one bridge and leave by another, thus that land mass must have an even number of connecting bridges. Further, if the traveler at the start of the journey leaves one land mass, then a single bridge will suffice and upon completing the journey the traveler may again only require a single bridge to reach the ending point of the journey. The starting and ending points then, are allowed to have an odd number of bridges. But if the starting and ending point are to be the same land mass, then it and all other land masses must have an even number of connecting bridges.
Alas, all the land masses of Konigsberg have an odd number of connecting bridges and the journey that would take a traveler across all the bridges, one and only one time during the journey, proves to be impossible!

Math Trek: Euler's Bridges, Science News Online, Sept. 23, 2006

Euler's Bridges
Ivars Peterson

The East Prussian city of (now part of Russia and known as Kaliningrad) straddles both banks of the River Pregel and an island, called Kneiphof, located right where the river divides into two branches. In the 18th century, seven bridges spanned various segments of the river, connecting different parts of the city.

These bridges were the subject of a well-known puzzle at the time: Could a person follow a path through the city that crosses each of the bridges only once, then returns to the starting point?

In 1735, Leonhard Euler (1707–1783), then living in St. Petersburg, provided the first mathematical proof that such a journey is impossible. He presented it to members of the St. Petersburg Academy on Aug. 26 of that year. His solution was eventually published in 1741 in the academy's proceedings, under the title "Solutio problematis ad geometriam situs pertinentis (The solution of a problem relating to the geometry of position)."

"Backlogs were apparently a problem even in the 18th century, but perhaps they were more of a problem for Euler than most since he was so prolific," comments Gerald K. Alexanderson of Santa Clara University in the October Bulletin of the American Mathematical Society. Indeed, within the mathematics section of the 1741 volume, 11 of the 13 articles are by Euler, all written in 1735 or 1736.

Euler's paper arguably marks the beginning of topology and graph theory. Even the paper's title shows that Euler himself was aware that he was dealing with a new type of geometry in which distance and measurement are not relevant. What matters is position and connection.

In his paper, Euler not only explained why it's impossible to make the desired journey across the Königsberg bridges but also established criteria for determining whether such a journey is possible for any network of bridges anywhere. [....]