Königsberg Bridges and Eulerian Paths | Algorithms II

The Seven Bridges Problem

In 1736, Leonhard Euler considered the city of Königsberg (now Kaliningrad), which straddled the Pregel River. Seven bridges connected four landmasses (two riverbanks and two islands). The puzzle: could a citizen walk through the city, crossing every bridge exactly once, and return to the starting point?

Euler’s key insight was to abstract away geography: landmasses become vertices, bridges become edges. This produced the first formal graph-theoretic argument in history. Euler proved no such walk exists: the four landmasses have degrees 3, 3, 3, and 5 (all odd), making an Eulerian circuit impossible. Beyond solving a puzzle, Euler established graph theory as a mathematical discipline.

Eulerian Paths and Circuits

An Eulerian path (or trail) visits every edge in the graph exactly once; vertices may be revisited. An Eulerian circuit (or tour) is an Eulerian path that starts and ends at the same vertex.

Theorem (undirected graphs): A connected, undirected graph has an Eulerian circuit iff every vertex has even degree. It has an Eulerian path but not a circuit iff exactly zero or two vertices have odd degree; if two, the path must start at one odd-degree vertex and end at the other. If more than two vertices have odd degree, no Eulerian path exists.

Directed version: An Eulerian circuit exists iff every vertex has in-degree equal to out-degree and the graph is strongly connected (ignoring isolated vertices). An Eulerian path (start ≠ end) exists iff exactly one vertex has out-degree $=$ in-degree $+ 1$ (start), one vertex has in-degree $=$ out-degree $+ 1$ (end), and all other vertices have in-degree $=$ out-degree.

Proof Sketch: Necessity

In an Eulerian circuit, every time the walk enters a vertex (except the start/end) it must also leave via a different edge. Thus each visit consumes two incident edges, one for entry and one for exit. For the circuit to cover every edge exactly once, each vertex must have an even number of incident edges in total. If the walk is a path from $a$ to $b$ ( $a \neq b$ ), vertex $a$ has one more exit than entry, $b$ has one more entry than exit, and all others are balanced, giving exactly two odd-degree vertices.

Sufficiency: If all degrees are even, construct the circuit by greedily following unused edges from the current vertex. When stuck (returned to start), you have a closed trail. Remove those edges; the remaining subgraph still has all even degrees. Recursively find circuits in each connected component and splice them into the main circuit at shared vertices. This construction is called Hierholzer’s algorithm and runs in $\Theta(|V| + |E|)$ .

Worked Example 1: Königsberg

Landmasses: two riverbanks (north, south), two islands (Kneiphof, Lomse). Bridges: 5 connect to Kneiphof, 3 to the north bank, 3 to the south bank, 3 to Lomse. In the graph, every vertex has odd degree (3, 3, 3, 5). Since all are odd, Euler’s theorem says no Eulerian circuit or path exists. The problem is impossible.

Worked Example 2: Modified Bridge Network

Suppose one bridge is added between the two riverbanks, making degrees: 4, 4, 3, 3. Now exactly two vertices have odd degree (3). An Eulerian path exists, starting at one odd-degree vertex and ending at the other.

Worked Example 3: Simple Abstract Graph

Graph with vertices $\{A,B,C,D\}$ and edges: $\{A,B\}, \{A,C\}, \{B,C\}, \{B,D\}, \{C,D\}$ (five edges). Degrees: $\deg(A)=2$ , $\deg(B)=3$ , $\deg(C)=3$ , $\deg(D)=2$ . Exactly two odd-degree vertices (B and C). Eulerian path: $B \to A \to C \to D \to B \to C$ . No circuit exists (B and C are odd).

Graph Invariants

The parity of vertex degrees (the count of odd-degree vertices) is a graph invariant preserved under isomorphism. In Königsberg, the parity multiset is $\{3,3,3,5\}$ , all odd; no isomorphic graph with all even degrees can exist. This is an early example of an invariant proof: properties preserved by isomorphism can be used to prove non-isomorphism.

Modern Applications

Chinese Postman Problem: Find the shortest closed walk covering every edge at least once. Solved by identifying odd-degree vertices, computing a minimum-weight perfect matching among them (to determine which edges to duplicate), then finding an Eulerian circuit. Runs in $O(|V|^3)$ due to the matching step. Applications in postal delivery, street sweeping, and gritting routes.
DNA fragment assembly (de Bruijn graphs): Sequencing produces short overlapping reads (k-mers). A de Bruijn graph is built where edges represent k-mers and vertices represent (k-1)-mer overlaps. An Eulerian path through this graph reconstructs the original genome sequence. This scales much better than Hamiltonian-path alternatives for large genomes.
PCB testing: Test probes must traverse every trace on a circuit board exactly once; this is an Eulerian path problem.
Snow plough routing: After a snowfall, every street must be ploughed; the problem reduces to Eulerian circuit construction on a multigraph (multiple lanes per road).

Key Distinction

Eulerian: visits every edge exactly once. Solvable in $\Theta(|V| + |E|)$ .
Hamiltonian: visits every vertex exactly once. NP-complete in general; no efficient algorithm is known.

Do not confuse these two in exam answers.

Summary

Concept	Condition
Eulerian circuit (undirected)	All vertices have even degree
Eulerian path (start ≠ end)	Exactly 0 or 2 odd-degree vertices
No Eulerian walk	$\ge 4$ odd-degree vertices
Directed Eulerian circuit	in-degree = out-degree for all vertices
Existence check	$\Theta(V)$ (count degrees)
Construction (Hierholzer)	$\Theta(V+E)$
Chinese Postman	$O(V^3)$ (matching on odd-degree vertices)

Past paper questions: Not a heavily examined standalone topic, but graph invariants and parity arguments appear in proofs. Connected components and BFS are related exam topics (y2025p1q9).