# Bristol Bridge Problem

It's 6:38 am, February 23rd, 2013. At this time on a Saturday there is hardly any traffic. The silence is broken only by the calls of the seagulls and the sound of my steps as I climb the old iron stairs leading up to Vauxhall Bridge. The riveted length of the footbridge takes me across the waters of the New Cut to a part of Bristol called Bedminster. Once there, I turn left and walk upstream until I reach another footbridge, Gaol Ferry Bridge. Compared to the steam age aesthetics of Vauxhall Bridge, this bridge seems impossibly light and playful with its rich Victorian decorations. I cross the bridge back to Spike Island, a river island in the centre of Bristol. The next bridge is now only a couple of steps away, a swing bridge, called Swing Bridge.

My walk is linked to the year 1736 and the Russian city of Caliningrad, or as it was known then, by its German name, Königsberg. The city lies close to the mouth of the river Pregel and occupies both banks of the river and two river islands. Connecting the different quarters were seven great bridges, and a much debated question was whether it was possible to go for a contiguous walk that took the walker across each bridge exactly once. Many citizens claimed that they had found such a walk, but when challenged could not reproduce it. Others held that such a walk was not possible, but could not prove that statement either. By 1736 the bridge problem was not only discussed in Königsberg but occupied the minds of intellectuals across Europe. I have taken on the same challenge in modern Bristol, which has some similarities to Königsberg. It lies close to the mouth of the river Avon, and like Königsberg, occupies both banks of the river and two river islands.

Meanwhile Swing Bridge has taken me to Redcliffe, on the second island. I follow the New Cut further upstream until I reach Bedminster Bridge. This old road bridge has been extended into a roundabout by the addition of a second bridge side-by-side to the original. I use the older bridge to cross the New Cut to Bedminster and return to Redcliffe via the newer bridge. Farther up the New Cut I pass Langton Street Bridge, whose yellow colour and bend shape have earned it the name Banana Bridge. I can't cross it right now, because it will be needed later. Instead, I continue farther upstream to Bath Bridge, another double-bridge roundabout, where I cross over to Bedminster and back to Redcliffe once more.

To be honest, I will not cross every single bridge in Bristol. In modern times there are some bridges that cannot be legally crossed on foot. But, those bridges would not have been included in the original Königsberg problem either. Keeping in mind that the bridge problem is all about a leisurely walk for the Lords and Ladies makes it clear which bridges should be included. For instance, also some minor bridges that crossed ditches and smaller rivers must have existed around Königsberg, but were not mentioned in the original problem. So, my challenge is to cross every bridge exactly once that spans one of Bristol's major waterways and is legally walkable.

Walking farther upstream I reach St. Philip's March, which was once a separate island, but is now connected to Redcliffe. At this point also the artificially dug riverbed that is the New Cut ends and turns into the Avon proper. A little further lies an old railway bridge. This bridge derailed one of my earlier attempts at the bridge walk, when I found that it was crossable, although I had thought it was not. Finding this bridge meant that I had started the walk in the wrong place and could not complete it without crossing a bridge twice. However, this time I have started right. I use the railway bridge to cross the Avon and continue farther upstream. I pass Totterdown Bridge, another one that will be needed later, and then cross the Avon again on Greenway Bridge, a beautiful wooden footbridge.

What makes the bridge problem fascinating is that it contains a taste of complexity. Although the challenge can be simply phrased, the walk that solves the challenge is a complex object that depends intricately on the placement of every single bridge. One can say that the walk emerges from the pattern of bridges. Dealing mathematically with such emergent properties of interconnected systems is the core challenge that underlies a wide variety of phenomena ranging from climate change to social networks.

