Bridges of Königsberg

Problem

Through the city of Königsberg flowed the Pregel River. In this river were two large islands, which were part of the city.

Joining the mainland either side of the river and those two islands there stood seven bridges.

It was a popular exercise among the citizens to take a pleasure stroll across the bridges.

The question naturally arose: was it possible to cross each bridge once and once only during the course of a single walk?

More to the point: could this be done such that the walkers end up back at their starting point?

Solution

The shape of the land and the positions of the bridges are irrelevant.

What is important is the relationships between the land and the bridges.

We can represent each of the landmasses as the vertices and the bridges as the edges of a multigraph:

The question now evolves into: does this graph allow the construction of an Eulerian circuit, or failing that, an Eulerian path?

It can be seen that this is a graph in which there are four vertices, each of which is odd.

From Eulerian Graph, it is clear that the walkers can not cross all the bridges once each and return to their starting point, as all the vertices would need to be even for that.

From Condition for Graph to be Traversable, it also follows that this graph is not traversable, as it has more than two odd vertices.

The answer to both questions is, therefore: No.

$\blacksquare$

Note

Do not assume that this problem relates to graph theoretic bridges.

Historical Note

The solution of this problem, in a rather different form, was first given by Leonhard Euler in his 1736 paper Solutio problematis ad geometriam situs pertinentis, widely considered as the first ever paper in the field of graph theory.

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 3.1$: Theorem $3.1$