The Bridges of Königsberg: How Euler Invented Graph Theory

Imagine you live in a beautiful 18th-century city threaded with rivers, and you've become obsessed with a puzzle your neighbors can't stop debating: is it possible to take a Sunday stroll that crosses each of the city's seven bridges exactly once, then return home? Not some bridges — all seven, each exactly once.

People in the city of Königsberg, Prussia, argued about this for years. Locals would try different routes, fail, try again, and eventually conclude that no route worked — but couldn't explain why it was impossible. That inability to explain the impossibility was the gap that mathematician Leonhard Euler stepped into in 1735, and what he produced in response wasn't just a solution to a local puzzle. It was the birth certificate of an entirely new branch of mathematics — one that now underlies how the internet routes your messages, how GPS finds your fastest path home, and how scientists reassemble the human genome from millions of tiny fragments.

The Concept

Königsberg — known today as Kaliningrad, Russia — sits on the Pregel River, which splits into two branches as it flows through the city. This creates two islands at the city's center: Kneiphof and Lomse. Seven bridges connected the various landmasses: the north bank, the south bank, and the two islands.

The question was whether you could walk a route crossing every bridge exactly once and return to your starting point. Simple to state. Maddening to solve by trial and error. And that difficulty is itself the clue: not every puzzle that looks like a routing problem is one.

Enter Leonhard Euler. Born in Basel, Switzerland in 1707, Euler would become one of the most prolific mathematicians in history — eventually authoring around 866 papers and books. When the Königsberg puzzle reached him, it was framed almost apologetically, as a trivial diversion from serious mathematics. Euler politely disagreed about the "trivial" part.

His great move was abstraction. Rather than studying the actual geography — the distances, the appearance of the bridges, the width of the river — he replaced each landmass with a point and each bridge with a line connecting two points. What was a city map became a diagram: 4 points (vertices) connected by 7 lines (edges).

What mathematicians now call a graph.

This might sound like a small technical step. In 1735, it was a philosophical revolution. For the first time, someone was proposing to study a pattern of connections independent of all physical details. Not the distances, not the shapes — just: what is connected to what, and how many times?

Why It Matters

Once Euler had his abstract graph, the key insight followed almost immediately.

Think carefully about what happens as you walk across bridges. Every time you enter a landmass, you use one bridge. Every time you leave, you use another. If you're simply passing through a landmass — entering and exiting without stopping there permanently — you use bridges in pairs: one in, one out. This means any "middle stop" in your walk must connect to an even number of bridges.

Only the start and end of your walk get special treatment. At the start, you leave without having arrived; at the end, you arrive without leaving. So at most two landmasses can have an odd number of bridges — the start and the finish. And if you want a round trip that returns you to where you began, even those must be even.

Now look at Königsberg's four landmasses:

The north bank connects to 3 bridges (odd)
The south bank connects to 3 bridges (odd)
Kneiphof island connects to 5 bridges (odd)
Lomse island connects to 3 bridges (odd)

Every single landmass has an odd number of bridges. For the walk to be possible, you need at most two. Königsberg has four. The walk is not merely difficult — it is provably impossible for any walker who has ever lived or ever will live, regardless of how clever their route or how long they're willing to try.

Euler published this proof in a 1741 paper titled Solutio problematis ad geometriam situs pertinentis — "The solution of a problem relating to the geometry of position" — presented to the St. Petersburg Academy in 1735. And buried in the proof was something far more valuable than the answer to a puzzle: a universal theorem.

An Eulerian path — a route through a graph that traverses every edge exactly once — exists if and only if the graph has zero or exactly two vertices with an odd number of edges. Zero odd-degree vertices means you can complete a loop returning to the start. Exactly two means you can traverse every edge with a different start and end point. Anything more means no such path exists.

This was the first theorem in graph theory. It's still taught in every discrete mathematics course in the world.

The Details

What Is a Graph, Really?

In modern mathematics, a graph has nothing to do with charts or plotted functions. It's simply a collection of vertices (points) and edges (connections between pairs of points). That's the entire definition.

The vertices might represent cities, web pages, people, genes, neurons, airports, proteins, or electrical components. The edges might represent roads, hyperlinks, friendships, chemical bonds, airline routes, synaptic connections, or power lines. The underlying mathematics is identical in every case.

This austere abstraction — just dots and lines — captures the structure of an enormous fraction of the world's interesting complexity. And it all descends from a philosopher's puzzle about Sunday afternoon walks.

The Internet as a Graph