Meanwhile I have reached the St. Philip's Causeway Bridge, another double bridge, on which I cross the Avon two more times. Then I turn my back on the Avon and cross the breadth of St. Philip's Marsh to the Feeder Canal that connects the Avon to Bristol's Floating Harbour. I cross the Feeder Canal on Marsh Bridge and walk farther upstream to the Netham Lock Bridge, the smallest double bridge on the walk. Here, I can only cross one of the two bridges right now. It takes me back across the Feeder Canal to the very tip of St. Philip's Marsh. From here it is just a few steps back to the Avon, which I cross on New Brislington Bridge, before heading farther upstream. Finally, three and a half hours into the walk, I reach St. Anne's Bridge the eastmost point of the walk. From here on there are no further bridges across the Avon up to a Motorway bridge near the town of Keynsham. I turn downstream, and follow the Avon to the beginning of Feeder Canal. Walking down the canal I cross the second bridge at Netham Lock, the Barton Hill footbridge, and another bridge named Marsh Bridge. Bristol's newest bridge is now just around the corner, but I can't reach it because I am on the wrong side of the Feeder Canal. It is time for a detour across some bridges which we have already seen but not yet crossed. I walk back across the breadth of Saint Philip's Marsh and cross the Avon on Totterdown bridge. Back on the Bedminster side it is a short walk through parks and residential areas to Langton Street's Banana Bridge.

In principle the bridge problem can be solved by a brute force approach: We know that the solution that we seek must be a sequence of bridges containing every bridge exactly once. We can thus list all such sequences and then, for each sequence, check whether it is actually walkable. In Bristol one such sequence could start "Swing Bridge, St. Anne's Bridge, Vauxhall Bridge, ...". But this sequence is not walkable, because Swing bridge connects Spike island and Redcliffe, whereas St. Anne's bridge is not reachable from either of the two islands without crossing another bridge. Checking all sequences in this way, we either eventually find the desired walk or prove that the walk does not exist.

To solve the Königsberg problem we only have to check 5040 sequences. To see this consider that when choosing the first bridge in the sequence we have the choice among seven bridges, once the first bridge in a sequence is chosen we have six choices left for the second bridge and then five for the third and so on. Thus the total number is 7*6*5*4*3*2*1=5040, which we can write as 7! (seven factorial). Such brute force solutions have become very popular because they can be quickly implemented on computers, which run through the 5040 sequences in some microseconds. However, even in 1736, we could have sat down with quill and parchment to write out and check all the sequences within two days or so. In Königsberg this would have revealed that the desired walk does not exist. We could still have gone off to our peers and claim that we have resolved the problem by proving this once and for all. However, this would have hardly earned much bragging rights because, said peers would have to go through the whole list of 5040 sequences again to confirm our results. For Bristol we need another solution anyway. I plan to cross 42 bridges, so one would have to check 42! sequences -- a number with 51 digits. Even the fastest computers would need roughly 10.000.000.000.000.000.000.000.000 times the age of the universe to check that many sequences.

Back on the walk I have reached Bristol's newest bridge. The modern footbridge is made of polished steel and has many tiny holes that are lit at night. But, now it is noon and the bridge reminds of a giant cheese grater. I use the bridge to cross Bristol's Floating Harbor, and then immediately return to Redcliffe by crossing Valentine's bridge, another modern footbridge. I wind my way further down the floating harbor crossing the Temple Bridge and St. Phillipe's bridge and taking a small detour to take a little footbridge across the remainder of the moat of Bristol castle. Then I reach Bristol Bridge. The great stone arches of this bridge were completed in 1768, but most of the upper half of the bridge was added in Victorian times. The first stone bridge in this place was probably built already in the 13th century. Its wooden predecessors gave the city its name Brycgstow -- place of the bridge.

