The Seven Bridges of Königsberg — the birth of graph theory

What just happened?

In 18th-century Königsberg (today Kaliningrad) the river Pregel split the city into 4 parts — two banks (A, B) and two islands (C, D — Kneiphof and the neighbouring island) — joined by 7 bridges. Residents wondered whether you could cross every bridge exactly once. In 1736 Leonhard Euler proved it was impossible — and in doing so founded a whole new branch of mathematics: graph theory.

The model: a graph instead of a map

Euler reduced the map to a graph: the landmasses become vertices and the bridges become edges. The number of bridges meeting a given landmass is called the degree of that vertex:

Every bridge has two ends, so the sum of all degrees is always twice the number of bridges — this is the handshaking lemma:

Euler’s theorem

A route that traverses every edge exactly once (an Eulerian path or circuit) exists if and only if the number of vertices of odd degree is:

0 odd vertices → an Eulerian circuit exists (start = finish, at any vertex). 2 odd vertices → an Eulerian path exists (you must start and finish exactly at those two vertices). Any other number of odd vertices — impossible, no exceptions.

Why Königsberg failed

In the original layout all 4 landmasses have odd degree (3, 3, 5, 3) — four odd vertices, not 0 or 2. That is why no walk over all 7 bridges without repetition exists — not because the residents lacked ingenuity, but because of the structure of the graph itself. Adding a single bridge (e.g. A–B) flips two of the landmasses to even degree, leaving exactly 2 odd vertices — and an Eulerian path appears at once.

What does it mean in practice?

The same parity condition governs postal and refuse-collection routes today (the Chinese postman problem), printed-circuit-board design, DNA sequencing (assembling fragments in a de Bruijn graph) and route planning in networks — everywhere you have to traverse every connection exactly once.

Why this matters for your exams:

Graph theory is not formally a separate exam topic, but Euler’s reasoning is a textbook example of a proof by invariant — count something that does not change (here: the parity of the degrees) and show that the problem’s condition contradicts it. The same move (“show that it cannot be done…”) appears in advanced-level combinatorics problems and in olympiad problems.

Remember: an Eulerian path or circuit exists if and only if the number of odd-degree vertices is 0 (circuit) or 2 (path) — any other number means it is impossible. This is the first result in the history of graph theory.