# Freely Solvable Graphs in Peg Solitaire

Authors: Robert A. Beeler; Aaron D. Gray
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

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.


---

## Body

## 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 Figure1), then the peg in x can jump over the peg in y into the hole in z. The peg in y 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,x·y→·z.In [3], this notion is generalized to graphs. A graph, G=(V,E), is a set of vertices, V, and a set of edges, E. 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 x and y and a hole in z, then we allow the peg in x to jump over the peg in y into the hole in z provided that xy,  yz∈E. The peg in y is then removed. This jump is denoted by x·y→·z.A graphG is solvable if there exists some vertex s so that, starting with a hole in s, there exists an associated terminal state consisting of a single peg. A graph G is freely solvable if this is true for all vertices. A graph G is distance 2-solvable if there exists some vertex s so that, starting with a hole in s, 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 996 nonisomorphic connected graphs on seven vertices or less, only 54 are not freely solvable. However, determining whether a specific graph is freely solvable is NP-hard. Also [6] shows that, if G is freely solvable and G′ is obtained by appending a pendent vertex to any vertex of G, then G′ 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, the platonic solids, the Archimedean solids, the complete graph, and the complete k-partite graph. Other examples are given in [3, 5, 6].Several useful results are included in [3]. The following theorem allows the completion of the game in reverse by exchanging the roles of pegs and holes.Theorem 1 (see [3]).
Suppose thatS is a starting state of G with associated terminal state T. Let S′ and T′ be the duals of S and T, respectively. It follows that T′ is a starting state of G with associated terminal state S′.The following observation is also useful.Observation 1 (see [3]).
(i) IfG can be k-solved with the initial hole in vertex s and a jump is possible, then there is a first jump; say  s′′·s′→·s. Hence, if there are holes in s′′ and s′ and pegs elsewhere, then G can be k-solved from this configuration. (ii) If G is a k-solvable spanning subgraph of H, then H is (at worst) k-solvable.Because of this observation, it is of particular interest to determine which trees are freely solvable. In Figure3, we list all nonisomorphic freely solvable trees with ten vertices or less. The list of trees comes from the appendix to Harary [7]. An exhaustive computer search [8] was used to determine solvability.Figure 3
Freely solvable trees withn(T)≤10.


## 2. The Cycle with a Subdivided Chord

