The Bridges of Husby
 
Support Ukraine

The Bridges of Husby

Back in Euler's day, Königsberg had seven bridges[a]. Husby, being more than twice as good, and being the suburb where the concept of traffic separation was taken the furthest, has sixteen - or twenty-one, if you count bridges leading out.

Königsberg did not have an Eulerian path[b] - it was not possible to stroll through the city and cross all bridges while only crossing each bridge once. But is it possible to find an Eulerian path through Husby?

2024-10-12 13:30

graph theory, math

Husby

 

The whole suburb is bordered to the north-west by Akalla, and to the east and north-east by Kista.

Husby doesn't have any river going through it, but it does have a main road - Norgegatan - so we'll consider that our river, along with Hanstavägen, which borders it to the north:

Norgegatan branches off left and right to smaller streets that lead to the various areas of Husby.

To partition the land on each side of the road we'll notionally extend the side streets indefinitely so we can't just go around the ends of them.

Marking the bridges in yellow, and the resulting areas in blue for areas that are part of Husby and green for areas that are not we get this:

Now we can get all graph theoretical on this, and replace the areas and bridges with vertexes and edges (solid lines being internal and dashed being external):

A quick count reveals that with the external areas it's not possible to find an Eulerian path - six of the areas have an odd number of bridges connecting them to neighboring areas, and we can have at most two. But removing the external areas reduces the number to just two, those marked in gray, and we should be able to find a path. Just eyeballing it gets us this:

So the answer is yes, Husby does have an Eulerian path (albeit not an Eulerian cycle).