Problem — The Bridges of Königsberg
In 1736, Leonhard Euler studied a famous puzzle from the city of Königsberg: could someone take a walk that crossed each bridge exactly once? The challenge was not about distance, speed, or geometry, but about structure.
Euler realized that the essential information was simply which land regions were connected by which bridges. By abstracting the map into vertices and edges, he transformed a real-world puzzle into one of the first problems in graph theory.
What is an Eulerian path?
An Eulerian path is a path that traverses every edge of a graph exactly once. If such a path starts and ends at the same vertex, it is called an Eulerian cycle.
This is the key difference from Hamiltonian problems. In Hamiltonian questions, the focus is on visiting each vertex exactly once. In Eulerian questions, the focus is on traversing each edge exactly once.
Euler’s insight was that the Königsberg puzzle could be answered without testing every possible route. Instead, the answer depends on the degrees of the vertices: how many edges touch each one.
Intuitively, every time you enter a vertex along one edge, you usually need another edge to leave it. That is why vertices of odd degree create difficulties: they break the natural “enter–leave” pairing.
This observation leads to one of the most elegant criteria in graph theory: Eulerian paths and cycles can often be recognized just by inspecting vertex degrees.
Why is this idea important?
Euler’s solution is historically important because it marked a shift away from traditional geometry. The exact shape of the land and bridges did not matter; only the connectivity mattered.
That abstraction became the foundation of graph theory and influenced many later areas of mathematics, computer science, and network analysis.
Today, Eulerian ideas appear in route inspection, street sweeping, circuit tracing, genome assembly, logistics, and communication networks — anywhere the goal is to cover connections efficiently.
Key intuition for Part 1
The core question is not “which route looks good?” but rather: does the structure of the graph allow such a route at all?
In the next part, we will formalize the degree conditions for Eulerian paths and cycles, and see exactly why the Königsberg graph does not admit one.