The Seven Bridges of Königsberg

Eduard Lucas: Récréations mathématiques

Bd. 1, Paris, 1882

The Pregolya River forms an island in the heart of the Prussian city of Königsberg (now Kaliningrad). In the eighteenth century, seven bridges connected the river banks to the island. This begged the question as to whether there was a route where one could cross all seven bridges only once and end up back at the starting point.  

The Seven Bridges of Königsberg – history

The Seven Bridges of Königsberg problem stems from Leonhard Euler, who proved in 1736 that no such route can exist. He considered the general case with any number of islands and bridges and revealed that the type of route in question is actually possible if none of the banks has an odd number of bridges. If there is an odd number of bridges on precisely two banks, a path which begins and ends with these two banks and crosses all bridges precisely once exists. If there are more than two places to which an odd number of bridges lead, as in Königsberg, a route that crosses all the bridges precisely once is impossible.

The Seven Bridges of Königsberg – mathematics

The bridge problem is a topological one, which Euler solved using a method that would be classed as graph theory today. It involves contemplating a graph, the nodes of which are the individual areas of the town and the edges the bridges. The idea is to find a cycle that runs along all the edges precisely once. In the language of graph theory, an "Eulerian circuit" is said to exist if there are no nodes with an odd number of edges. If the starting and finishing points are not the same, this is referred to as an "Eulerian path".  The assertions proven by Euler can be applied to the corresponding assertions for graphs.

One variation of the problem is the question as to whether a shape can be drawn in one stroke, without lifting the pencil from the paper.