---
tag: 0YCW781Q9D
kind: example
name: Seven Bridges of Königsberg
msc: [05C45]
instance_of: [05NWGBHKSZ]
sources:
  - url: https://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg
    locator: Euler's analysis
same_as:
  wikidata: Q33100
  wikipedia: Seven Bridges of Königsberg
---

## Example

The city of Königsberg had four land areas, joined by seven bridges over the river Pregel.
The problem asked for a walk that crosses each bridge exactly once.

Model each land area as a vertex and each bridge as an edge. This gives a connected [[multigraph|01M5T0KDG7]] with $4$ vertices and $7$ edges.
The degrees of the vertices are $5$, $3$, $3$ and $3$.
An [[Eulerian trail|0NNYDD1AVR]] can have at most two vertices of odd degree, by the theorem on [[degrees along an Eulerian trail|0CDVDGWGEG]].
Here all four degrees are odd, so the walk does not exist.

## Remarks

Leonhard Euler solved the problem in 1736. His analysis is often seen as the start of graph theory.
The problem has no solution even if the walk does not have to return to its start.

## Explanations

### L1 human

Each time a walk passes through a land area, it uses two bridges there, one to enter and one to leave.
So a land area in the middle of the walk needs an even number of bridges.
Königsberg had four land areas with an odd number of bridges.