Inspired by this question.
This game is played on an arbitrary graph. Player 1 starts by choosing a vertex. Then alternate:
- Player 2 selects a set of $n$ vertices of the graph. Player 1 loses if they are on any of these.
- Otherwise, player 1 moves from their current vertex to one of its neighbours. Player 2 learns nothing other than that the game hasn't ended.
What is the minimum $n$ such that player 2 wins?
WOLOG, the graph is connected and simple. As @Tavish notes, the only way to make progress is to completely eliminate vertices; but the eliminated set need not be monotonic per turn. $n$ itself is monotonic under induced subgraphs.
Several interesting cases to consider:
- The infinite star: $n=1$
- $k$ triangles joined at a common vertex (or the $2k$-star, with leaves paired): $n=2$
- Two infinite stars with their roots connected: $n=1$
- The $k$-path, $k\geq5$:
n=2$n=1$ still - The 5-cycle with one vertex exploded into $k$ unconnected vertices: $n=2$
- The $k$-cycle, $k\geq6$:
n=3$n=2$ still - An induced subgraph of minimum degree $k$: $n\geq k$
So it seems path length plays a complicated role here, not just degree.
Here's an easy upper bound:
Arbitrarily order the vertices. Maintain two sets, called the burned set and the current-tag set; both start out empty.
- Pick the earliest unburned vertex, and add it and its unburned neighbours to the current-tag set.
- Tag all of the current-tag set this turn.
- Whenever a vertex and all its neighbours are all either burned or currently-tagged, burn that vertex and remove it from the current-tag set.
- Repeat.
Correctness invariant: player 1 may never be on a burned vertex.
Any stronger theorems?