Seven Bridges of Königsberg — Definition, Formula & Examples
The Seven Bridges of Königsberg is a historic puzzle that asked whether you could walk through the city of Königsberg, crossing each of its seven bridges exactly once and returning to your starting point. In 1736, Leonhard Euler proved this was impossible, and his reasoning laid the foundation for graph theory.
The problem models the Königsberg landmasses as four vertices and the seven bridges as edges in a multigraph. Euler demonstrated that a closed walk traversing every edge exactly once (an Eulerian circuit) exists if and only if every vertex has even degree. Since all four vertices in the Königsberg graph have odd degree, no such circuit — or even an Eulerian path — exists.
How It Works
To analyze the problem, you represent each landmass as a node and each bridge as an edge connecting two nodes. Then you count the degree of each node — the number of edges attached to it. The Königsberg graph has four nodes with degrees 3, 3, 3, and 5, all odd. An Eulerian path (crossing every edge exactly once without necessarily returning to the start) requires exactly 0 or 2 vertices of odd degree. Since all four vertices have odd degree, neither an Eulerian path nor an Eulerian circuit is possible.
Example
Problem: The Königsberg graph has four vertices: A (north bank), B (south bank), C (island 1), and D (island 2). The edges are: A–C, A–C, A–D, B–C, B–C, B–D, and C–D. Determine whether an Eulerian path or circuit exists.
Step 1: Count the degree of each vertex by tallying its edges.
Step 2: Count how many vertices have odd degree. All four vertices — A, B, C, and D — have odd degree.
Step 3: Apply Euler's theorem: an Eulerian circuit requires 0 odd-degree vertices; an Eulerian path requires exactly 2. With 4 odd-degree vertices, neither exists.
Answer: It is impossible to cross all seven bridges exactly once, whether or not you require a return to the starting point.
Why It Matters
This problem is considered the origin of graph theory and topology, two major branches of modern mathematics. In discrete math courses, it introduces the concept of Eulerian paths and circuits, which apply directly to real problems like designing efficient mail delivery routes, circuit board wiring, and network traversal algorithms.
Common Mistakes
Mistake: Confusing Eulerian paths with Hamiltonian paths.
Correction: An Eulerian path traverses every edge exactly once; a Hamiltonian path visits every vertex exactly once. The Königsberg problem is about edges (bridges), not vertices (landmasses).