Peg solitaire game on graphs

Peg solitaire game is a board game which traditionally begins with pegs in every space except for one which is left empty (hole). The rule of the game can be defined as two adjacent pegs, say x and y, are followed up by a hole z, then the peg x can jump over the peg y into the hole z. Then the peg y is removed and the main goal is to remove every peg but one. If this is achieved, then the board is considered solved. These boards are treated as connected graphs in the combinatorial sense. Let G = (V, E) be a given graph. If there are pegs in vertices x and y and hole in z, then we allow x to jump over y into z such that {x, y} and {y, z} are edges of G. As described above, the peg y is removed. If the all pegs are removed except one then the graph is called solvable. In this master thesis, initially the solvability conditions of the peg solitaire game are compiled from the literature and the necessary and sufficient conditions for the solvability of various graphs are presented. Moreover, it is proved that Sierpinski graphs are solvable. Keywords: Graph, Peg solitaire game, Sierpinski graph