Stuck in Königsberg

There was a myth in the Prussian city of Königsberg that if a person crossed every bridge in the city exactly once in a single day (without crossing a river by boat or swimming), then that person would immediately find true love.

Many people in the city sought to find a path that would lead them to this elusive goal…

Sadly, it's not at all easy to find a path that will lead across every bridge. Here's one example of a path that doesn't work.

If a solution doesn't immediately present itself, one approach is to simply try many different random paths and hope that one of them will lead to a valid solution. Unfortunately, it's not obvious how many attempts one should make before giving up. None of the paths below work, for example…

Leonhard Euler's solution to this problem in 1736 laid the foundations for graph theory and led to a great deal of valuable mathematics. It did not, however, lead anyone in Königsberg to true love, as Euler was able to show that the problem was insoluble. There is no path that crosses every bridge exactly once.

The problem below takes as given that it's impossible to cross all the bridges, but it asks you to find a worst-case scenario. What's the shortest path through the city that leads to getting "stuck"?

Today's Challenge

If you're only allowed to cross each of the bridges from Königsberg exactly once (and you can't swim the rivers), it's impossible to cross all the bridges.

What is the smallest number of bridges that can be crossed before getting stuck?

×