Resumen de Analysis of a game of graph solitaire

R. Hemasinha

• Let G be a simple undirected graph. To each vertex assign one of two colours say red or blue. A solitaire game is played on G as follows. A move consists of selecting a blue vertex, inverting the colours of its neighbours and then deleting the chosen vertex and all edges incident upon it. The goal is to delete all the vertices. The question of finding a winning strategy in the case when G is a simple cycle was proposed in the problems section of the American Mathematical Monthly. In this article some general results on winning colour configurations are derived and the game is analysed for certain other graph classes.