Math · Exploration

The Seven Bridges of Königsberg

Can every bridge be crossed exactly once?

A walk through Königsberg

Königsberg was a Prussian city around the Pregel River. Its seven bridges joined four land regions: two mainland banks and the islands of Kneiphof and Lomse. A local puzzle asked whether one walk could cross every bridge exactly once.

Try it

Euler changed the problem

Rather than drawing routes through the city, Leonhard Euler kept only the connections. Each land region becomes a vertex; each bridge becomes an edge. The map’s shapes, distances, and river bends can disappear without changing the question.

Use “Show the graph” to see the same structure stripped down to its essential connections. Because several bridges can join the same pair of regions, this is a multigraph.

Connection can matter more than shape

This is an early lesson in topology: some questions depend on how things are connected, not on their exact geometry. Stretching the map cannot turn an impossible bridge walk into a possible one.

Stop searching. Count.

At an intermediate region, every bridge used to arrive needs another unused bridge to leave. Those uses come in pairs, so intermediate vertices must have even degree. Only a starting vertex and an ending vertex may have an unpaired bridge.

A connected graph has an Euler trail exactly when it has 0 or 2 odd-degree vertices; it has an Euler circuit exactly when it has none. The original seven-bridge graph has four odd-degree vertices, so no route can cross every bridge exactly once.

Why one bridge changes the answer

Remove a bridge in the interaction and recount the degrees. The graph is left with two odd-degree vertices, so an Euler trail becomes possible: begin at one odd vertex and finish at the other.

Why this problem matters

Euler’s analysis of the problem in the 1730s is widely regarded as a founding moment for graph theory. It showed that a carefully chosen abstraction can settle a question that route-by-route trial cannot.

Computing connection

Graphs preserve the relationships that matter while discarding irrelevant geometry. Networks, delivery routes, software dependencies, and social connections can all be reasoned about this way.