Walking an undirected graph as a game, without revisiting vertices

Question

Given an undirected graph and a starting vertex, two players take turns "walking" the graph by visiting a vertex connected to the last one visited. It's forbidden to visit a vertex twice (no matter which player visited a vertex first, either player can't visit it again). The first player to get stuck loses.

Given the simplicity of the setup I imagine this has been studied and some conditions are known (about the graph/starting vertext) for which player has the winning strategy, but couldn't find anything. Any results/references? Thanks!

Answer 1

The game is related to slither. But in slither there is no starting vertex, and the path can be extended in both direction, making it more difficult to analyze, but the basic idea still works

If player 1 chooses a perfect matching, he will always be able to play an edge from the matching. If the graph has not perfect matching, then we can use the Edmonds-Gallai decomposition to generalize the strategy of playing along a matching. In the Edmonds-Gallai decomposition, the vertex set is partitioned into outer, inner and perfect vertices.

• $v$ is an outer vertex if there is a maximum matching that avoid $v$,
• $v$ is an inner vertex if every maximum matching covers $v$ and $v$ is adjacent to an outer vertex,
• $v$ is a perfect vertex otherwise (it is covered by every maximum matching but is not adjacent to any outer vertex).

When we remove all the inner vertices, we get that the perfect vertices form perfectly matchable connected components called even components (their cardinals are even), and outer vertices form factor-critical odd components (removing any vertex in an odd component make it perfectly matchable, but we won't use this fact).

If the starting vertex $s$ is an outer vertex, the second player may choose a maximum matching $M$ that avoids $s$ and play using $M$. If at some later point in the game she is not able to move, the path build by the two players is would be an $M$-augmenting path, a contradiction to the maximality of $M$.

If the starting vertex $s$ is an inner vertex, the first player may choose any maximum matching $M$ avoiding some outer vertex $v$ adjacent to $s$, move first to $s$ and then play using $M$. If she gets stuck later, this would also imply the existence of an $M$-augmenting path.

If the starting vertex $s$ is a perfect vertex, then both players want to avoid being the first to move to an inner vertex (or getting stuck in the even component of perfect vertices). We already know that the first player may use the strategy for perfect graph in the even component containing $s$, hence forcing the second player to lose or move to an inner vertex.