Melting Dreams

it’s true you can’t draw one continuous line that would do the trick. but if the kitty and bunny set out by going through the doors they’re marked beside and each walked the certain way their colored arrows show at the same time their “collective path” as a team would go through each door only once. The moral of the story is actually about friendship , and cooperation, because in this world there are tasks you can’t do on your own.

This is a graph theory problem looking for eulerian paths. If we represent each room as a dot (a vertex) and each door as a line between dots (an edge) we have a graph. We say the degree of each vertex is the number of edges that go to it. An eulerian path goes around the graph using every edge exactly once and an eulerian circuit does the same as well as ending up back where it started. Here’s a graph for the original setup.

Note that the degrees of the vertices are 9, 5, 5, 4, 5, 4. Four of them are odd. A connected graph has an eulerian path if and only if it has exactly two vertices with odd degree. A connected graph has an eulerian circuit if and only if it has exactly zero vertices with odd degree. This has four, so it has no eulerian path or cycle.

NOW, as for whether there’s a path that goes through every door TWICE, that’s the same as finding a path that goes through every door in this new diagram once.

And look at that! All the vertices have even degree! Of course they do, because we basically duplicated each edge in the original. So now we not only have an eulerian path, but an eulerian cycle! A path that goes through every door exactly twice AND ends up back where it started! Here’s one that’s kinda tangly for fun as well as a tamer organized one. The organized one involves often just going on one door and leaving immediately, but the tangly one demonstrates that’s not the only way to do it.

Graph theory is fun!

2039

moiré foray 09