The Bridges of Konigsberg: How a Walk Invented Graph Theory

On a wet Saturday I drew a city on the back of a receipt: a river splitting around an island, seven little dashes for bridges, and a promise that has been made in that city for three hundred years. Cross every bridge exactly once. Start anywhere, finish anywhere. My ten-year-old counted the dashes with her finger, traced two routes, crossed both out, and said the sentence every parent wants to hear in a completely different situation: I do not think it can be done.

She was right, and she had walked straight into the problem that started graph theory. In 1736 the Prussian city of Konigsberg sat across the river Pregel, with two islands in the water and seven bridges joining the four pieces of land. Visitors were challenged to make the round, and nobody could. Nobody could say why, either. Leonhard Euler, already one of the most productive mathematicians alive, treated it as a serious question and sent back an answer that fits on a postcard. The people who like to complain that school math never touches real thinking have not spent time with the genuine history of math, where a Sunday puzzle becomes a whole branch of the subject.

Seven bridges and a promise nobody could keep

The map is the easy part. There are four places to stand, and what matters is how many bridges leave each one. The two banks of the river have three apiece, the small eastern island has three, and the middle island has five, because two channels meet around it.

Read that last row again, because it is the whole trick, and it is the kind of detail a nine-year-old can check on the receipt with a pencil. Every bridge has two ends, so the ends have to balance against the land. Four places, fourteen ends, and the arithmetic works out exactly.

Euler's real move: stop measuring, start counting

The obvious attack on this puzzle is to get better at walking. Draw the routes, remember which bridges are used, try again. Euler went the other way. He noticed that the length of a bridge, the shape of the island, and the width of the river never enter the problem at all. Two routes that look completely different are the same route the moment they connect the same places in the same order.

So he threw away almost everything on the map. What survived was a short list of positions and the connections between them, which is the object we now call a graph, though that word arrived long after Euler. He called the subject he was starting the geometry of position, and the name is honest about what changed: measuring where things are, taught in every shape and space lesson, is a different activity from counting how things are attached.

This is the moment a child can be let in on something adult: a problem can be made easier by deleting information that looks essential. Not simplifying the drawing. Refusing to care about most of it. Euler kept four dots and seven lines, which is roughly the information on my receipt, and that was enough.

The odd-corner rule that settles it

Now follow a walker. Arrive at a piece of land, and you must leave it, unless it is where the walk started or where it finished. So every bridge into a place has to be matched with a bridge out, pair by pair, whenever you are passing through. Only the two ends of the whole journey can be left unpaired, and only if they are different places.

That single sentence is the entire proof, and it has two consequences worth saying out loud. A walk that returns to its starting point needs every single place to have an even number of bridges, because nothing is allowed to be left over. A walk that starts in one place and finishes in another needs exactly two odd places, the beginning and the end.

Konigsberg has four odd places: 5, 3, 3, and 3. Four is more than two. No walk exists, and no cleverness can rescue it, because the impossibility does not depend on the walker at all. It is a property of the city. I still remember the look on my daughter's face when the counting did it. Not disappointment. More like relief, the feeling of putting down a puzzle that had been quietly accusing her of not trying hard enough.

A proof that outgrew its bridges

Euler published the argument in 1736 in the proceedings of the St Petersburg Academy (Euler, 1736), and the paper is a strange kind of masterpiece: a proof of nothing. It does not produce a route, a design, or a method. It removes a whole category of possibility and shows, in a way any patient reader can check, that the failure was never personal.

Mathematicians kept the idea. A century and a half later it was common to draw networks of dots and lines for railway schedules, molecules, and political alliances, and today the same picture underlies search engines, social platforms, and the map on your phone. Euler also gets regular mention among the people who shaped the subject (a short gallery of mathematicians), usually for the volume of his work rather than for this one, which he probably considered a small detour.

The bridges themselves did not make it out of history. Konigsberg is Kaliningrad now, and the layout Euler sketched did not survive the Second World War. A reader who wants to try the walk today cannot, because the walk is gone. The argument is not.

Where the same walk runs today

The reason this 1736 puzzle keeps showing up is that a walker who uses every edge exactly once is a genuinely useful object. Snow ploughs, street sweepers, meter readers, and delivery vans all have to cover ground, and the ideal world is a route that covers every street once and comes home. Euler's rule tells a route planner in advance whether that perfect sweep exists, and when it does not, which junctions force a street to be driven twice.

The most surprising use is in biology. DNA sequencing machines do not read a genome top to bottom. They produce millions of short, overlapping fragments, and assembling them into one sequence is a stitching problem of exactly Euler's kind: turn the fragments into a graph and look for a walk that uses every edge once. Pavel Pevzner and his colleagues laid out that approach in 2001 (Pevzner, Tang & Waterman, 2001), and assembly software still leans on the same trick. A walk nobody could make through seven bridges now runs through a genome.

This part is genuinely useful when a child asks why they are learning this. Not because the standards list it, but because a question about a walk turned into the language used to describe the internet, the genome, and the traffic light at the end of the street.

Teach it on one napkin, then let it go

You need paper, a pencil, and about ten minutes. Draw four dots and connect them however you like with as many lines as you like, then ask a simple question: can a single stroke cover every line exactly once? Count how many lines meet at each dot. If every dot has an even number, the scribble can be drawn and you finish where you started. If exactly two dots are odd, it still works, as long as you begin at one odd dot and end at the other. Three or more odd dots, and no amount of patience will help.

Do it once with your child and the counting becomes a habit. After that they will draw a corner with three lines and announce, before lifting the pencil, that it cannot be done. This is a real mathematical move: gathering the same habit of trying a simpler version, then a smaller one, is most of what the problem-solving playbook teaches, and it transfers to word problems that have nothing to do with bridges.

The bridges of Konigsberg themselves are gone, and the city that built them is now called Kaliningrad. What survived is a habit that is worth more than a correct answer: when a task feels impossible, count instead of trying harder. Euler did it with seven bridges and four pieces of land, and he never had to leave his desk.