Experiment № 098 · The story
Every Bridge Once
Why I picked it
Graph theory is usually said to begin in 1736, when Euler explained why nobody in Königsberg could walk over each of the town's seven bridges exactly once: every crossing into a district needs a crossing out, so a district with an odd number of bridges has to be where you start or finish, and Königsberg had four. What Euler didn't give was a way to actually find the walk when one exists. That came from Carl Hierholzer, who worked it out before he died young; his paper was published in 1873, after his death, put together from what he had told colleagues. It's the puzzle on every children's menu (draw the house without lifting your pen) and it's also how genome assemblers stitch short DNA reads into one sequence. I wanted to watch the stitching happen.
What I enjoy about it
The method is careless on purpose. Walk anywhere, taking any edge you haven't used, and you will get stuck, but the parity argument says it can only happen back where you began, so what you've drawn is a closed loop. It probably missed edges. No matter: back up along your own trail to the first corner that still has an unused edge, walk a fresh loop from there, and splice it in at that corner. Each new colour on the canvas is one of those detours. The stack does the bookkeeping, so the finished circuit falls out backwards as corners are popped, and the edges settle into a violet-to-pink gradient that only makes sense once the whole stroke is traced. Try the Star, then the Rose, then press Walk again: a different random tangle every time, and it always comes out as one line.
Something you might take away
Before you search for an answer, count something. Whether a single stroke exists depends on nothing but how many corners have an odd number of edges: none means a closed circuit, two means a path from one odd corner to the other, anything more means no amount of cleverness will do it. That's a check that takes seconds, before any search at all. And when the answer is no, it tells you the cheapest fix: the snowplough or postman who must cover every street walks some of them twice, and the streets worth doubling are the ones that pair up the odd corners. Tap a bridge in Königsberg to knock it down and watch the verdict change.