The cycle with a subdivided chord, denoted byCSC(n,m), is formed from a cycle on n vertices, labeled 0,1,…,n-1 in the usual way, by adding an edge from vertex 0 to vertex m to form a chord. This edge is then subdivided. The resulting vertex on the chord is labeled c. Figure 4 shows a cycle with a subdivided chord. As usual, Pn will denote the path on n vertices with vertices labeled 0,1,…,n-1 in the usual way.Figure 4
The cycle with a subdivided chord,CSC(6,2).In the following result, we show thatCSC(n,m) is solvable with the initial hole in several vertices. However, these graphs may be solvable from additional vertices as well. In [3], it was shown that P2n is solvable with the initial hole in vertex 1 and the final peg in (2n-2), where n≥2. If n≥5 is odd, then Pn is distance 2-solvable with the initial hole in 1 and the final two pegs in (n-3) and (n-1).Lemma 2.
The graphCSC(2k,m) is solvable with the initial hole in vertex 0, 1, 2, 3, m-3, m-2, m-1, m, m+1, m+2, m+3, 2k-3, 2k-2, 2k-1, or c. The graph CSC(2k+1,m) is solvable with the initial hole in vertex 0, 2, m-2, m, m+2, or 2k-1.Proof.
Note that the verticesi and i+m(modn) are symmetric.
ForCSC(2k,m), suppose the initial hole is in vertex 0; jump  m·c→·0. An even path subgraph is formed by m-1, m,…,2k-1, 0,…,m-2 with a hole in m. This subgraph is solvable with the final peg in m-3 by [3]. Alternately, an even path is formed by m+1, m, m-1,…,0,  2k-1,…,m+2 with a hole in m. Solve this path with the final peg in m+3. By Theorem 1, the graph may also be solved with the initial hole in m-3 or m+3. A similar argument holds if the initial hole is in m, 3, or 2k-3.
Suppose that the initial hole is in 1. Jumpc·0→·1. Solve the even cycle formed by the remaining pegs with a hole in 0. A similar argument holds when the initial hole is in m-1, m+1,or 2k-1.
Suppose that the initial hole is in 2. Jump0·1→·2. Solve the even path formed by the remaining pegs with a hole in 0. A similar argument holds for the case when the initial hole is in m-2, m+2, or 2k-2.
Suppose that the initial hole inc. Jump 1 over 0 into c. Solve the even path formed by the remaining pegs with a hole in 0.
ForCSC(2k+1,m), suppose the initial hole is in vertex 0. An even path is formed by c, 0, 1,…,2k with a hole in 0. Solve this path with the final peg in 2k-1. Alternately, an even path is formed by c, 0, 2k, 2k-1,…,1 with a hole in 0. Solve this path with the final peg in 2. By Theorem 1, the graph may also be solved with the initial hole in 2k-1 or 2. A similar argument holds when the initial hole is in m, m-2, or m+2.We now give some freely solvable examples of this type of graph.Theorem 3.
The graphCSC(2k,4) is freely solvable.Proof.
If the initial hole is in vertex{2k-3,2k-1,0,1,…,7,c}, then the graph is solvable by Lemma 2.
Suppose the initial hole is ini, where i is even and 8≤i≤2k-4. An even path is formed by i-1, i,…,0, c, 4 with a hole in i. Solve this path, ending in c. Then jump  2·1→·0, 0·c→·4, and 3·4→·c. Finally, solve the even path with a hole in 4, formed by c, 4, 5,…,i-2.
Suppose the initial hole is inj, where j is odd and 9≤j≤2k-5. An even path is formed by j-1, j,…,2k-1 with a hole in j. Solve this path, ending in 2k-2. Then jump  c·0→·2k-1, 2k-2·2k-1→·0, 1·0→·c, 4·c→·0, and 2·3→·4. Finally, solve the even path with a hole in c, formed by 0, c, 4, 5,…,j-2.Theorem 4.
The graphCSC(2k,1) is freely solvable.Proof.
If the initial hole is in vertex{2k-3,2k-1,0,1,2,4,c}, then the graph is solvable by Lemma 2.
Suppose the initial hole is ini, where i is even and 6≤i≤2k-4. An even path is formed by i+1, i,…,1, c with a hole in i. Solve this path, ending in 1. Then jump  1·0→·c. Finally, solve the even path with a hole in 1, formed by c, 1,…,i+2.
Suppose the initial hole is inj, where j is odd and 3≤j≤2k-5. An even path is formed by j-1, j,…,2k-1, 0, c with a hole in j. Solve this path, ending in 0. Now jump  1·0→·c. Finally, solve the even path with a hole in 1, formed by c, 1,…,j-2.Note thatCSC(2k,1) is isomorphic to the graph formed from C2k+1 by adding a chord between vertices 0 and 2. Thus, this provides partial progress on the open question from [5] as to whether all chorded odd cycles are freely solvable.Theorem 5.
The graphCSC(2k+1,3) is freely solvable.Proof.
If the initial hole is in vertex0, 1, 2, 3, 5, or 2k-1, then the graph is solvable by Lemma 2.
Suppose the initial hole is ini, where i is even and 4≤i≤2k. An even path is formed by i-1, i,…,2k,0,1 with a hole in i. Solve this path, ending in 0. Then jump  3·2→·1 and  0·c→·3. Finally, solve the even path with a hole in 2, formed by 1, 2,…,i-2.
Suppose the initial hole is inj, where j is odd and 7≤j≤2k-3. An even path is formed by j-1, j,…,2k,0 with a hole in j. Solve this path, ending in 2k. Then jump  3·c→·0,  1·2→·3,  2k·0→·c, and  c·3→·2. Finally, solve the even path with a hole in 3, formed by 2,3,…,j-2.
Suppose the initial hole is inc. Jump  2·3→·c and  0·c→·3. Solve the even path formed by the remaining pegs with a hole in 2.It is currently unknown ifCSC(n,m) is freely solvable for other values of n and m.


## 3. The Mesh and Related Graphs

