Undirected Geography who wins is a matching, the nimber is PSPACE-hard

A token sits on a vertex. Players take turns sliding it to a neighbouring vertex, and the vertex it leaves is deleted, so the token traces a path that can never come back. Whoever cannot move loses. The player to move wins exactly when the token's vertex lies in every maximum matching. Matchings settle who wins in polynomial time; the overlay shows one. The Grundy value (what the position is worth inside a sum of games) is a different matter: it is PSPACE-complete in general. Every legal move is marked with its exact value, a 0 means a winning move.

token and its trail a maximum matching of what is left ring: vertex missed by this matching

the position

moves

Two answers, two costs

Who wins (Fraenkel, Scheinerman and Ullman, 1993): delete the token's vertex. If the maximum matching gets smaller, the vertex was in every maximum matching and the player to move wins by moving along a matching edge. If it stays the same, every move lands on a vertex the opponent can match. This takes two runs of Edmonds' blossom algorithm.

What it is worth: the Grundy value decides sums such as two boards played side by side. Burke, Ferland and Teng (FOCS 2021) proved it PSPACE-complete, even on planar bipartite graphs of degree 4, and polynomial on degree 3, where their branch-and-bound needs only winnability tests. The panel shows both numbers when the board has degree at most 3.

Checked against the literature

The repository recomputes the paper's constructions, read from its arXiv TeX source. The edge gadget and the lemmas behind it hold on every digraph with up to 3 vertices. The branch-and-bound matches exact search. The high-nimber construction of Section 5 gives *n at Nn for n = 4…9 when built as the figures draw it. Built from Algorithm 1 exactly as printed, it gives 0, *, *2, * …, because the printed algorithm leaves out three things the figures and lemmas rely on. An exhaustive pass over every connected graph up to 9 vertices confirms the matching theorem on all 2,445,437 starting positions and finds the fewest vertices that a value *k needs: 1, 2, 4, 6, 8, 10 for k = 0…5. A tree needs 2k.