How do you catch a cat on a tree?

Question

Suppose we have a finite (not directed) connected graph $ G $ with no loops (self-edges). There's a cat on one of the vertices of this graph but we don't know which.

We play the following game: at every turn, we can check one of the vertices to see if the cat is there or not. If the cat is there, we win. If the cat is not there, the cat gets a move in which it can move to any neighbor of the vertex it's currently at, and it must use this move. This is important: the cat can't sit in its current position, it has to move from it when its turn comes. Then we go on to the next turn in which we make a move and the cat makes a move, then to the next turn, etc. until we either catch the cat or fail to do so forever.

For which finite graphs $ G $ do we have a strategy that's guaranteed to win?

Some preliminary observations: what we're doing is defining a directed graph structure on the power set $ \mathbb P(V) $ of the vertices $ V $ of $ G $ and asking if we can get to the empty set from the set $ V $. For small graphs it's possible to exhaustively search this directed graph using depth-first search and determine whether there is a solution or not.

Furthermore, this picture also makes it clear that $ G $ must actually be a tree if we have a strategy that's guaranteed to catch the cat. This is because if there is a cycle in $ G $ which is initially included in a set, then after we make our observation we can exclude at most one vertex from this cycle, and since every vertex in the cycle has at least two neighbors when the cat makes its move it will still be possible for it to be anywhere along the cycle.

Here are some simple cases: we always have a winning strategy for the path graphs $ P_n $. If the vertices are $ 1 $ through $ n $, then we simply observe $ 2, 3, \ldots, n-1, n-1, n-2, \ldots, 3, 2 $ in order and we're guaranteed to catch the cat no matter what it does. If you don't see how this works, it's worth working it out explicitly.

Here is a tree for which we have no strategy that always wins:

I don't have a proof of this fact; it's verified by depth-first search as I mentioned earlier (though a proof for this specific case shouldn't be hard to find). However, some close cousins of this tree do have winning strategies, such as this one:

The optimal (in the sense of minimizing the number of moves in the worst case) solution for this graph takes at most fourteen moves to catch the cat. You can try to see if you can find it.

As I've said, I'm interested in any nontrivial results about trees of this type, so even if you don't have a full classification you can post whatever partial results you're able to prove.

Note: If anyone has confusions about the problem, this Colab notebook contains an implementation of a verifier for whether there is an always-winning strategy for any given graph or not.

Answer 1

The minimal tree (by number of nodes) where you cannot catch the cat is this 10-node graph:

o
 \
  o
   \
    o
     \
      o - o - o - o
     /
    o
   /
  o
 /
o

Call this tree $Y$. I claim that if $T$ is any tree not containing $Y$, then you can catch the cat. Here is a sketch of the argument:

If $T$ does not contain $Y$, then $T$ consists of a long path (the "spine") with some number of paths of length at most 2 (the "legs") coming out of each internal vertex (i.e. not an endpoint) of the spine. Some of the legs from an internal spine vertex may share another common leg-internal vertex, as in the second picture in the original post (see the central spine vertex).

To catch the cat, start with the first internal vertex of the spine. At each internal vertex $v$, if there are any legs of length 2 coming out of $v$, then for each such leg, step onto the leg's internal vertex and then immediately back to $v$. (Shared leg-internal vertices need only be visited once.) Then move to the next vertex of the spine. Repeat this until you get to the last internal spine vertex and handle all its legs of length 2. For the last leg of the last internal spine vertex $v$, you do not need to go back to $v$ after walking onto the leg. At this point, we have traversed all non-leaf vertices at least once, and the cat is restricted to one of the bipartitions of the tree. Now traverse the same vertices again, but in reverse order (again after traversing the last leg you don't need to go back). This will catch the cat.

For example:

A------B-------C-------D--------E---------F
      / \                       |
     G   H                      I
    /     \                     |
   J       K                    L

The winning sequence of guesses described above is B, G, B, H, B, C, D, E, I (at this point we've traversed all the non-leaf vertices, now we do the same sequence in reverse, omitting the final B) I, E, D, C, B, H, B, G.