Node Kayles

Node Kayles is a two-player game played on an undirected graph where players alternately select a vertex, removing that vertex and all its neighbors from the graph. The player who cannot move loses. Like the Geography game, Node Kayles is PSPACE-complete on general graphs, and it belongs to the family of combinatorial games that capture strategic interaction on discrete structures. The game was introduced by Richard Guy and Cedric Smith in the 1950s as part of the systematic study of impartial games, and its complexity classification was established later by Schaefer.

The simplicity of Node Kayles — select a vertex, remove it and its neighbors — belies its computational depth. The game is a model for resource allocation problems, network inhibition, and strategic domination: each move is an irreversible commitment that eliminates future options not only for the mover but for the opponent. This irreversibility is the structural feature that makes the game PSPACE-complete, and it is the same structural feature that makes many real-world strategic problems hard.