In 1736, 32 years before the completion of Bristol bridge, the Königsberg bridge problem was solved be Leonard Euler. From a modern perspective one can say that the key insight for the solution is that one can only fail by trapping oneself in a city quarter that cannot be left without using a bridge twice. While the walk that we seek is a complex global object, failure occurs because of a local problem, and hence is much easier to analyze. Consider for instance a quarter that can only be reached via a single bridge. If we do not start in this quarter, our walk must end there, because once we cross its bridge we cannot leave again. So any quarter with only one bridge must be start or end point of the walk, if one exists. Neither Königsberg nor Bristol has such a quarter with only a single bridge. But, the same conclusion holds for all quarters connecting to an odd number of bridges. If a quarter has three bridges we must visit it twice to cross all its bridges. However, if this quarter wasn't our starting point, there will only be a single usable bridge left after we have arrived and departed for the first time, and thus the walk will end on the second visit. Similarly a quarter with 13 bridges needs to be visited seven times, and if the quarter was not our starting point, the walk will end when we arrive for the seventh time. Thus, every quarter that connects to an odd number of bridges can only be the start or end point of the walk. Since the walk can only have one start and one end point, a walk cannot exist if more than two quarters connect to an odd number of bridges.

Meanwhile I have used Redcliffe Bridge to return to Redcliffe a final time, before taking the blue Ostrich Bridge to Spike Island. I cross the Floating Harbour again on Prince Street Bridge and then follow it downstream while crossing Pero's Bridge and Poole's Wharf Bridge. Finally, Cumberland Basin Bridge takes me across the Floating Harbour once more, back to Spike Island. Crossing the breadth of the Island I reach Avon Bridge, a small Railway bridge, designed by Isambard Kingdom Brunel. After crossing this bridge it is just a minutes walk to Brunel way, one of the major roads into Bristol. Brunel way crosses the Avon and the Floating Harbour, on a giant swing bridge, called Plimsoll bridge. The first arc of this bridge takes me back to Spike Island, where I take a small detour to cross two smaller bridges beneath Plimsoll Bridge. Then, via the second arc, I cross the Floating Harbour once more and arrive in the quarter of Hotwells. Now the next bridge is five miles away.

In Königsberg all four quarters of the city connect to an odd number of bridges and thus Euler's solution proved that no walk can exist. In Bristol Spike Island and the right river bank have an odd number of bridges, whereas the left bank and Redcliffe connect to an even number or bridges. Thus a walk exists and must start on Spike Island or the right bank. I have chosen Spike Island as the start point of the walk with Bristol's most famous bridge and major landmark, Brunel's Clifton Suspension Bridge. Ending the bridge walk with the Suspension Bridge has not been possible until last year, when Bristol's youngest bridge was build. A new footbridge, named Möbius Bridge, is scheduled to be build soon, which will make ending the walk with the Suspension Bridge impossible once more.

It is sometimes criticized that mathematicians occupy their time by thinking about simple puzzles, and indeed it can be argued that Euler's elegant solution of the bridge problem in itself has little applications. Nevertheless the importance of his work is hard to overstate. The solution of the bridge problem marked the birth of graph theory, the mathematical study of networks, and by extension discrete mathematics and modern network science. It thus led to a series of discoveries that provide the basis for services such as google, facebook, and twitter, and even the internet itself. Perhaps even more importantly, it is becoming apparent that networks provide a unifying theme in complex systems research that provides and thus has vast applications ranging from biology and medicine to the design of robust technical systems.

Meanwhile I have reached Sea Mills where I am crossing the River Trym three times. From here it is another four miles walk along the bank of the Avon to the largest bridge in the walk. The Avonmouth Bridge carries the M5 motorway across the river. From atop the 1.3 km long bridge both Bristol and Cardiff are visible, and in the distance the two huge Severn bridges can be seen. From here on I walk upstream again. Six more miles to the final bridge.

The sun is already setting when I reach Clifton Suspension Bridge, from the small footpath on the bank of the river the bridge appears as an impossibly thin band that crosses the Avon Gorge high above. I pass under the bridge first, then, after a quarter of a mile, double back onto a forest path that climbs the 75 meters up to the level of the bridge. When I finally reach the bridge it is already dark and the bridge is beautifully lit by tiny white lamps that trace the curve of the steel-link cables. After 33 miles I cross the final bridge.