Seven bridges, and the invention of throwing things away

Königsberg in the early eighteenth century sat on both banks of the river Pregel, which split around an island before rejoining. Seven bridges connected the four resulting landmasses. The question, apparently a genuine local amusement, was whether a walk existed that crossed every bridge exactly once.

The problem has the shape of a puzzle and none of the usual escape routes. It is not a trick question, there is no bridge that can be crossed twice on a technicality, and the number of bridges is small enough that the answer feels as though it ought to be findable by persistence.

Nobody could find such a route. That is weak evidence — plenty of things are hard to find and exist anyway — and there are only so many orders in which seven bridges can be crossed, so someone patient enough could in principle have settled it by exhaustion.

Euler did something better in 1736, and what he did is more interesting than the answer he got. He proved no such route exists — but he proved it by first deciding that almost everything about the problem was irrelevant, which is a move the gluing diagram of a Möbius band makes in the same spirit. He proved no such walk exists, by an argument that never mentions a bridge.

Delete the city #

The first move is the one that matters, and it consists of noticing everything the problem does not depend on.

The width of the river is irrelevant. So is the length of each bridge, the distance between them, the shape of the island, which bank is north, and the entire geography of the city. A walker on the island who wants to reach the north bank has a certain number of bridges available, and nothing else about the situation affects the answer.

What is left after deleting the irrelevant parts:

This is a graph, and Euler’s paper is generally counted as the first in graph theory. What makes it foundational is not the theorem but the act of abstraction: the recognition that a whole class of questions depends only on what is connected to what, and that everything else can be thrown overboard without loss.

Euler himself was slightly apologetic about it. He opens the paper by noting that the problem concerns neither magnitude nor calculation, and therefore appears to belong to no branch of mathematics then recognised — before suggesting it might belong to what Leibniz had speculatively called the geometry of position. He was inventing the subject and knew it, which is rarer than the histories usually suggest; most foundational papers are recognised as foundational only afterwards.

One more thing is thrown away, and it is easy to miss: the identity of the bridges. The proof never asks which bridge is which, only how many meet each landmass. Two graphs with the same degree sequence and the same connections behave identically, whatever their edges are called. Discarding names as well as geometry is what makes the result a theorem about a class of objects rather than an observation about one city. It is also what makes the result reusable: the same count settles whether a plotter can draw a figure without lifting the pen, whether a street-sweeping route can avoid repeating itself, and whether a sequence of dominoes can be laid end to end. None of those problems mentions a bridge, and every one of them is this same problem, wearing a different set of clothes and answered in every case by the same count of odd degrees.

The parity argument #

Now the proof, which takes one observation.

Consider any landmass that is not the start or the end of the walk. Every time the walk arrives there, it must subsequently leave — otherwise it would have ended there. So the bridges at that landmass are used in pairs: one to come in, one to go out. Since every bridge is used exactly once, the number of bridges meeting that landmass must be even.

The start and the end are the two exceptions. The start has an unmatched departure at the beginning; the end has an unmatched arrival. Each of those can be odd. If the walk begins and ends at the same place, even they must be even.

So a walk using every edge exactly once requires: either zero or exactly two vertices of odd degree. Not one, not three, not four.

Königsberg has four vertices, and their degrees are 3, 3, 3 and 5. Every one of them is odd. So no such walk exists — and the argument never needed to consider a single candidate route.

The counting is the entire proof, and it settles infinitely many cities at once. Any arrangement of bridges whatever can be checked by listing degrees and counting the odd ones.

What the impossibility proof actually delivers #

An exhaustive search would have established that no walk exists in Königsberg. Euler’s argument establishes considerably more: why none exists, what would have to change for one to exist, and what the answer is for every other city.

That is the difference between verification and understanding, and it is worth being precise about. A search confirms a fact about one object. The parity argument identifies the property responsible — a property that can be checked in a moment, that generalises to any graph, and that immediately answers the follow-up questions. How many bridges would need to be added to make the walk possible? One, joining two of the odd landmasses, which would leave exactly two odd vertices. Which two? Any two, and the walk then has to start at one of the remaining odd ones and finish at the other.

None of that comes out of a search.

The condition turned out to be sufficient as well as necessary, though Euler only proved the necessary half and rather breezily asserted the rest. The full proof — that a connected graph with zero or two odd vertices always has such a walk — was not published until Carl Hierholzer’s in 1873, over a century later. This is a common shape for a result: the obstruction is found quickly because it only requires exhibiting a reason for failure, and the construction takes much longer because it requires handling every case that does not fail.

The search Euler did not run #

Königsberg is small enough that the brute-force route really was available, and it is worth running, because the comparison is the entire case for the abstraction.

A walk over seven bridges is an ordering of the seven together with a choice of where to begin. Enumerating all $7! = 5040$ orderings from each of the four landmasses, and discarding at each step any that asks the walker to set off from somewhere they are not standing, returns zero valid routes. The theorem and the exhaustion agree, as they must. The exhaustion took a few thousand operations; the parity count took four.

Run the same search on the modern city of the postscript below — five bridges, two of them lost — and it returns twelve walks. That is also what the theorem predicts, and it predicts it more sharply than a bare count suggests: the two odd landmasses there are the north and south banks, and all twelve walks begin at one bank and end at the other, six in each direction. Not one of them starts on the island or the eastern spit, and no search was needed to know that.

The gap between the two methods is the point, and at seven bridges it is invisible. Checking parities costs one pass over the edges. Searching costs a factorial: at seven bridges that is five thousand orderings and no machine notices, at twenty bridges it is $2.4 \times 10^{18}$ and no machine finishes, and the parity check is still one pass over twenty edges. The abstraction turned a problem whose cost grows faster than any exponential into one that grows linearly, and it did it by discarding everything except a count.

