drossbucket

[Written as part of Notebook Blog Month.]

Last year I walked the Bristol Bridge Walk with my brother. This is a 28 mile circuit in the style of Königsberg’s famous bridge problem, where every bridge in Bristol (or more accurately, every footbridge across the Avon) has to be crossed exactly once. It was designed by Thilo Gross, who figured out that Bristol’s bridge problem can be solved, unlike Königsberg’s. At least until they build more bridges and mess it up.

I wrote a Twitter thread on this a while back but thought I’d try an expanded version here. The interesting bit for me is how much of Gross’s work in creating this route was in defining the problem, mapping all the mess of modern Bristol onto a clean mathematical model.

The original Königsberg bridge problem has the following structure, with four land masses and seven bridges:

Euler worked out that it wasn’t possible to cross each bridge exactly once. The solution is simple and short enough that I may as well reproduce it here. He found a clever reframing of the problem, where the four land masses become nodes of a graph, and the seven bridges become edges between them:

Now, ignore the start and end of the walk for a minute. For the rest of the time, every time you enter a land mass by a bridge, you also leave by a bridge. So if every bridge has been crossed exactly once, then for any node of the graph apart from the start and end ones, there must be an even number of edges coming out of it.

Now this can’t possibly work for Königsberg, because all four nodes have three edges coming out of them, and you can only get away with having the two start and end nodes with odd numbers of edges. So the problem is insoluble.

Bristol has a similar overall structure to Königsberg, so the problem maps over quite nicely. There’s one main river, the Avon, with two islands in the middle of it: Spike Island and Redcliffe. Here’s a map:

So there are four nodes. But modern Bristol has a whole lot more bridges. 45 in fact. (Or maybe 47 now. The two new arena bridges were closed when I did the walk. They don’t change anything though, you just cross one and immediately cross back on the other.) Here’s the graph:

A is the north bank, B is the south, C is Spike Island and D is Redcliffe. There are so many bridges between Redcliffe and the two banks that I just wrote the numbers instead of drawing each edge. There are also several internal bridges linking the north bank to itself, for reasons I’ll get to.

(I came up with that graph myself, and it might not exactly match Gross’s. I tried to construct it to match his descriptions, but there might be some edge cases I counted slightly differently to him.)

Ignoring the internal edges linking A to A (which can be removed), all nodes have an even number of edges. A has 20 without the internal edges, B has 18, C has 12 and D has 26. So it’s a soluble problem.

Now, coming up with that graph was a good deal more complicated than just counting bridges. This is the bit I find interesting as an example of problem formation, mapping complicated stuff in the real world onto a clean mathematical model with an unambiguous technical solution. Gross explains all the work he had to do to figure out the scope of the problem, and what should actually count as a bridge:

It required about three solid days of work spread over a fortnight. Two thirds of the time was spent just finding out where all the bridges were, and what was to count as a bridge and what not. Only bridges that are walkable are included and a judgement had to be made about some smaller bridges (not comparable in size to Königsberg’s bridges) on tributaries of the Avon that would have led the resulting walk long distances through some dull areas. Some bridges comprise two separate structures of segregated traffic and are counted as two.

It turns out that Bristol is like Königsberg on the large scale, but when it comes to the details there are a whole bunch of judgement calls. These generally have a reasonable, common-sense resolution, so the resulting solution doesn’t feel arbitrary, but it does mean that solving the problem is not just a quick matter of drawing some nodes and edges. I’ll go through a load of these below.

First up, Gross needed to decide what counts as a bridge. This is purpose-dependent: rail- and car-only bridges don’t count in this solution because the whole point is to be able to walk it.

Next, it’s not exactly true that there are four nodes. If you look closely at the map, there are two little islets off of Spike Island:

The left islet is kind of complicated, and worth looking at on a satellite view:

The two bottom footbridges linking the islet to Spike Island are genuine public bridges over the Avon and should definitely be included. The two top ones are little lock gate thingies. I don’t think they’re reliably walkable, and they probably shouldn’t count. So it’s a reasonable choice to ignore them and count the islet as part of the north bank node for the purposes of this graph.

The right islet is simpler: one bridge on, one bridge off. It kind of doesn’t matter much what you do with it – it could be counted separately (in which case it’s a new node with two edges), or shoved in with either the north bank or Spike Island. Gross went for the second option, preserving the similarity with Königsberg. Then the south bridge gets counted as the bridge between the north bank and Spike Island, and the second one gets counted as an internal bridge linking the north bank to itself. (At least that’s what I did. Not sure exactly how Gross formalised it.)

Also, there are a couple of minor rivers emptying into the Avon. There’s the Trym:

In a sense this cuts the north bank into two: west of the Trym and east of the Trym. Should these be two nodes? And should you have to traverse all the bridges along the Trym as well, right out into the suburbs of Bristol?

Gross goes with no. It’s a small river and is just not a big deal: I don’t think that which side of the Trym you’re on is part of many people’s mental geography in Bristol, in the way that ‘north of the Avon’ (or ‘east of the motorway’) would be. (While walking this we crossed it without noticing, and had to go back to get a photo of the bridge.) Also walking to the outer suburbs and back would be a big hassle and make an already long walk really tedious. So both sides of the Trym are the same node, and the bridges over the Trym that do get crossed as part of this walk are internal bridges linking the north bank to itself.

There’s a similar argument for the Frome:

This one’s easier, actually, because it’s mostly culverted in the centre and doesn’t really divide up Bristol at all. There are a couple of smaller rivers in the south, the Malago (also culverted) and Brislington Brook (tiny) which are even easier to rule out.

So we’re settled on four nodes. Now for the edges. This is mostly more straightforward, but even here there are special cases:

Is a bridge like this two bridges or one bridge? The aerial photo makes them look very much like one bridge, as you can see the whole intersection, but as a pedestrian they feel more like two. It doesn’t matter too much, but it would be annoying if the rule was inconsistent in different places. In this case they all get counted as two.

One last decision. There’s a single ‘outlier bridge’ in Bristol, the motorway bridge at Avonmouth. Here’s a map of the whole route area:

This bridge does have a footbridge, so it ought to count. But it’s way out in the west, miles down from the next bridge, the Clifton Suspension Bridge. It adds maybe a third of the route just on its own. It would be a reasonable decision to leave it out, but also annoying, because it’s such a big important bridge and the walk wouldn’t feel complete. So it’s kept in. This actually works out quite well, because one of the nicest parts of the walk is the path through Leigh Woods on the way back from Avonmouth.

So… is the Bristol Bridge Problem soluble? It is, in the sense that you can make reasonable arguments for dividing Bristol up into nodes and edges in a way that gives you a soluble problem. It isn’t, in the sense that you could probably make different reasonable arguments for dividing it up in a different way that doesn’t. (It’s fairly robust to small changes, but if you dropped the Avonmouth outlier and counted the double bridges as single ones you could maybe get something that isn’t soluble). In the end the arguments for it being soluble were all good enough that I was happy to go along with them for the sake of an interesting walk. It’s soluble enough for my purposes.

I really like this as a demonstration of the work of problem formation. It’s easy to understand without a specific technical background: the mathematical model is a simple graph, and the decisions about how to map Bristol on to it are all easy-to-understand common sense sorts of decisions. But it’s still not a trivial toy problem you’d find in a textbook. Gross had to put days of work into finding a good formalisation, and the decisions are genuinely hard to call without being completely arbitrary. It’s a great example of mapping between a technical problem and the mess of the world.