For many years, the people of Shmoopland have been terrorized by bridge trolls charging troll tolls, until the city officials decided to change the zoning laws. From now on, trolls aren't allowed to live underneath bridges—letting humans and goats everywhere share a sigh of relief. To make sure the trolls don't come back, they hire you to monitor all the bridges.

Here's a breakdown of the city and all the bridges trolls could hide under:

Because Shmoopland is a glorified archipelago (apparently), there are seven bridges connecting everything together (labeled in brown).

Your boss—admittedly a bit of a sadist—promises you a huge raise if you can cross every single bridge once and only once, ending in the same place that you started. They don't give you anything if you happen to visit the same region twice in your troll-hunting trek, which is a pretty weird restriction but whatever.

If you start planning your route, you'll notice that your paths won't ever check every bridge while also checking each one once and only once. It's so close though. One more bridge and you'd solve the puzzle. Maybe it's this next path…

It isn't.

All of the regions are actually inescapable—if you take a bridge from one region to another, you can't go back to the first region unless you go to a third region. For most bridges, that'd be fine, but that final bridge will always be in either

1. a place where all the other bridges have been used.
2. unable to make a circuit.

Let's look at an example path for the bridges. Say you started at Region 3, went to 4, then to 1. You head back to 4, then to 2, then 3, and finally to 4 again, you would only have crossed 6 of the 7 required bridges and, more importantly, you'd be stuck in Region 4 without a way to get out and cross that final bridge—much less come back to where you started.

Still not convinced? Let's try again. Go from 1 to 4, to 3, back to 4, back to 1, to 2, and back to 3, and now you're stuck in Region 3 without any way of crossing that final bridge between Region 4 and Region 2.

If we look at this map as a—wait for it—graph, all the regions can be nodes and the bridges edges. In order to enter and leave a region, you need two edges. Since every node has an odd degree (an odd number of edges attached), you won't be able to leave every region the same number of times you can enter them. Eventually, you'll need to get out of a region where there are no more bridges to cross.

If you start in Regions 1, 3, or 4, you can come into Region 2, go out of it, and then come back in again, but you've used all three bridges attached to 2, meaning that you won't be able to leave it. If you started in Region 2, you could leave it once, come back again, and leave it a second time, but then you'd have no way to get back there.

No matter how you work the graph, it's impossible to visit every single bridge—much less end up where you started.

(If you don’t believe us, try for yourself. If you do find a solution, you'll deserve more than that meager promotion your boss promised; you should probably be knighted or something.)

This troll problem isn't new—at least not the bridge part of it—it's just typically known as the 7 Bridges Problem. Way back in 1736, Leonard Euler (pronounced, "Oiler") wanted to figure out if the 7 Bridges of Königsberg could form a circuit if you tried crossing each one once and only once. They can't, but if you remove one bridge from the list (like that pesky one between Region 4 and Region 2), all of the sudden you'd have a solution.

Euler figured out that it's all about the degree of each node when determining whether a path through all the edges only once (called an Euler Path) is even possible. If every single node in a graph has an even degree, then it's possible. Otherwise? Sometimes, but it isn't guaranteed.

Think about a five-pointed star.

Every node here has two edges connecting it to two other points, giving each node an even degree. You can even draw the entire star from start to finish and end up where you started, creating an Euler Circuit.

Once you get out of the "clearly fine always" category, things get a little more nuanced. If two nodes have odd degrees but every other node has an even degree, you can still find an Euler Path. Those two nodes kind-of even each other out. But if you have one, three, or any larger number of nodes with odd degrees, you won't ever find an Euler path.

Whew.

In the 7 Bridges problem, all four regions have an odd number of bridges connecting them, meaning no Euler Path could possibly exist.

At least that's good news for trolls.