The node deletion game NODE KAYLES is a two persons perfect information game played on a graph $G$. Players alternate picking a node from the graph $G$; the node and its adjacent nodes are deleted. The first player unable to move loses the game. Deciding the winner of a NODE KAYLES game is $\mathsf{PSPACE}$-complete [1]. Similarly in the EDGE KAYLES [1] game the two players must pick an edge; the edge is deleted along with the two endpoint nodes and the edges incident to its two endpoint nodes. The complexity of finding the winner of a EDGE KAYLES game is unknwon. On the Q&A site cstheory.stackexchange.com I submitted a mix of the two games; I call it the BRIDGES AND ISLANDS game: at each turn each player must pick an edge (a “bridge”) or an isolated node (an “island”); if a player picks a node the node is deleted along with its incident edges, if it picks an edge, the edge is deleted along with its two endpoint nodes and the edges incident to them. Like the other two games, the first player unable to move loses the game. I didn’t succeed in finding the complexity of BRIDGES AND ISLANDS.

However decideng the winner is polynomial time solvable when the three games are played on a path. Here I give a quick proof for EDGE KAYLES; the proof for the other two games is similar. Continue reading →