Why the Seven Bridges of Königsberg Can’t Be Crossed in One Walk – Euler’s Insight

Problem Overview

In early 18th‑century Königsberg (now Kaliningrad), a river divided the city into two islands connected by seven bridges. A pedestrian wondered whether it was possible to cross each bridge exactly once and return to the starting point.

Euler’s Reasoning

Euler modeled each landmass as a vertex and each bridge as an edge, creating a graph. He argued that except for the start point, every time a traveler enters a vertex via one bridge they must leave via another, so each vertex must have an even degree for a single‑stroke walk.

Why It’s Impossible

The Königsberg graph has four vertices, each of odd degree, violating the even‑degree condition; therefore a walk crossing all seven bridges exactly once cannot exist.

Early Attempts

Before Euler’s work, many tried to find such a route. With 7! = 5040 possible permutations, exhaustive testing was impractical, highlighting the need for a theoretical approach.

Later Developments

In 1735, students wrote to Euler asking for a solution. After a year of study, Euler published his paper in 1736, founding graph theory.

Euler abstracted the problem into a graph with vertices A, B, C, D. He showed that vertex A has degree 5 (odd), B and D have degree 3 (odd), so no Eulerian trail exists.

Eulerian Path Conditions

The graph must be connected.

The number of vertices with odd degree must be either 0 or 2.

These criteria allow quick verification: the Königsberg graph has four odd vertices, so it is not Eulerian.

Euler’s Legacy

Euler’s analysis not only solved the bridge puzzle but also established the Eulerian path theorem, laying groundwork for topology and modern graph theory. A connected graph with all even-degree vertices has an Eulerian circuit; one with exactly two odd-degree vertices has an Eulerian trail.