Seven Bridges of Königsberg

Euler’s 1736 paper on the bridges of Königsberg is widely regarded as the earliest contribution to graph theory – yet Euler’s solution made no mention of graphs.

A well-known recreational puzzle concerns the bridges of Königsberg. It is claimed that in the early eighteenth century the citizens of Königsberg used to spend their Sunday afternoons walking around their beautiful city. The city itself consisted of four land areas separated by branches of the river Pregel over which there were seven bridges. The problem that the citizens set themselves was to walk around the city, crossing each of the seven bridges exactly once and, if possible, returning to their starting point.

In 1254 the Teutonic knights founded the Prussian city of Königsberg (literally, king’s mountain). With its strategic position on the river Pregel, it became a trading center and an important medieval city. The river flowed around the island of Kneiphof (literally, pub yard) and divided the city into four regions connected by seven bridges: Blacksmith’s bridge, Connecting bridge, High bridge, Green bridge, Honey bridge, Merchant’s bridge, and Wooden bridge.

Königsberg later became the capital of East Prussia and more recently became the Russian city of Kaliningrad, while the river Pregel was renamed Pregolya.

In 1727 Leonhard Euler began working at the Academy of Sciences in St. Petersburg. He presented a paper to his colleagues on 26 August 1735 on the solution of a problem relating to the geometry of position’: this was the K6nigsberg bridges problem. He also addressed the generalized problem; given any division of a river into branches and any arrangement of bridges, is there a general method for determining whether such a route exists?

ln 1736 Euler wrote up his solution in his celebrated paper in the Commentarii Acadeniae Scientiarum Imperialis Petropolitanae under the title ‘Solutio problematis ad geometriam situs pertinentis’; Although dated 1736, Euler’s paper was not actually published until 1741, and was later reprinted in the new edition of the Commentarii which appeared in 1752.