We look back 250 years to the origins of graph theory when Euler presented a paper on the solution of the Konigsberg bridges problem.
THE TRAIL BEGINS
The beautiful medieval city of Konigsberg in Prussia was founded by the Teutonic knights in 1254. Over the next 200 years it grew into a large and wealthy town with many beautiful churches and a fine cathedral. Its situation on the river Pregel made it an ideal trading center for many commodities, such as grain, potash, salt, hemp, and wood. (Two photographs of Konigsberg can be seen in [17].) The river Pregel surrounded the island of Kneiphof, and the various parts of the city were linked by seven bridges known as Green bridge, Merchant's bridge, Blacksmith's bridge, High bridge, Wooden bridge, Connecting bridge, and Honey bridge (see Fig. 1).
On 26 August 1735 Leonhard Euler presented a paper to the Academy of Sciences in St. Petersburg (now Leningrad) where he had worked since 1727 and had succeeded Daniel Bernoulli as leading mathematician in 1733. In his paper, Euler described the solution of "a problem relating to the geometry of position". This problem, which he believed to be widely known (although no evidence has come to hand which supports this), was the Konigsberg bridges problem, which asks whether it is possible to find a route which crosses each of the seven bridges of Konigsberg once and once only. More generally, given any division of the river into branches and any arrangement of bridges, is there a general method for determining whether. such a route is possible?
Euler's paper on the Konigsberg bridges first appeared (in Latin) in the Commentarii Academiae Scientiarum Imperialis Perropolitanae under the title "Solutio problematis ad geometriam situs pertinentis" [7]. Although dated 1736, it was not actually published until 1741 (see Fig. 2), and was later republished in the new edition of the Commentarii (Novi Acta Commentarii . . .),