Königsberg Bridge Problem — Definition, Formula & Examples
The Königsberg Bridge Problem asks whether you can walk through the city of Königsberg, crossing each of its seven bridges exactly once and returning to your starting point. Euler proved in 1736 that no such route exists, and his reasoning laid the foundation for graph theory.
Given a multigraph representing the four landmasses of Königsberg as vertices and the seven bridges as edges, the problem asks whether an Eulerian circuit exists. By Euler's theorem, 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) is possible.
How It Works
To analyze the problem, replace the physical map with a graph: each landmass becomes a vertex (node), and each bridge becomes an edge connecting two vertices. Count the number of edges meeting at each vertex — this is the vertex's degree. Euler showed that a route crossing every edge exactly once and returning to the start (an Eulerian circuit) requires every vertex to have even degree. If exactly two vertices have odd degree, an Eulerian path (not a circuit) exists. If more than two 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), D (east bank). The edges are: C–A, C–A, C–B, C–B, C–D, A–D, B–D. Determine whether an Eulerian circuit or Eulerian path exists.
Step 1: Count the degree of each vertex by tallying how many edges touch it.
Step 2: Check parity. All four vertices have odd degree. For an Eulerian circuit, every vertex must have even degree. For an Eulerian path, exactly two vertices must have odd degree.
Step 3: Since four vertices have odd degree (more than two), neither an Eulerian circuit nor an Eulerian path exists.
Answer: It is impossible to cross all seven bridges exactly once, whether or not you require returning to the start.
Why It Matters
This problem marks the birth of graph theory and topology as mathematical disciplines. The same degree-parity reasoning Euler used applies today in network routing, circuit design, and any problem that asks whether a route can traverse every connection exactly once.
Common Mistakes
Mistake: Confusing Eulerian paths with Hamiltonian paths. Students sometimes think the problem asks about visiting every landmass (vertex) exactly once.
Correction: The Königsberg problem is about crossing every bridge (edge) exactly once, not visiting every landmass (vertex) exactly once. Visiting every vertex exactly once is the Hamiltonian path problem, which is a different question entirely.