On variants of Vertex Geography on undirected graphs
Undirected Vertex Geography (UVG) is an impartial two-person game played on a (undirected) graph G with a specified vertex u. Players, Alice and Bob, alternately choose a vertex that has not been chosen before and that is adjacent to the last chosen vertex. Alice plays first, choosing an adjacent vertex of u. The first player who is unable to choose a vertex loses. Determining whether Alice has a winning strategy in this game (the UVG problem) is known to be solvable in polynomial time.