In [3], it is shown that, if G is solvable or distance 2-solvable and H is solvable or distance 2-solvable, then the cartesian product G□H is solvable. We now consider a specific case of when such graphs are freely solvable, namely, meshes Pn□Pm. If n or m is even, then Pn□Pm is Hamiltonian and has an even number of vertices. Hence, it is freely solvable by [3]. Thus, it suffices to consider the case where both n and m are odd. Label the vertex of G□H induced by g∈V(G) and h∈V(H) by (g,h).Lemma 6.
Form≥3, there exists a peg solitaire solution to the mesh Pm□P3 such that (i) the initial jump is  (m-1,2)·(m-1,1)→·(m-1,0) and (ii) the final peg is in vertex (m-2,0).Proof.
Proceed by induction onm. An exhaustive computer search [8] shows that the claim holds for m=3. Assume the claim holds for Pm□P3, and consider Pm+1□P3. With the initial hole in vertex (m,0), jump  (m,2)·(m,1)→·(m,0),  (m-1,2)·(m-1,1)→·(m,1), and  (m-2,2)·(m-2,1)→·(m-1,1). The Pm-1□P3 subgraph is solvable by hypothesis, ending in (m-3,0). Now jump  (m,0)·(m-1,0)→·(m-2,0),  (m-3,0)·(m-2,0)→·(m-1,0),  (m-1,1)·(m-1,0)→·(m,0), and  (m,1)·(m,0)→·(m-1,0) to solve the graph.Lemma 7.
The meshP2k+1□P3 is freely solvable with the final peg in vertex (2k-1,0).Proof.
Proceed by induction onk. If k=1, then use Lemma 6. Assume the claim holds for P2k+1□P3, and consider P2k+3□P3. Lemma 6 shows that the claim holds with the initial hole in vertex (2k+2,0).
Case
1. Suppose the initial hole is in (i,j), where 0≤i≤2k and 0≤j≤2. The P2k+1□P3 subgraph is solvable by hypothesis, ending in (2k-1,0). Now jump  (2k+2,0)·(2k+1,0)→·(2k,0),  (2k-1,0)·(2k,0)→·(2k+1,0),  (2k+2,2)·(2k+2,1)→·(2k+2,0),  (2k+1,2)·(2k+1,1)→·(2k+2,1),  (2k+2,0)·(2k+1,0)→·(2k+1,1), and  (2k+2,1)·(2k+1,1)→·(2k+1,0) to solve the graph.
Case
2. Suppose the initial hole is in (2k+1,0). Jump (2k,1)·(2k+1,1)→·(2k+1,0) and  (2k,2)·(2k+1,2)→·(2k+1,1). The P2k+1□P3 subgraph is solvable by hypothesis, ending in (2k-1,0). Finally, jump (2k+2,0)·(2k+1,0)→·(2k,0),  (2k-1,0)·(2k,0)→·(2k+1,0),  (2k+2,2)·(2k,0)→·(2k-1,0),  (2k+2,2)·(2k+2,1)→·(2k+2,0),  (2k+2,0)·(2k+1,0)→·(2k+1,1), and  (2k+1,2)·(2k+1,1)→·(2k+1,0) to solve the graph.
Case
3. Suppose the initial hole is in (2k+1,1). Jump  (2k,2)·(2k,1)→·(2k+1,1). The P2k+1□P3 subgraph is solvable by Lemma 6, ending in (2k-1,0). This reduces the graph to Case 1. Suppose the initial hole is in (2k+1,2). Jump  (2k,1)·(2k,2)→·(2k+1,2). This reduces the graph to the above case.
Case
4. Suppose the initial hole is in (2k+2,1). Jump (2k+1,2)·(2k+1,1)→·(2k+2,1) and  (2k,1)·(2k,2)→·(2k+1,2). The P2k+1□P3 subgraph is solvable by Lemma 6, ending in (2k-1,0). This reduces the graph to Case 2. Suppose the initial hole is in (2k+2,2). Jump  (2k+1,1)·(2k+1,2)→·(2k+2,2) and  (2k,1)·(2k,2)→·(2k+1,2). This reduces the graph to Case 2. The case where the initial hole is in (2k+2,0) is analogous.Theorem 8.
The meshP2k+1□P2n+1 is freely solvable.Proof.
We prove the stronger statement thatP2k+1□P2n+1 is freely solvable with the final peg in vertex (2k-1,2n), which is symmetric to vertex (2k-1,0). Proceed by induction on n. If n=1, then the claim holds by Lemma 7. Assume the claim holds for P2k+1□P2n+1, and consider P2k+1□P2n+3.
Case
1. Suppose the initial hole is in (i,j), where j≤2n. The subgraph P2k+1□P2n+1 is solvable by hypothesis, ending in (2k-1,2n). Now jump  (2k-1,2n+1)·(2k-2,2n+1)→·(2k-2,2n) and (2k-1,2n)·(2k-2,2n)→·(2k-2,2n+1). The remaining pegs form an even path with a hole in (2k-1,2n+1). Solve this path with the final peg in (2k-1,2n+2).
Case
2. Suppose the initial hole is in (i,2n+2). Jump (i,2n)·(i,2n+1)→·(i,2n+2). A hole is now in (i,2n). Solve the P2k+1□P2n+1 subgraph by hypothesis, ending in (2k-1,2n).
Ifi=2k-1, then jump  (2k-3,2n+1)·(2k-2,2n+1)→·(2k-2,2n),  (2k-2,2n)·(2k-1,2n)→·(2k-1,2n+1), and  (2k,2n+1)·(2k-1,2n+1)→·(2k-2,2n+1). The remaining pegs form an even path with a hole in (2k-3,2n+1). Solve this path with the final peg in (2k-1,2n+2).
Ifi=2k-2, then jump  (2k-1,2n)·(2k-1,2n+1)→·(2k-2,2n+1). If i=2k, then jump  (2k-1,2n)·(2k-1,2n+1)→·(2k,2n+1). In either case, this reduces the graph to Case 1.
Ifi∉{2k-1,2k-2}, then jump  (2k-1,2n+1)·(2k,2n+1)→·(2k,2n) and  (2k,2n)·(2k-1,2n)→·(2k-2,2n).
Ifi=0, then, for j=1,…,2k-3, jump  (2k-j-1,2n+1)·(2k-j-1,2n)→·(2k-j-2,2n). Now jump  (1,2n+2)·(0,2n+2)→·(0,2n+1), (0,2n+1)·(1,2n+1)→·(2,2n+1),  (2,2n+2)·(2,2n+1)→·(1,2n+1), and  (1,2n)·(1,2n+1)→·(1,2n+2). The remaining pegs form an even path with a hole in (2,2n+2). Solve this path with the final peg in (2k-1,2n+2).
Ifi≠0, then, for j=1,…,2k-i-2, jump (2k-j-1,2n+1)·(2k-j-1,2n)→·(2k-j-2,2n). If i is odd, then the remaining pegs form an even path with a hole in (i,2n+1). Solve this path with the final peg in (2k-1,2n+2). If i is even, then (0,2n+1), (1,2n+1),…,(i,2n+1), (i,2n) form an even path with a hole in (i,2n+1). Solve this path, ending in (1,2n+1). Now jump  (1,2n+2)·(0,2n+2)→·(0,2n+1),  (0,2n+1)·(1,2n+1)→·(2,2n+1), and  (2,2n+1)·(2,2n+2)→·(1,2n+2). The remaining pegs form an even path with a hole in (2,2n+2). Solve this path with the final peg in (2k-1,2n+2).
Case
3. Suppose the initial hole is in (i,2n+1). Jump (i+1,2n)·(i+1,2n+1)→·(i,2n+1) or  (i-1,2n)·(i-1,2n+1)→·(i,2n+1). In either case, this reduces the graph to Case 2.It follows from Theorem8 that the cylinderCn□Pt is freely solvable. The generalized web is obtained from Cn□Pt by appending a pendant vertex zi to (i,t-1) for i=0,…,n-1. Similarly, the generalized wheel is obtained from Cn□Pt by adding a new vertex c such that c is adjacent to (i,0) for i=0,…,t-1. Finally, the generalized helm is obtained from the generalized wheel by appending a pendant vertex zi to (i,t-1) for i=0,…,n-1.Corollary 9.
The generalized web, generalized wheel, and the generalized helm are freely solvable forn≥3 and t≥2.Proof.
We first show that a mesh of even order may be solved with the final peg in an outermost vertex. ForP2k+1□P2n, suppose the initial hole is in vertex (i,j). Without loss of generality, assume j≤2n-2. Solve the P2k+1□P2n-1 subgraph ending in (2k-1,2n-2). Jump  (2k-1,2n-1)·(2k,2n-1)→·(2k,2n-2),  (2k,2n-2)·(2k-1,2n-2)→·(2k-2,2n-2), and  (2k-2,2n-2)·(2k-2,2n-1)→·(2k-1,2n-1). The remaining pegs form an even path with a hole in (2k-2,2n-1). Solve this path with the final peg in (1,2n-1).
ForP2k□P2n, suppose the initial hole is in vertex (i,j). Without loss of generality, assume that i≤2k-2. Solve the P2k-1□P2n subgraph, ending in (2k-2,2n-2). The remaining pegs form an even path with a hole in (2k-3,2n-1). Solve this path, ending in (1,2n-1).
For the generalized web, if the hole is in(i,j), then solve the mesh subgraph with the final peg in (0,t-1). Now, jump  zk·(k,t-1)→·(k+1,t-1) for k=0,…,n-1. If the hole is in z0, then jump  (0,t-2)·(0,t-1)→·z0. Next, jump  zi·(i,t-1)→·(i-1,t-1) for i=1,…,n-1. Finally, jump  z0·(0,t-1)→·(0,t-2). Ignoring the pendants, the graph is a mesh after the first jump.
For the generalized wheel, if the hole is in(i,j), then solve the mesh subgraph with the final peg in (0,0). Now jump  c·(0,0)→·(1,0). If the hole is in c, then jump  (0,0)·(1,0)→·c. This reduces the graph to the case of the mesh after the first jump.
For the generalized helm, if the hole is in(i,j) or zi, then solve the generalized web subgraph with the final peg in (0,0). Now jump  c·(0,0)→·(1,0). If the initial hole is in c, then solve the wheel subgraph, ending in (0,t-1). Now, jump  zk·(k,t-1)→·(k+1,t-1) for k=0,…,n-1.


