Königsberg Bridge Problem¶

Definition¶

The Königsberg bridge problem asks whether a closed walk can cross each of the city's seven bridges exactly once. Represent each land region by a vertex and each bridge by an edge. The resulting four-vertex network asks whether an Euler tour exists.

Interpretation¶

The Königsberg problem shows how a network model reduces a question to its essentials: land areas become vertices, bridges become edges, and shapes and distances disappear. The impossibility then follows from vertex degrees rather than from testing every possible walk.

The Konigsberg bridges as a network of four land areas joined by seven edges, including parallel ones, with every vertex of odd degree, so no Euler tour exists.

The island $A$ is joined to each bank $B$ and $C$ by two parallel bridges and to $D$ by one, and $D$ is also joined to $B$ and to $C$ : seven edges in all. The degrees are $5,3,3,3$ , so all four vertices are odd, while an Euler tour needs every degree to be even.

Parallel bridges must stay separate edges, because each bridge has to be crossed; merging the two bridges between $A$ and $B$ into one edge would change both degrees and the question. A single odd vertex would already settle the matter: a closed walk uses the bridges at each land area in pairs, one to arrive and one to leave, and an odd number of bridges cannot be paired.

If the walker may cross some bridges twice, the question becomes a Chinese postman problem. Counting each bridge as length 1, pairing $A$ with $B$ and $C$ with $D$ needs one extra crossing each, so a closed walk with $9$ crossings exists, two bridges being crossed twice, and no shorter closed walk crosses every bridge.

Key Results¶

Parallel bridges are separate edges between the same vertices.
The illustrated degrees are 5, 3, 3, and 3, so the even-degree condition fails.
The requested return to the starting point is part of the problem.

Examples¶

The four vertices represent the land areas: island $A$ , banks $B,C$ and area $D$ . Four odd-degree vertices also rule out an open edge-once trail: such a trail has exactly two odd endpoints, or none if closed. Euler’s 1736 analysis is conventionally regarded as the beginning of graph theory.

The central land region has five incident bridge edges.
At an odd-degree region, a closed traversal cannot pair all arrivals and departures.

Prerequisites¶

Sources¶

OR Modelling · Week 4

Aliases: seven bridges of Königsberg, Seven bridges of Konigsberg, Konigsberg bridge problem, Königsberg bridges problem

Last updated: 20 October 2026 03:02