Königsberg Bridge Problem: Euler's 1736 Proof

The Puzzle That Stumped a City

In the 1700s, Königsberg was the beating heart of East Prussia. The city sat on the banks of the Pregel River, a thriving port and trading hub, one of the most cultured corners of the Baltic world. It was a place of merchants, scholars and busy river traffic.

But it had a peculiar geography. The city was built across two large islands, and those islands were tied to each other, and to the north and south banks of the Pregel, by a total of seven bridges. Seven crossings. That was the whole layout, and it was about to drive the whole town a little bit crazy.

Here is the game the residents played. Could you set out on a walk that crossed each of the seven bridges exactly once, and no bridge twice? Not a sprint, not a shortcut, just one clean loop through every crossing. It sounds simple when you say it out loud. It is not.

The puzzle spread fast. It became a genuine local obsession, the kind of thing people argued about over drinks and sketched out on scraps of paper. And for a long time, nobody could crack it.

Why the Königsberg Bridge problem would not budge

The trouble was that every attempt either skipped a bridge or repeated one. People kept producing near-misses, routes that worked right up until the final crossing, and then collapsed. The city had a riddle that refused to be solved by walking around and hoping.

It took an outsider to see it clearly. In the mid-1730s, the Swiss mathematician Leonhard Euler (1707 to 1783) turned his attention to the problem, and he did something nobody had thought to do. He threw away the map.

That was the real move. To Euler, the size of the land masses did not matter. The length of the bridges did not matter. The only thing that counted was which piece of land connected to which, and how many crossings touched each one. Strip away everything else, and the city becomes a handful of dots joined by lines.

Euler laid it out as a simple diagram. Each of the four land areas became a point, and each bridge became a line or curve linking two of those points. That sketch is often described as the first known example of what we now call a graph, though historians treat that label as a simplification rather than a settled fact.

What Euler proved was decisive. No such walk existed. The people of Königsberg had been chasing something that was never there, and the reason was hiding in plain sight in the connections themselves.

The city has changed hands and names since. Königsberg is now Kaliningrad, and it sits within Russia's borders, a far cry from the Prussian trading town that once puzzled its own residents with seven simple bridges.

Euler's Simple Idea That Changed Everything

By the mid-1730s, the puzzle of the Königsberg Bridge problem had been argued over in parlors and taverns for years, and nobody could settle it. Then a Swiss mathematician named Leonhard Euler (1707 to 1783) stepped in and published his solution in 1736. His answer was blunt and final: no such walk through Königsberg existed. What many residents had only guessed at, Euler proved.

But Euler was not really chasing a party trick. What fascinated him was that the puzzle could serve as a model for far harder questions. So he stripped the city down to its bones. The geography of the map? Irrelevant. How big the landmasses were? Irrelevant. The physical dimensions of the bridges? Also irrelevant. The only thing that mattered was how the regions connected to one another.

Out of that insight came a drawing so plain it hardly looks like mathematics. Euler reduced the whole city to a handful of points and the links between them. No compass, no scale, no river. Just the bare pattern of what touched what.

That diagram is widely regarded as the first known example of what we now call a graph, though historians treat that label as a common simplification rather than settled fact. Either way, the move itself was the revolution: Euler had shown that you could throw away everything except the pattern of connections and still answer the question completely.

From a Puzzle to a Field: How Graph Theory Grew

Euler's 1736 analysis of the Königsberg Bridge problem did more than settle a walking route. It handed mathematics a new way of seeing, and within a few generations that way of seeing had a name, a vocabulary, and a growing crowd of practitioners.

The honest version of the story is not a straight line from Königsberg to the modern textbook. It is widely repeated that graph theory sat dormant for roughly a century after Euler, but that framing oversimplifies things. There was a relative lull, a stretch where the ideas Euler had sharpened were not pushed much further, yet the field was not asleep. Interest simply gathered slowly, then picked up speed as the 19th century wore on and more mathematicians found reasons to care about points and the lines joining them.

Two Englishmen did much of that gathering. In 1878, the term "graph" itself entered the language through James Sylvester. Around the same period, Arthur Cayley produced work on graphs that mathematicians still rank among the most important results the field has. So the vocabulary and some of the deepest early structure arrived in the same century, from the same country, and largely independently of the bridge puzzle that started it all.

Then the 20th century changed the scale of the question. Graph theory grew into one of the branches of mathematics with the widest reach into other scientific fields, and the reason is simple: networks are everywhere. The internet is the cleanest example. Model it as one enormous graph and every web page becomes a node, every hyperlink an edge running between them. The same skeleton describes social networks, transportation routes, and the wiring inside a cell.

What Euler proved in Königsberg was that the shapes and distances on a map can be thrown away entirely. Only the pattern of connections matters. That single move, made in 1736 while answering a puzzle about seven bridges, is why a city in old Prussia still sits at the front of every graph theory course.

Euler Paths, Euler Circuits, and the 1873 Proof

Count the edges touching a single vertex and you have its degree. That one number decides everything about whether a walk can cross every edge of a graph exactly once. In graph theory, the degree of a vertex is simply the number of edges connected to it, and it is the hinge on which the whole Königsberg Bridge problem turns.

An Euler path is a walk that crosses each edge of a graph exactly once. You are allowed to pass through the same vertex more than once along the way, so the rule is about edges, not about territory. If that walk happens to finish on the very vertex where it started, it gets a different name: an Euler circuit. Same idea, one extra condition tacked on at the end.

Leonhard Euler (1707 to 1783) first put these concepts on paper in 1736, while he was picking apart the seven bridges of Königsberg. He had already shown that no such walk existed across those bridges. What he built to prove it was something bigger: the vocabulary of paths and circuits that outlived the puzzle itself.

Then came the condition. For a graph to hold an Euler circuit, two things must be true. The graph has to be connected, and every one of its vertices has to sit at an even degree. Euler showed that this requirement is necessary. He also claimed it was sufficient, meaning that even degrees alone guarantee the circuit exists. He did not prove that second half.

The gap sat open for well over a century. The complete mathematical proof of sufficiency finally arrived in 1873, published by Carl Hierholzer. Once that proof landed, the result could be stated cleanly and completely, and it is how we state it today. Euler's theorem says a graph has an Euler circuit if and only if it is connected and all of its vertices have even degree.