Every router on the internet is a vertex. Every physical cable or wireless link between them is an edge. When data packets travel from a server in one country to your phone in another, graph algorithms decide the fastest path through tens of thousands of connected devices.

The most famous of these algorithms — Dijkstra's shortest-path algorithm, invented in 1956 — finds the minimum-weight path between any two vertices in a graph in a matter of milliseconds, even for graphs with millions of nodes. Every time you load a web page, something very close to Euler's framework is working on your behalf.

GPS Navigation

Your navigation app models the road network as a weighted graph: intersections are vertices, road segments are edges, and each edge carries a weight representing travel time or distance. Finding your fastest route is a shortest-path computation on this graph. The fact that it runs on your phone in under a second — for a graph containing millions of intersections — is a triumph of the graph-theoretic ideas Euler planted in 1735.

Social Networks and Six Degrees

Every person on a social platform is a vertex. Every friendship, follow, or professional connection is an edge. The famous "six degrees of separation" claim — that any two humans on Earth are connected through at most six mutual acquaintances — is a mathematical statement about the diameter of the human social graph.

Graph algorithms detect communities within these networks, identify influential nodes (influencers), predict which connections you're likely to form next (friend recommendations), and model how information — or misinformation — propagates through populations. The Facebook social graph, with over three billion vertices, is one of the largest graphs ever constructed.

PageRank and the Web

Google's original search algorithm, PageRank, treated the entire web as a directed graph — pages as vertices, hyperlinks as directed edges. The algorithm computed the "importance" of each page based on how many other important pages linked to it, through a process of iterative computation on this graph. The entire modern search industry — now worth hundreds of billions of dollars — emerged from a graph-theoretic insight about connected documents.

DNA Sequencing

Perhaps the most surprising application: when scientists sequence a genome, they obtain millions of short DNA fragments (called reads) and must reassemble them into a continuous sequence. This is, at its mathematical core, a graph problem.

The fragments become vertices; overlapping sequences between fragments become edges. Reconstructing the genome means finding a path through this graph that visits every fragment in the right order. Researchers use a structure called a de Bruijn graph, and the reconstruction exploits Eulerian-path ideas — the same ideas Euler described when proving that Königsberg's walk was impossible. The genome you carry in every cell has, in a real sense, been read using mathematics invented by a man who lived three centuries before DNA's discovery.

The Geometry of Position

Euler called his approach geometria situs — the "geometry of position." Classical geometry cared about measurement: lengths, angles, areas, volumes. Euler was proposing something entirely different: a geometry that discards measurement and studies only the pattern of connections.

Whether Königsberg's bridges were long or short, stone or wood, beautiful or plain — none of that entered his analysis. Only the pattern of connections mattered. This idea seeded two massive mathematical fields: graph theory itself, and topology — the study of shapes that can be deformed continuously without tearing. Both trace their lineage to Euler staring at a city map and asking: what is the essential structure here, stripped of everything accidental?

The Bridges Today

The city of Königsberg was devastated in World War II. Allied bombing in 1944 and the Battle of Königsberg in 1945 destroyed much of the city, including several of its famous bridges. The Schmiedebrücke (Forge Bridge) and Köttelbrücke were destroyed and never rebuilt. The city was transferred to Soviet control and renamed Kaliningrad in 1946.

Of the original seven bridges Euler analyzed, only a few survive in any form today. The physical puzzle has dissolved. The mathematical framework derived from that puzzle now runs on every smartphone, every router, every genome sequencer on the planet.

The abstraction outlasted the thing it abstracted.

Takeaways

Graph theory was born from a city puzzle in 1735: Euler proved no walk could cross all seven of Königsberg's bridges exactly once because all four landmasses had an odd number of bridges — and a valid route requires at most two such "odd" points.

The key move was abstraction: By replacing geography with a pattern of vertices and edges, Euler created a framework that describes any network of connections, from neural circuits to social media.

The fundamental theorem: An Eulerian path exists if and only if a graph has zero or exactly two vertices with odd degree. This result, nearly three centuries old, remains one of the most useful in all of discrete mathematics.

Graph theory now powers modern civilization: Internet routing, GPS navigation, social network analysis, search engine ranking, and DNA genome sequencing all rely on the mathematical ideas Euler invented by thinking carefully about bridges.

The deepest lesson is about how to think: Euler didn't find a clever route — he found the mathematical reason no route could exist. He changed what question he was asking, and that changed everything. When a problem resists brute force, step back and ask: what is the true structure here?