## 4. The Fat Triangle

We now construct thefat polygon, denoted by Fp(n;a0,a1,…,an-1). Label the vertices of Cn, with x0, x1,…,xn-1. Replace the edge between xi and xi+1(modn) with ai edges, where ai≥1. For j=1,…,ai, place a new vertex, yi,j, on the jth edge between xi and xi+1(modn). So xiyi,j and yi,jxi+1(modn)∈E(Fp(n;a0,a1,…,an-1)). Further, let Ai={yi,j:j=1,…,ai}. In this section, we show that Fp(3;a0,a1,a2) (i.e., the fat triangle) is freely solvable (see Figure 5). Without loss of generality, we assume a0≥a1≥a2≥1.Figure 5
Fat triangleFp(3;4,3,2).Theorem 10.
The fat triangle is freely solvable for alla0,a1,a2≥1.Proof.
For convenience of exposition, we define and solve the following configurations.
Configuration
A. Suppose there are pegs in vertices x0, y0,1, y0,2,…,y0,i and a hole in x1. If i=1, then jump  x0·y0,i→·x1, ending in x1. If i≥2 is even, say i=2t, then, for t=1,…,t, jump  x0·y0,2t-1→·x1 and  x1·y0,2t→·x0, ending in x0. If i≥3 is odd, then make the additional jump  x0·y0,i→·x1, ending in x1.
Configuration
B. Suppose there are pegs in vertices x0, y0,1, y0,2,…,y0,i and y1,1, y1,2,…,y1,i and holes in x1 and x2. If i=1, then jump  x0·y0,1→·x1 and  x1·y1,1→·x2, ending in x2. If i≥2 is even, say i=2t, then, for t=1,…,t, jump  x0·y0,2t-1→·x1,  x1·y1,2t-1→·x2,  x2·y1,2t→·x1, and  x1·y0,2t→·x0, ending in x0. If i≥3 is odd, then perform the additional jumps  x0·y0,i→·x1 and  x1·y1,i→·x2, ending in x2.
Case
1. If a0=a1=a2=1, then the graph is C6, which is freely solvable by [3]. If a0=a1=a2≥2, then it suffices to show solutions with the initial hole in vertices x0 and y1,1.
Suppose the initial hole is inx0. Jump  x1·y0,1→·x0,  y2,1·x0→·y0,1,  x2·y1,1→·x1, and  x1·y0,1→·x0. Now jump  x0·y0,i→·x1,  x1·y1,i→·x2, and  x2·y2,i→·x0, for i=2,…,a0, to eliminate the a0-1 remaining pegs in A0, A1, and A2. This solves the graph with the final peg in x0. The final jump could also be  y2,a1·x2→·y1,1. Thus, by Theorem 1, the graph can also be solved with the initial hole in y1,1 and the final peg in x0.
Case
2. If a0>a1=a2, then it suffices to show solutions with the initial hole in vertices x0, y0,1, x2, and y2,1.
Suppose the initial hole is inx0. Solve the Fp(3;a1,a1,a1) subgraph, ending in x0, as in Case 1. Now use the method described in Configuration A to eliminate the a0-a1 remaining pegs in A0. If a0-a1 is even, then the final peg is in x0. However, the final jump could also be  y0,a0·x1→·y0,1. If a0-a1 is odd, then the final peg is in x1. However the final jump could also be  y0,a0·x0→·y0,1. In either case, the graph can be solved with the initial hole in y0,1 by Theorem 1.
Suppose the initial hole is inx2. Jump  x1·y1,1→·x2,  x0·y0,a0→·x1, x2·y2,1→·x0, and  y0,1·x1→·y0,a0. Use the method of Configuration A to eliminate the remaining a0-1 pegs in A0. If a1=1, then this solves the graph. If a0-1 is even, then the final peg is in x0. If a0-1 is odd, then the final peg is in x1. If a1≥2, then use the method described in Configuration B to eliminate the remaining a1-1 pegs in A1 and A2. If a0-1 and a1-1 have the same parity, then the final peg is in x0. Otherwise, the final peg is in x1.
Suppose the initial hole is iny2,1. Jump  y0,1·x0→·y2,1. If a0=a1+1, then this reduces the graph to Case 1. If a0≥a1+2, then this reduces the graph to the case of the initial hole in x0.
Case
3. If a0=a1>a2, then it suffices to show solutions with the initial hole in vertices x0, y0,1, y2,1, and x1.
Suppose the initial hole is inx0. Solve the Fp(3;a2,a2,a2) subgraph, ending in x0, as in Case 1. Now use the method described in Configuration B to eliminate the remaining a0-a2 pegs in A0 and A1. As in Case 2, the graph may also be solved with the initial hole in y0,1.
Suppose the initial hole is in vertexy2,1. First jump  y0,a0·x0→·y2,1. If a0=2, then this reduces the graph to Case 1. Assume that a0≥3. Jump  x1·y0,1→·x0,  y0,2·x0→·y0,a0,  x2·y1,1→·x1, and  x1·y1,2→·x2. Now use the method described in Configuration A to eliminate the a2 pegs in A2. If a2 is even, then the ending peg is in x2. If a2 is odd, then the ending peg is in x0. Next use the method described in Configuration B to eliminate the remaining a0-2 pegs from A0 and A1. If a0-2 and a2 have the same parity, then the final peg is in x2. Otherwise, the final peg is in x0.
Suppose the initial hole is inx1. Jump  x0·y0,1→·x1,  x2·y2,1→·x0,  x1·y1,1→·x2, and  y0,2·x0→·y0,1. If necessary, use the method described in Configuration A to eliminate the remaining a2-1 pegs in A2. If a2-1 is even, then the ending peg is in x2. If a2-1 is odd, then the ending peg is in x0. Next use the method described in Configuration B to eliminate the remaining a0-1 pegs from A0 and A1. If a2-1 and a0-1 have the same parity, then the final peg is in x2. Otherwise, the final peg is in x0.
Case
4. If a0>a1>a2≥1, then the graph may be reduced to a solvable configuration with the initial hole in each vertex.(i)
Suppose the initial hole is inx0. Use the method described in Configuration A to eliminate a0-a1 pegs from A0. If a0-a1 is even, then the ending peg is in x1. If a0-a1 is odd, then the ending peg is in x0. This reduces the graph to Case 3. The case where the initial hole is in x1 is analogous.(ii)
Suppose the initial hole is inx2. Use the method described in Configuration A to eliminate a1-a2 pegs from A1. This reduces the graph  to Case 2.(iii)
Suppose the initial hole is iny0,1. Jump  y0,a0·x0→·y0,1. This reduces the graph to Case 3 or 4(i). The cases where the initial hole is in y1,1 or y2,1 are analogous.


## 5. Open Problems

We end this paper by listing a few open problems as possible avenues for future research. (i) What other graphs are freely solvable? (ii) Is the corona of a (freely) solvable graph likewise (freely) solvable? (iii) What is the solvability of a cycle with a chord that is subdivided multiple times? (iv) For what graphs is it possible to start with a specific initial jump and end with another specific jump? (v) Suppose that we want to start with our initial hole in any vertexs and end with our final peg in any vertex t. For what graphs is this possible? (vi) What is the solvability of other fat polygons?



---

*Source: 605279-2013-09-02.xml*