Graph Euler: The Seven Bridges That Invented a Branch of Mathematics
Can you cross every bridge in a city exactly once and return to where you started? This question sounds like a children’s riddle, the kind you might sketch on a napkin during a long dinner. But in 1736, the Swiss mathematician Leonhard Euler proved that for one city, the answer was no and in doing so, he created a new branch of mathematics. The concept of graph Euler originates in that proof, in a Prussian city whose geography posed a puzzle geometry alone could not solve. The seven bridges of Königsberg, spanning the river Pregel and connecting two islands to the mainland, became the birthplace of graph theory. What makes this story extraordinary is not just the solution but the nature of the question: Euler showed that some problems cannot be answered by cleverness or persistence. They can only be answered by understanding structure itself. In that shift from trying harder to thinking differently, modern mathematics found one of its most fertile territories.
Euler Saw Connections Where Others Saw Crossings
Picture Königsberg in the early eighteenth century: a prosperous trading city in East Prussia, now the Russian exclave of Kaliningrad. The river Pregel divides the city into four landmasses connected by seven bridges. On Sundays, citizens strolled along the riverbanks, and the question became civic folklore: could you design a walk that crossed each of the seven bridges exactly once? Neighbors argued over it. Nobody found such a route, but nobody could prove it was impossible, either.
Leonhard Euler, then working at the Imperial Russian Academy of Sciences in St. Petersburg, learned of the problem through correspondence with Carl Leonhard Gottlieb Ehler, the mayor of Danzig. Euler initially dismissed it. In a 1736 letter, he wrote that the problem bore “little relationship to mathematics” and suspected it fell beneath serious analysis. But something gnawed at him. The problem resisted every tool of calculus, algebra, and classical geometry. It was not about distances or angles. It was about something else, something no existing mathematical language could articulate.
So Euler invented that language. He stripped away every irrelevant detail — the width of the river, the length of the bridges, the shape of the islands — and reduced the city to a diagram of points and connections. Landmasses became vertices; bridges became edges. What remained was the skeleton of a problem, and within that skeleton, the notion of an Euler path — a route traversing every edge exactly once — either existed or did not. Euler’s genius was not in finding the answer but in realizing the question needed a new framework to be asked properly.
Thinking in Shapes, Not Numbers
Before touching a single formula, consider what Euler actually did in human terms. Imagine you are handed a floor plan of a museum with many doorways connecting the rooms. Your task: walk through every doorway exactly once. You can start in any room. You can end in any room. But every doorway must be used precisely once — no skipping, no repeating.
Now forget the floor plan’s proportions and the size of the rooms. The only thing that matters is how many doorways each room has. If a room has an odd number of doorways, every time you enter through one, you leave through another, but eventually, you’ll get stuck entering with no unused exit or need to start there to avoid that trap. Euler realized that the parity of connections — whether each node has an even or odd number of edges — determines everything. This insight is the foundation of what mathematicians now call an Euler circuit, a closed route that traverses every edge exactly once and returns to its starting vertex.
The Königsberg bridge problem fails because all four landmasses have an odd number of bridges. In Euler’s framework, an Eulerian graph — one admitting a circuit that uses every edge exactly once — requires every vertex to have even degree. Königsberg’s graph has four vertices, each of odd degree. No circuit exists. No path exists either, because an Euler path (one that need not return to its starting point) requires exactly zero or two vertices of odd degree. Königsberg has four. The walk is impossible not because nobody tried hard enough but because the structure forbids it.
This was a revolution disguised as a recreational puzzle. For the first time, mathematics proved that a certain kind of task was inherently impossible — not practically difficult, but logically excluded by the architecture of connections. And the subject that Euler birthed in that moment, graph theory, now undergirds everything from social network analysis to airline route optimization.
From Intuition to Rigor — The Degree Theorem
Euler’s reasoning, laid out in his 1736 paper “Solutio problematis ad geometriam situs pertinentis,” follows a line of thought so clean that a modern reader can reconstruct it step by step. He begins with the handshake lemma, an observation so fundamental that it serves as the first theorem in virtually every graph theory textbook. If you sum the degrees of all vertices in a graph, the result equals twice the number of edges, because each edge contributes exactly one degree to each of its two endpoints. Written as a formula, if \( G \) is a graph with vertex set \( V \) and edge set \( E \), then \( \sum_{v \in V} \deg(v) = 2|E| \). This means the total degree is always even, which immediately implies that the number of vertices with odd degree must itself be even — you cannot have an odd number of odd-degree vertices in any graph.
From this base, Euler constructed the theorem that bears his name. A connected graph possesses an Euler trail — a walk that uses each edge exactly once — if and only if it has zero or two vertices of odd degree. When exactly zero vertices have odd degree, the trail closes into an Euler circuit: you end where you began. When exactly two vertices have odd degree, the trail must start at one and finish at the other. These are the only possibilities, because any graph, as the handshake lemma guarantees, cannot have exactly one or three odd-degree vertices.
To see why this works, consider what happens at any intermediate vertex during an Euler walk. Each time you arrive at a vertex, you must also leave it (unless it is the final vertex of your walk). This means every visit “uses up” two edges — one for arrival, one for departure. At an intermediate vertex, you therefore need an even number of edges. Only the starting and ending vertices of an open trail can afford to have odd degree, because at the start you leave without having arrived, and at the end you arrive without leaving. The degree condition captures exactly this constraint.
Formally, a connected graph \( G \) is Eulerian — meaning it admits an Euler circuit — if and only if every vertex \( v \in V(G) \) satisfies \( \deg(v) \equiv 0 \pmod{2} \). A connected graph admits an open Euler trail if and only if exactly two vertices have odd degree. The Königsberg graph has four vertices with degrees 3, 3, 3, and 5 — all odd. Since the number of odd-degree vertices is neither zero nor two, neither a circuit nor a trail exists. The proof is complete, and the citizens of Königsberg can stop searching.
What strikes a modern reader about this argument is its economy. No complicated machinery, no lengthy calculations — just a counting argument and a parity observation. Yet the theorem’s reach is enormous. The same logic that settled a Sunday strolling puzzle now determines whether a graph euler traversal is possible in networks with millions of nodes, from DNA fragment assembly in bio-informatics to circuit-board wire routing in electrical engineering.
What Kind of Truth Did Euler Discover?
Here is where the Königsberg problem becomes genuinely unsettling — not as mathematics, but as epistemology. Euler proved that no walk across the seven bridges could exist. He did not test every possible route. He did not survey the citizens of Königsberg for evidence. He proved it by reasoning about the abstract structure of connections. And that proof has remained valid for nearly three centuries, surviving the physical destruction of the bridges themselves (most were demolished or rebuilt during World War II). The city changed. The bridges vanished. The theorem stands. What kind of truth survives the annihilation of the physical world it originally described?
The most defensible reading of this situation, I believe, is that Euler discovered a fact about structure that was never dependent on the bridges at all. The bridges were a lens, not a source. The impossibility result belongs to the graph — an abstract object defined by incidence relations — and the graph exists (or subsists, as Russell would say of abstract objects that have being without existing in space or time) independently of any physical realization. Plato would have recognized this immediately: the bridges of Königsberg were shadows on the cave wall, and Euler turned to look at the Form itself — the pure relational structure that determines what traversals are possible.
But Imre Lakatos, the Hungarian philosopher of mathematics, would push back hard against this Platonic comfort. In Proofs and Refutations — first published as articles in 1963 and collected posthumously in 1976 — Lakatos argued that mathematical concepts do not arrive fully formed; they are shaped, stretched, and revised through a dialectical process of conjecture and criticism. The very definition of “graph” was not available to Euler in its modern form. He spoke of “paths” and “crossings” in natural language, and the formal apparatus of graph theory — vertices, edges, degree sequences — was constructed gradually by later mathematicians who refined, corrected, and extended Euler’s original insight. If the concept was built rather than found, can we honestly say it was waiting to be discovered?
I find the tension genuinely productive. The parity argument — the fact that an odd number of odd-degree vertices is impossible — feels discovered. It is a consequence of counting, and counting does not seem like a human invention. Two edges per visit is not a convention; it is a logical necessity. Yet the decision to model a city as a graph, to strip away geography and retain only connectivity, was an act of radical creative invention. Euler did not discover graphs in the riverbed of the Pregel. He invented a way of seeing, and through that invented lens, he discovered truths that appear to be eternal.
This duality — invention of framework, discovery of consequence — may be the deepest lesson of the graph Euler story. It suggests that mathematical truth is neither purely found nor purely made. It is found within structures that are made, and once those structures are articulated, the truths they contain become as stubborn and immovable as anything in nature. The bridges could be bombed. The theorem could not.
What is an Euler path in graph theory?
An Euler path (also called an Euler trail) is a route through a graph that visits every edge exactly once. A connected graph has an Euler path if and only if it contains exactly zero or two vertices of odd degree. If zero vertices have odd degree, the path forms a closed Euler circuit, returning to its starting vertex.
A Theorem Built Through Argument
Euler’s 1736 paper did not use the vocabulary of modern graph theory. He referred to landmasses and bridges, not vertices and edges. He presented his argument in Latin prose, mixing intuitive reasoning with flashes of combinatorial insight. And critically, he did not offer a complete proof by today’s standards. His argument for the necessity of the degree condition was convincing but informal; the sufficiency direction — proving that if the degree conditions are met, a trail actually exists — was left to later mathematicians.
Carl Hierholzer, a German mathematician, published the first rigorous constructive proof of sufficiency in 1873, more than a century after Euler’s original paper. Hierholzer’s algorithm provides a method for actually constructing an Euler circuit in any connected graph where every vertex has even degree: start at any vertex, follow edges (removing them as you go) until you return to the start, then splice in additional sub-circuits from any vertex that still has unused edges. The algorithm terminates precisely when all edges have been traversed — a beautiful constructive complement to Euler’s existential argument.
As documented in resources like Wolfram MathWorld’s entry on Eulerian paths, the modern formulation of these results requires careful treatment of connectivity. A disconnected graph with isolated vertices (vertices of degree zero) can still be considered Eulerian if its non-trivial component satisfies the degree condition — a subtlety Euler never addressed. The history of the theorem is thus a history of progressive clarification, of mathematicians arguing over edge cases and refining definitions until the result achieved its current crystalline form. Mathematics, here as everywhere, was built not by solitary geniuses issuing perfect decrees, but by communities of thinkers correcting and extending each other’s work across generations.
Legacy and Connections — From Bridges to Algorithms
The reach of Euler’s bridge problem across modern science and technology is staggering. In computer science, the existence of Euler trails is fundamental to algorithms for genome assembly, where DNA sequencing machines produce overlapping fragments that must be stitched together — a process modeled as finding Euler paths in de Bruijn graphs. In operations research, the Chinese Postman Problem asks for the shortest route that traverses every street in a city at least once — a direct descendant of the Königsberg question. In electrical engineering, Euler circuits determine whether a circuit board can be tested with a single continuous trace.
Graph theory itself, the field Euler inadvertently founded, has grown into one of the most active and applicable branches of mathematics. From Ramsey theory to network flows, from the four-color theorem to Google’s PageRank algorithm, the conceptual DNA of Euler’s 1736 paper runs through the discipline like the river Pregel through Königsberg. Every time you use GPS navigation, every time a social media platform suggests a connection, every time an epidemiologist traces the spread of disease through a contact network — Euler’s abstraction is silently at work, turning the mess of the physical world into a skeleton of vertices and edges that can be reasoned about with precision.The story of Euler and the bridges of Königsberg is only one thread in a much larger tapestry. To follow how a single insight can open an entire branch of mathematics, explore the rest of our Mathematics section.
The Open Question
Euler looked at a city and saw a diagram. He looked at bridges and saw edges. He looked at a practical question — can I take a pleasant Sunday walk? — and found, hiding inside it, a theorem that would outlast the city, the bridges, and the empire that contained them. The physical world offered the question. The abstract world held the answer. And the relationship between those two worlds remains, after three centuries, one of the deepest open problems in all of philosophy.
Here is what haunts me: the citizens of Königsberg walked those bridges for years, never finding the route, never proving it impossible. The impossibility was there the whole time — encoded in the parity of connections, written into the structure of the graph before anyone knew what a graph was. If a truth can exist before anyone articulates it, before anyone even has the language to express it — what else is out there, true and silent, waiting for the right pair of eyes?
References and Further Reading
Euler, L. “Solutio problematis ad geometriam situs pertinentis.” Commentarii Academiae Scientiarum Petropolitanae, 8 (1741), 128–140. Originally presented 1736.
Hierholzer, C. “Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren.” Mathematische Annalen, 6 (1873), 30–32.
Lakatos, I. Proofs and Refutations: The Logic of Mathematical Discovery. Cambridge University Press, 1976.
Wikipedia contributors. “Eulerian path.” Wikipedia, The Free Encyclopedia.
MIT OpenCourseWare. Mathematics for Computer Science, Graph Theory unit. Massachusetts Institute of Technology.
Weisstein, Eric W. “Eulerian Path.” MathWorld. Wolfram Research. mathworld.wolfram.com/EulerianPath.html