It is worth being exact about what that buys. The parity test answers whether. It does not hand over a route — Hierholzer’s construction does that, and it also runs in a single pass. What has no such shortcut is the neighbouring question of visiting every landmass once rather than every bridge, and the absence is not for want of looking: no comparable test is known, and finding one would settle the largest open problem in the subject.

Why three odd landmasses is not a possible city #

The condition says zero or two odd vertices. It is natural to read that as a rule that happens to exclude one, three and four, and to wonder what is special about the numbers it allows. Nothing is: one and three were never available.

Add up the degrees of every vertex in any graph whatever. Each edge has two ends, and each end contributes 1 to the degree of the vertex it touches, so the total is exactly twice the number of edges — necessarily even. Königsberg checks out: $3 + 3 + 3 + 5 = 14 = 2 \times 7$, and there are seven bridges.

Now split that sum into the even-degree vertices and the odd-degree ones. The even ones contribute an even total. The whole sum is even. So the odd ones must contribute an even total too — and a collection of odd numbers adds to an even total only if there are an even number of them.

Odd-degree vertices come in pairs, always, in every graph. There is no arrangement of bridges anywhere, of any size, with exactly one odd landmass, or three, or any odd number.

That is the handshake lemma, usually stated as the observation that at any party the number of people who have shaken hands an odd number of times is even. It is the first result in graph theory after the definitions, and it tightens Euler’s theorem considerably. The possible counts of odd vertices are $0, 2, 4, 6, \ldots$; the walk exists for the first two and fails for all the rest. So the condition is not a narrow window in a wide range of possibilities. It is the bottom two rungs of the only ladder there is.

It also retroactively explains the shape of the argument. The proof needed the start and the end to absorb the two unmatched edges, and it needed exactly two of them because unmatched edges are the odd degrees and those cannot be produced singly. The theorem’s asymmetry — why two exceptions rather than one or three — is not a feature of walks at all. It is a feature of edges having two ends.

Euler’s paper contains no graph #

There is an awkward fact behind the standard telling, and it is worth stating on a site whose whole premise is that the picture is the argument.

Euler’s 1736 paper has no picture of four dots and seven lines in it. It has a map of the city, and then it has letters. He labels the four landmasses $A$, $B$, $C$, $D$, labels the bridges $a$ through $g$, and reasons about sequences of letters: a walk crossing seven bridges is a string of eight capitals, and the question becomes how many times each capital can appear in it. The counting argument about how often $A$ must occur, given how many bridges touch it, is entirely symbolic.

The graph — the drawing that every retelling opens with, including this one — is a later reconstruction. The vertex-and-edge diagram in the modern sense took another century and more to become standard notation, and the paper credited with founding graph theory contains nothing that would now be recognised as a graph.

That is not a debunking. Euler’s abstraction is exactly as radical as advertised; he did throw the geography away and keep only what touches what. He simply expressed the result in letters, because the notation for expressing it in dots had not been invented, and inventing it was not the part of the problem he was working on.

The lesson runs against the grain of a figure-first collection, and is better for it. The picture here is not what made the discovery possible — the discovery preceded the picture by a hundred years. What the picture does is make the finished argument cheap to hold, and that is a different service and a real one. A diagram can be the best way to carry an idea without having been the way anyone arrived at it, and it is worth not confusing the two.

What the picture cannot show #

The graph makes the parity argument obvious and hides the harder half of the theorem completely.

Counting odd degrees shows that a walk cannot exist when four vertices are odd. It does not show that a walk does exist whenever zero or two are — and that converse is a genuinely different kind of claim, requiring a construction rather than an obstruction. Euler asserted it; Hierholzer proved it 137 years later. The picture gives no clue that anything is missing, which is a good general warning: a diagram that settles an impossibility often looks as though it has settled the possibility too.

Connectivity is the other thing the count cannot see. Two separate graphs, each with all degrees even, have no walk between them, and no amount of degree-counting notices. The condition has to carry “and the graph is connected” as a separate clause that the parity picture simply does not contain.

The ladder from here #

Later rungs: Hierholzer’s construction, drawn as a walk that splices in loops as it goes. Hamiltonian paths, which look like a small variation and are computationally brutal — the difference between an easy problem and a hard one, visible in two nearly identical pictures. The Chinese postman problem. Planarity, and Kuratowski’s two forbidden graphs. Euler’s formula for polyhedra as the same invariant in another setting. Graph colouring and the four-colour theorem. Trees, spanning trees, and shortest paths. And the adjacency matrix, where a graph becomes a grid of numbers and its powers count walks.

Postscript: the city, and the bridges #

Königsberg is now Kaliningrad. Two of the seven bridges were destroyed by bombing in 1944 and never rebuilt, two more were replaced by a modern highway, and the configuration today has an Eulerian path — it is possible to walk it, starting and ending on the two banks.

The mathematics outlasted the object it was about, and then the object changed to satisfy it, by accident.

The move, elsewhere #

Deleting the parts of a problem that do not matter is the most portable technique in the essay collection, and it is worth naming as a technique rather than a trick. It is also the hardest to teach, because it consists of a judgement — knowing what the question depends on — rather than a procedure. Slicing a cone throws away four separate equations and keeps one surface; the gnomon throws away arithmetic and keeps a shape.

A matrix becomes a picture of a deforming grid by throwing away the numbers and keeping the geometry, and its determinant throws away almost everything and keeps only the area factor. Ulam’s spiral throws away every property of the integers except primality and their position in a spiral, and something unexpected survives. A Möbius band is studied by discarding all its measurements and keeping only how it is glued.

The skill is not the deleting. Anyone can delete. The skill is knowing what the question depends on — and the only real test of that judgment is whether the answer survives.

Euler kept four dots and seven lines. It was enough.