A Sunday Stroll That Changed Mathematics
In the summer of 1736, the citizens of Königsberg — a prosperous Prussian city built on the banks of the Pregel River — had a puzzle they couldn't solve. The city was divided into four landmasses connected by seven bridges, and the question was simple: could you take a walk through the city, crossing each bridge exactly once?
Simple to ask. Maddeningly hard to answer by just trying. You'd set out from the island in the middle, cross one bridge, then another, and for a while it would feel like you were getting somewhere. Five bridges down, two to go — surely this time you'd make it. But then you'd find yourself stuck: the only uncrossed bridges were on the other side of the river, and there was no way to reach them without recrossing one you'd already used.
People tried starting from different spots. They tried going north first instead of south, or taking the bridges in various orders. Nobody could do it, but nobody could prove it was impossible either. It was the mathematical equivalent of a locked room mystery: everyone was sure something was wrong, but no one could find the body.1
Enter Leonhard Euler, the most prolific mathematician who ever lived — a man who published so many papers that the journal of the St. Petersburg Academy was still printing his backlog twenty years after he died. Euler heard about the Königsberg problem and recognized something that the Sunday strollers didn't: the answer had nothing to do with geography.
The Trick: Stop Looking at the Map
Here's the move that Euler made — the one that turned a local puzzle into a whole new branch of mathematics. He said: forget the map. Forget the shape of the riverbanks, the distance between the bridges, whether they curve left or right. None of that matters.
What matters is the connections. The island connects to the north bank by two bridges. The island connects to the south bank by two bridges. The island connects to the east bank by one bridge. The north bank connects to the east bank by one bridge. The south bank connects to the east bank by one bridge.
That's it. That's the entire problem. You can throw away the map and replace it with dots and lines.2
This was a genuinely radical act. Euler didn't solve the Königsberg bridge problem in the way that people expected — by finding a clever route. He dissolved it. He showed that the problem belonged to a completely different category of mathematics than anyone had imagined, one where the only thing that mattered was the abstract structure of connections. He had invented what we now call graph theory.3
The Birth of Topology, Too
Euler didn't know it, but he was also laying the foundations of topology — the study of properties that survive stretching, bending, and deforming. When Euler said "the shape of the riverbanks doesn't matter," he was making a topological argument. Two cities with different maps but the same connection structure are, for this problem, the same city. It took another century before mathematicians realized this idea deserved its own field.
The Parity Argument
So Euler has his dots and lines — his graph, in the terminology that would come later. Now he needs to figure out: when can you trace all the lines without lifting your pen and without retracing?
Think about what happens when your path passes through a node. You arrive on one edge and leave on another. That's two edges used up. If you pass through the same node again later, that's two more edges. Every time you pass through a node, you consume edges in pairs.
This means that for any node in the middle of your path — one that's neither the start nor the end — the number of edges touching it must be even. If a middle node had an odd number of edges, you'd eventually arrive there with no unused edge to leave on. You'd be stuck.
What about the start and end nodes? The start node uses one edge when you first leave it (unpaired), and then pairs after that. So the start node can have an odd number of edges. Same logic for the end node.
Euler's Theorem on Traversability
A graph has an Euler path (crossing each edge once) if and only if it has at most 2 nodes with odd degree.
If it has exactly 0 odd-degree nodes, you can make a circuit — ending where you started. If it has exactly 2, you must start at one odd node and end at the other.
Now count the odd nodes in Königsberg: North bank has degree 3 (odd). South bank has degree 3 (odd). The island has degree 5 (odd). The east bank has degree 3 (odd). That's four odd-degree nodes. You're allowed at most two. The walk is impossible.4
And just like that — no trial and error, no exhaustive search, no "try harder" — the impossibility is proven. This is what mathematicians mean when they talk about the power of proof. A thousand failed attempts might make you suspect something is impossible; a proof makes it certain.
The Bridge Crossing Puzzle
Don't take Euler's word for it. Try to cross all seven bridges yourself. Click on a landmass to start, then click adjacent landmasses to walk across bridges. After you've convinced yourself it's impossible, try the modified versions where we add or remove a bridge to make it solvable.
Degrees of Freedom
The beautiful thing about Euler's argument is that it doesn't just solve one puzzle — it solves an infinite family of puzzles, all at once. Give me any map of any city with any number of bridges, and I can tell you in seconds whether an Euler path exists: just count the degree of each node and check how many are odd.
This is what good mathematics does. It doesn't just answer the question in front of you; it answers every question shaped like the question in front of you.
The citizens of Königsberg wanted to find a path. Euler did something better: he found a reason.
And the reason generalizes. An Euler circuit — a path that crosses every edge exactly once and returns to the start — exists if and only if every node has even degree. No exceptions allowed, because now the start node is also the end node, and every visit must pair its edges perfectly.
Drawing Without Lifting Your Pen
You've probably encountered a version of this as a party trick: can you draw this shape without lifting your pen? The "house envelope" puzzle, for instance — a square with an X through it and a triangle on top. Try it. You can do it if you start in the right place (one of the bottom corners), because those are the two nodes with odd degree.5
Here's a tool to explore this on your own. Draw any graph — place nodes with a click, connect them by dragging — and the algorithm will instantly tell you whether an Euler path or circuit exists.
The Other Traversal Problem
There's a cousin of Euler's question that looks almost identical but is monumentally harder. Instead of crossing every edge once, what if you want to visit every node once?
This is the Hamiltonian path problem, named after William Rowan Hamilton, who in 1857 sold a puzzle based on it — the "Icosian game," where you had to find a route visiting every vertex of a dodecahedron exactly once. (It sold poorly. Victorian parlor game consumers apparently had taste.)6
The maddening thing is that there's no elegant parity argument for Hamiltonian paths. No simple criterion like "count the odd-degree nodes." In fact, determining whether a graph has a Hamiltonian path is NP-complete — it's one of the hardest problems in the hardest class of problems in computer science. The best known algorithms, for general graphs, essentially require you to try an exponential number of possibilities.
The most famous version of the Hamiltonian problem is the Traveling Salesman Problem (TSP): given a list of cities and the distances between them, what's the shortest route that visits each city exactly once and returns home? Every delivery company, every circuit board manufacturer, every genome sequencer faces some version of this problem. And as far as we know, there's no fast algorithm to solve it perfectly — though approximation methods get surprisingly close. If you could prove whether P = NP (that is, whether every problem whose solution can be checked quickly can also be found quickly), you'd win a million dollars from the Clay Mathematics Institute.
The contrast is striking. Euler paths: easy to check, elegant theory, solved in 1736. Hamiltonian paths: brutally hard, no clean characterization, still unsolved in any deep sense nearly 300 years later. Two problems about tracing routes through graphs, and one is trivial while the other might be forever intractable. Mathematics is not fair.
Graphs EverywhereThe World Is a Graph
Euler couldn't have known what he was starting. The "dots and lines" he invented to think about bridges turn out to be the right way to think about an astonishing range of real-world systems.7
Social networks are graphs: people are nodes, friendships are edges. Facebook's social graph has billions of nodes. The "six degrees of separation" conjecture — that any two people on Earth are connected by at most six friendship links — is a statement about the diameter of a graph.
The internet is a graph: routers are nodes, cables are edges. When your data packet travels from your laptop to a server in Virginia, routing algorithms are finding paths through an enormous graph in real time.
Google Maps is running graph algorithms every time you ask for directions. Intersections are nodes, road segments are edges (weighted by time or distance), and Dijkstra's shortest-path algorithm — a direct descendant of Euler's thinking — finds your route.
Your brain is a graph: roughly 86 billion neurons connected by trillions of synapses. Neuroscience increasingly uses graph-theoretic tools to study everything from memory formation to the structural basis of consciousness.
The Petersen graph — a specific ten-node graph discovered in 1898 — has become the go-to counterexample in graph theory, the mathematical equivalent of "have you tried turning it off and on again." Need to disprove a conjecture about graphs? Check the Petersen graph first. It's probably a counterexample. It has no Hamiltonian cycle, it's not planar, and it defies almost every generalization you try to make about well-behaved graphs.8
Coloring and Planarity
One of the most famous problems in graph theory is the four-color theorem: any map can be colored with at most four colors such that no two adjacent regions share a color. This is a graph theory problem in disguise — regions are nodes, shared borders are edges, and you're asking about the chromatic number of a planar graph.
The four-color theorem was finally proved in 1976 by Kenneth Appel and Wolfgang Haken, but only with the help of a computer that checked 1,936 special cases. It was the first major theorem proved by computer, and it sparked a philosophical crisis: is a proof that no human can verify really a proof? Mathematicians are still arguing about this.
The LessonThe Power of Impossibility
There's something almost paradoxical about the Königsberg story. Euler's great achievement was proving that you can't do something. He didn't build a bridge or find a path; he showed, with absolute certainty, that no path exists.
But this negative result was more productive than any solution could have been. If someone had found a clever route across the seven bridges, that would have been a fun fact about one particular city. By proving it impossible, Euler created an entire theory — a framework that explains not just Königsberg but every possible graph, every possible network, every possible pattern of connections.
The most important mathematical results are often the ones that tell you what can't be done — because the reasons why illuminate the structure of what can.
This pattern repeats throughout mathematics. Gödel's incompleteness theorems (you can't prove everything that's true), the halting problem (you can't predict whether every program terminates), Arrow's impossibility theorem (you can't design a perfect voting system) — the impossibility results are the ones that reshape our understanding of what's possible.
The citizens of Königsberg wanted a walking tour. What they got, thanks to one mathematician's willingness to step back and think abstractly, was the foundation of an entire branch of mathematics — one that now underpins the technology, infrastructure, and social networks that connect our world.
Not a bad outcome for a Sunday stroll that never happened.