I was seeking problems to be solved using graph theory concepts for instruction of my class and found one on an online IQ test. This is similar to the “7 Bridges of Königsberg” Problem:

“If a doughnut shaped house has two doors to the outside and three doors to the inner courtyard, then it’s possible to end up back at your starting place by walking through all five doors of the house without ever walking through the same door twice.”

To present this in graph theory language, we’re looking for an Eulerian circuit across a graph with 3 vertices and 5 edges. This means the exact same thing as the problem above.

Think of each of those 3 vertices as a “state”. One of them is “inside of the house”. Another is “inside of the courtyard” and the third is “outside”.

Every time we enter a part of the house, we must also leave it. So for us to start on the inside, go outside, and end up back inside when we finally finish, for example, we’ll need to cross an even number of doors. This would be true even if we could somehow go from the inner courtyard directly outside.

This turns out to be a requirement of every “state” we pass through: it must be entered and it must be left. If we weren’t concerned with ending up in the starting location, we could make two exceptions to this: the starting state, which one does not require a door to initially enter, and the ending state, from which one does not leave. Ordinarily, these could tolerate an odd number of doors. But since we want to start and end in the same location, we don’t even have that luxury: if we don’t enter once and don’t leave once, we skip two doors and we’re back to an even number.

In the language of graph theory, we call the number of adjacent edges to a vertex the degree of that vertex. What we can then say is that an Eulerian circuit – a path that crosses every edge once and ends at the same vertex it began – requires every vertex in the graph to have an even degree.

In other words, all “areas” within the house must have an even number of doors for such a path to exist. So what is the degree of each vertex? (how many doors lead in and out of each area?)

Two doors exist between the inside and the outside and three exist between the inside and the courtyard.

One of the vertices has an odd degree, thus no Eulerian circuit exists and it is not possible to cross each door once and end up back where you started.

There’s also a bit more relaxed traversal called an “Eulerian path”, which removes the restriction that we must end in the starting location. That would indeed be possible: start in the courtyard, walk through the three doors, leaving you in the inside, and walk the two doors from the inside to the outside. This starts you in the courtyard and ends inside of the house.

Let’s say that we’ve been hired as a contractor by the owners of the doughnut shaped house, who wish to exercise every morning by taking an Eulerian circuit around the house. How could we rectify this?

The answer is to either build another door between the inside and the courtyard or to knock one down.

Whichever is cheaper to do, I suppose.