UNDIRECTED EDGE GEOGRAPHY

The game of edge geography is played by two players who alternately move a token on a graph from one vertex to an adjacent vertex, erasing the edge in between. The player who first has no legal move is the loser. We show that the decision problem of determining whether a position in this game is a win for the first player is PSPACE-complete. Further, the problem remains PSPACE-complete when restricted to planar graphs with maximum degree 3. However, if the underlying graph is bipartite we provide (1) a linear algebraic characterization of the P- and N-positions, yielding (2) a polynomial time algorithm for deciding whether any given position is P or N, and also (3) a polynomial time algorithm to find winning moves.