Skip to main content
Edges & Surfaces

The graph theory of Leonhard Euler

Edges & Surfaces — Part 1 of 3

The Seven Bridges of Königsberg

A Sunday puzzle in 1736 Prussia: can you walk through the city crossing all seven bridges exactly once? Leonhard Euler proved it impossible — and in doing so, invented a whole new kind of mathematics. He abstracted the city into dots and lines, asked only about their connections, and discovered that the answer depends on a single number: the degree of each vertex. This was the birth of graph theory, and the first step toward modern topology. Parts 2 and 3 show where the same idea leads next.

Sketch of Königsberg's seven bridges — Altstadt, Kneiphof, Löbenicht, Ponarth connected by seven numbered bridges
Königsberg, Prussia · 1736 — four landmasses, seven bridges

"This type of solution bears little relationship to mathematics… and yet I found myself unable to solve it by any known means."

— Leonhard Euler, letter to Carl Ehler, 1736

The city of Königsberg (now Kaliningrad) straddled the river Pregel. Two islands — Kneiphof and Ponarth — were linked to the north bank (Altstadt) and south bank (Löbenicht) by seven wooden bridges.

Citizens spent Sunday afternoons trying to find a walk crossing each bridge exactly once — without success. Euler's insight was to strip away the city entirely and keep only the connections. The result was the first theorem of a branch of mathematics that didn't yet have a name.

The seven bridges

1 Blacksmith's — Altstadt ↔ Kneiphof
2 Connecting — Löbenicht ↔ Kneiphof
3 Merchant's — Löbenicht ↔ Kneiphof
4 Green — Altstadt ↔ Kneiphof
5 Honey — Kneiphof ↔ Ponarth
6 Wooden — Altstadt ↔ Ponarth
7 High — Löbenicht ↔ Ponarth

Modern Kaliningrad

Two bridges were destroyed in WWII. Two more demolished for a Soviet highway. The modern city now has exactly two odd-degree nodes — an Eulerian path is finally possible, though for the wrong historical reasons.

Euler's abstraction: strip away the city — keep only the connections
Euler's graph. Each landmass becomes a vertex (A–D). Each bridge becomes an edge. The city has been abstracted to pure connection structure.
Step 1 / 8

Try it on paper

Draw four dots labeled A B C D. Connect: A–B twice, C–B twice, A–D once, B–D once, C–D once. Try to trace all seven edges without lifting your pen or repeating any. Try every starting dot — you will always get stuck. Then count how many edges meet at each dot: that number is the degree, and it is the key to everything that follows.

Hierholzer's algorithm (1873)

Euler proved when a path exists. Carl Hierholzer proved how to find one, in a paper published posthumously in 1873. His algorithm runs in O(E) time — linear in the number of edges. Start anywhere, follow edges greedily, and splice sub-circuits until all edges are used. This algorithm reappears directly in Part 2: The Chinese Postman Problem.

The bridge to Parts 2 and 3

Euler's key move was abstraction: he replaced a physical map with a graph — just vertices (land masses) and edges (bridges). The geometry of the city became irrelevant; only the pattern of connections mattered. This is the founding act of topology: ignoring distance and shape, keeping only structure.

In Part 2 (Chinese Postman), we ask the natural follow-up: if the walk is impossible, what is the shortest walk that still covers every edge, even if some must be repeated? The answer requires fixing the odd-degree vertices — the same vertices that made Königsberg impossible.

In Part 3 (Euler Characteristic), Euler's edge-counting moves from graphs to surfaces. Instead of asking whether you can traverse all edges, you ask: what does V − E + F tell you about the shape of a surface? The same combinatorial arithmetic that blocked the Königsberg walk now classifies spheres, tori, and the topology of the universe.

DNA sequencing — genome assembly uses de Bruijn graphs where reassembling the genome is finding an Eulerian path. Every sequenced genome has relied on this directly.

CNC and fabrication — laser cutters, pen plotters, and 3D-printer perimeters minimise tool travel by finding Eulerian trails through the cut geometry.

Euler's theorem — and the number that recurs in all three parts

Let G be a connected graph. G has an Eulerian circuit if and only if every vertex has even degree. G has an Eulerian trail if and only if exactly two vertices have odd degree.

Königsberg has four odd-degree vertices — the walk is impossible. The minimum number of extra edge-traversals needed to make it possible is the subject of Part 2.

The deeper pattern: degree is a local count (edges at a vertex), but it governs a global property (whether the whole graph can be traversed). This local-to-global principle — a local count determining a global constraint — is the central idea of topology, and it reappears in Part 3 as the Euler characteristic χ = V − E + F.

Note: an Eulerian circuit visits every edge once. A Hamiltonian cycle visits every vertex once. The Eulerian question is solvable in linear time; the Hamiltonian question is NP-complete.

Königsberg Seven Bridges