Mathematics
The Seven Bridges of Königsberg and Graph Traversal
Quick fact
Euler's 1736 solution showed that a walk crossing every bridge exactly once is possible only if the graph has either zero or exactly two vertices of odd degree; since Königsberg had four such vertices, the tour was impossible.
Why this is interesting
You are standing in 18th-century Königsberg, trying to cross all seven bridges exactly once and return to your starting point. Is it possible? Euler said no—and in solving it, he gave birth to a whole new branch of mathematics.
Read the full explanation
Understanding The Seven Bridges of Königsberg and Graph Traversal
The problem is about crossing the city's seven bridges, which span the Pregel River and connect two islands to the mainland. To analyze it, think of each landmass—the two islands and the two mainland regions—as a dot (a vertex), and each bridge as a line connecting two dots (an edge). This creates a graph. The question becomes: can you trace a path through the graph that uses each edge exactly once? Such a path is called an Eulerian trail (or Eulerian path). Imagine trying to draw a figure without lifting your pen or retracing any line. That's the same challenge. Euler noticed that when you enter a vertex, you need an unused edge to leave. For a vertex in the middle of the walk, each time you enter, you also leave, using two edges per visit. So every time you pass through a vertex, you use an even number of edges. Only the start and end vertices can use an odd number of edges, because you start there and don't need to leave, or end there and don't need to enter. Therefore, for an Eulerian trail to exist, the graph must have either zero or exactly two vertices of odd degree (the number of edges incident to a vertex). The Königsberg graph had four vertices, each with an odd degree (3, 5, 3, and 3), so no such walk existed.
A deeper explanation
The underlying principle is the relationship between the degrees of vertices and the structure of a trail that uses every edge exactly once. This principle, later formalized as Euler's theorem, states that a connected graph has an Eulerian circuit (a closed trail that uses every edge) if and only if every vertex has even degree. For an open Eulerian trail, exactly two vertices have odd degree, and the trail must start at one and end at the other. The why is the parity argument: each time a trail enters and leaves a vertex, it consumes two edges, so the number of edges used at a vertex must be even unless the vertex is the start or end. In Königsberg, all four vertices had odd degrees, making an Eulerian trail impossible. Euler's work not only solved the puzzle but also created a foundational tool for analyzing all kinds of networks—from road systems to the internet—by asking whether a route can cover every edge exactly once. This concept of graph traversal remains central to modern computer science and logistics.