Freely Solvable Graphs in Peg Solitaire

In a 2011 paper, the game of peg solitaire is generalized to arbitrary boards, which are treated as graphs in the combinatorial sense. Of particular interest are graphs that are freely solvable, that is, graphs that can be solved from any starting position. In this paper we give several examples of freely solvable graphs including all such trees with ten vertices or less, numerous cycles with a subdivided chord, meshes, and generalizations of the wheel, helm, and web. 1. Introduction Peg solitaire is a table game which traditionally begins with “pegs” in every space except for one which is left empty (i.e., a “hole”). If in some row or column two adjacent pegs are next to a hole (as in Figure 1), then the peg in can jump over the peg in into the hole in . The peg in is then removed. The goal is to remove every peg but one. If this is achieved, then the board is considered solved [1, 2]. Figure 1: A typical jump in peg solitaire, . In [3], this notion is generalized to graphs. A graph, , is a set of vertices, , and a set of edges, . Because of the restrictions of peg solitaire, we will assume that all graphs are finite, undirected, and connected graphs with no loops or multiple edges. For all undefined graph theory terminology, refer to West [4]. If there are pegs in vertices and and a hole in , then we allow the peg in to jump over the peg in into the hole in provided that ,？？ . The peg in is then removed. This jump is denoted by . A graph is solvable if there exists some vertex so that, starting with a hole in , there exists an associated terminal state consisting of a single peg. A graph is freely solvable if this is true for all vertices. A graph is distance 2-solvable if there exists some vertex so that, starting with a hole in , there exists an associated terminal state consisting of two pegs that are distance 2 apart. In Figure 2, the left graph is not solvable. The middle graph in Figure 2 is solvable but not freely solvable. The right graph in this figure is freely solvable. Figure 2: An example of an unsolvable, a solvable, and a freely solvable graph. In [5], it is shown that, of the nonisomorphic connected graphs on seven vertices or less, only are not freely solvable. However, determining whether a specific graph is freely solvable is NP-hard. Also [6] shows that, if is freely solvable and is obtained by appending a pendent vertex to any vertex of , then is (at worst) solvable. We are motivated by the above comments to give examples of freely solvable graphs in this paper. Known examples of freely solvable graphs include the Petersen graph,