top of page
RESEARCH
Peg Solitaire on Caterpillars: Making Them Solvable
SEBASTIAN LOZANO, Harvard College '25
THURJ Volume 15 | Issue 1
Abstract
Peg solitaire is a classic game where players aim to remove pegs from a board via a jump move. In the context of graph theory, this game introduces an interesting challenge: for a given graph G, how many edges must be added to make it solvable in peg solitaire? This quantity is known as the minimal solvability number, ms(G). We study the ms(G) specifically for caterpillar graphs, identifying types with known minimal solvability numbers and exploring families, such as caterpillars of length 3, that remain unsolved. For this family, we provide upper bounds on the ms(G) and identify cases where ms(G) = 1.
Overview
This paper is broken down into 5 sections. In section 1, we give an introduction of our topic. This is followed by section 2, which discusses the known minimal solvability number of shorter caterpillars. We discuss their solvability and overall minimal solvability number. We then follow with our main results in section 3, which focuses on giving the upper bounds on the minimal solvability number for caterpillars of length 3. We finally finish our content with section 4, which gives specific examples of caterpillars of length 3 in which we know have minimal solvability number ms(G) = 1. Section 5 discusses possible open questions for further research.
Introduction
Peg solitaire is a traditional one-player game where a player has a board with cells where all but one are filled with pegs. A move in peg solitaire is known as a jump. A jump consists of three adjacent spaces, where the first two vertices have a peg, and the last vertex is a hole. A player would use the first peg to jump over the peg it is adjacent to into the empty hole. A player's objective is, through a series of jumps, to get rid of all the pegs on the board until left with only one. This game is traditionally played on an English cross shaped board (de Wiljes and Kreh, 2022).
Naturally, one can play on different shaped boards which can be as big or as small as desired. In fact, this combinatorial game can be played on boards that resemble arbitrary connected graphs. In 2011, Beeler and Hoilman (Beeler and Hoilman, 2011) generalized the game of peg solitaire to different graphs. Pegging moves on graphs, focusing on questions like how many pegs must one put on a graph so that, with any given distribution of pegs on any empty vertex v, one can find a sequence of jumps that places a peg at vertex v, were also studied in 2009 and 2006 respectively (Niculescu and Niculescu, 2009; Helleloid et al., 2006). A recent 2022 survey by de Wiljes and Kreh collects many papers in the peg solitaire literature. Similar to the cross board, we can play peg solitaire on a connected graph, G = (V, E), by filling in every vertex but one with a peg. One vertex must be left empty, which we will refer to as the starting hole.
To describe an arbitrary jump, let us say we are given 3 adjacent vertices, a, b, c, where the first two have pegs and the last is a hole. A jump move then uses the peg in a to jump over the second peg in b into the empty hole in c, which we will denote as ab-c. Upon performing this jump, the peg that was jumped over is removed, meaning we are now left with holes in a and b while c now has a peg. With every jump, a player always removes one peg and one peg only. Given a graph with n vertices for n ∈ N, the maximum number of moves a player can perform is (n-2); by that point, a player would only have one peg remaining, winning the game.
Though the goal of peg solitaire is to remove all but one peg, achieving this isn't possible on every graph due to structural constraints. Some graphs inherently lack a configuration that allows a single remaining peg, making them unsolvable. To systematically study which graphs can be made solvable, we will introduce terminology and concepts developed by de Wiljes and Kreh specifically for peg solitaire on graphs (2022):
When beginning the game, we have a starting state S ⊆ V of empty vertices, which will always be a single vertex. After playing a game, we end up with a terminal state T ⊆ V of vertices with pegs and no more jumps are possible. We say T is associated to S if T can be reached from S through a sequence of jumps. With this in mind, we get the following:
Definition 1.1. A graph G is solvable if there is some v ∈ V such that the starting state S = {v} has an associated terminal state consisting of a single vertex.
Definition 1.2. A graph G is k-solvable if there is some v ∈ V such that the starting state S = {v} has an associated terminal state consisting of k vertices.
For the sake of this paper, we will only refer to a graph G as k-solvable if there exists no j ∈ N where j < k such that the graph is also j-solvable, no matter where the starting hole is assigned. In other words, the graph cannot be solved with an end state smaller than k. A k-solvable graph will have solitaire number Ps(G) = k. Knowing the solvability of graphs is important for determining the following graph invariant. The minimal solvability number ms(G) is the smallest number of edges that have to be added to a graph G in order to make it solvable (de Wiljes and Kreh, 2022) where an 'edge' represents a connection between two pegs.
The minimal solvability number ms(G) has been found for various graph classes such as complete graphs, path graphs, cycles, stars, and double stars (de Wiljes and Kreh, 2022). De Wiljes and Kreh point out that one "[has] to start with adding edges instead of solving the original graph first," meaning that edges must be appended first before solving the graph (2022). Furthermore, since the complete graph (a graph where all vertices are connected to each other by edges) is solvable and it is possible to add edges to any graph until it becomes complete, we know that the minimal solvability number ms(G) exists for any graph G.
De Wiljes and Kreh pose a natural question about determining the minimal solvability number ms(G) of different classes of graphs. In this paper, we focus on caterpillar graphs, a type of graph consisting of a central 'spine' of vertices with smaller branches, or 'legs,' extending from it. We examine the minimal solvability number ms(G) for various types of caterpillar graphs. Some caterpillars are isomorphic to graphs for which we know the minimal solvability number ms(G); these will be discussed and presented. More importantly, we establish precise upper bounds on the minimal solvability number ms(G) for a previously unknown caterpillar graph - specifically, caterpillars of length 3. These bounds significantly advance our understanding of the minimal solvability number ms(G) for this family. Some caterpillars of length 3 can also easily be solved with only adding one edge, so we also give examples of families of caterpillars of length 3 that have ms(G) = 1. The following proposition will be used to help with our results:
Proposition 1.1 [8, Proposition 1.1]. For every connected graph G = (V, E), ms(G) ≤ Ps(G) - 1.
Figure 1. A jump move in peg solitaire.
Figure 2. Adding an edge to improve solvability.
Figure 3. Examples of complete, path, cycle, star, and double star graphs.
Known Caterpillar Graphs
A caterpillar graph can be constructed from a path of length n by appending an arbitrary number of pendant vertices to each vertex on the path. The path with pendants attached to each of its vertices will be known as the spine of the caterpillar (Beeler et al., 2017). See Figure 4 below:
We want to categorize different caterpillars and determine their minimal solvability number ms(G). Through the study of the literature surrounding peg solitaire and minimal solvability number ms(G) of graphs, we are able to categorize some caterpillars and assign them a respective minimal solvability number ms(G). One simple category of caterpillars consists of caterpillars of length n with zero pendants attached to every vertex on its spine. Without the caterpillar's pendants, we are only left with the spine of the caterpillar, which by construction is a path of length n. These graphs are isomorphic to the common path graphs, in which we know their minimal solvability number.
Proposition 2.1 [3, Theorem 2.3]. Let P be the path on n vertices where n ∈ N. If we have P₂n or P₃, then this graph has ms(G) = 0. If we have P₂n+1 for n > 1, this graph has ms(G) = 1.
This result follows immediately from the fact that paths of even length or length 3 are solvable while paths of odd length for an odd number greater than 3 are 2-solvable (Beeler and Hoilman, 2011). Combined together with Proposition 1.1, we were able to get the given result.
Following this categorization, we now consider caterpillars with pendants attached to its spine since pendants are a notable feature of a caterpillar. For the remainder of this paper, we will be referring to caterpillars of length n. When mentioning said caterpillars, the lengths refer to the length of its spine, not including any extra length that could be considered with any of the caterpillar's pendants.
That being said, let us now consider the smallest length caterpillar: a caterpillar of length one. This caterpillar will have the following notation: Cat₁(n) where n is the number of pendants attached to the single vertex on its spine. These caterpillars are isomorphic to another graph with a known solvability and minimal solvability number, the star graphs. In general, a caterpillar of length 1 with n pendants is at best (n-1)-solvable due to the nature of an empty spine vertex. If the starting hole was in the spine, no moves are possible since we would have no 2 adjacent pegs. If the starting hole was in a pendant, one can at most move from another pendant, over the spine, into the hole. Thus, (n-1) pegs would still remain, showing it is unsolvable. Because of how unsolvable these caterpillars are, the minimal solvability number ms(G) increases with the number of pendants.
De Wiljes and Kreh determine the minimal solvability number ms(G) of star graphs by appending edges between pendants to form a sort of 'windmill blade.' Due to how they look, we will be referring to edges that connect two pendants as blades edges for the remainder of the paper. De Wiljes and Kreh ultimately prove the following result.
Proposition 2.2 [8, Corollary 2.1]. Let Cat₁(n) be a caterpillar of length 1 with n pendants. If n ≥ 3, then
To solve caterpillar graphs of length 1 with additional blade edges, we begin by placing the initial empty hole in a pendant. From here, the solution proceeds in steps:
-
Start by jumping a peg over the central spine into the empty hole.
-
Since there exists blades, we can jump via this blade back into the empty central spine.
-
With another pendant, jump into a pendant that has a blade edge. Depending on the number of pendants in our original caterpillar of length 1, we either have another blade or our graph is solvable.
Through this process, we can achieve solvability by a sequence of systematic jumps. A detailed algorithmic jump sequence is available in (de Wiljes and Kreh, 2022).
Naturally, the next caterpillar we consider is a caterpillar of length 2. This caterpillar will have the following notation: Cat₂(L, R) where L is the number of pendants attached to the left center and R is the number of pendants attached to the right center where L, R ∈ N. This is the final caterpillar in which we know its minimal solvability number since it is also isomorphic to a known graph - a double star graph. The solvability of caterpillars of length 2 is known and proved by the following.
Proposition 2.3 [4, Theorem 3.1]: Let L ≥ R ≥ 1. Then, Cat₂(L, R) is solvable if L ≤ R + 1.
These caterpillars of length 2 by construction have ms(G) = 0, and the following result is known about its general minimal solvability number ms(G).
Proposition 2.4 [8, Proposition 2.5]: Let L ≥ R ≥ 1. Then, ms(Cat₂(L, R)) = [(L-R-1)/4].
A full explanation on why this works is outlined by de Wiljes and Kreh (2022). In essence, the authors consider appending edges in between left pendants and perform a specific algorithmic jump set according to whether L - R = 0, 1, 2, or 3 mod 4. So far, we have considered a variety of different caterpillars and have given the minimal solvability number based on its construction. We considered the number of pendants and total length of the caterpillar. Up to now, the given caterpillars were isomorphic to graphs in which we knew their minimal solvability number ms(G). Next, we are going to showcase properties of the minimal solvability number ms(G) of an unknown graph.
Figure 4. A caterpillar of length 3.
A New Caterpillar Graph
After determining the minimal solvability number ms(G) of caterpillars of length 1 and 2, we are now interested in finding the minimal solvability number ms(G) of caterpillars of length 3. Unlike the previous caterpillars we have seen, caterpillars of length 3 are not isomorphic to a graph with a known minimal solvability number ms(G), meaning it cannot simply be presented as we have previously been doing. This raises a natural question: what is the most effective method for appending edges to caterpillars of length 3 in order to be able to solve them? Determining an optimal strategy for their placement becomes essential. To address this, we need to consider both the structure of the caterpillar and the specific arrangement of pendants, as these factors influence which configurations are solvable. We explore approaches for appending edges that minimize the number of edges needed.
In order to distinguish the vertices of a caterpillar of length 3, we are going to assign a specific name to each of the vertices, depending on where they are. Suppose you are given a caterpillar of length 3. This caterpillar will have the notation Cat₃(L, C, R) where L is the number of pendants attached to the leftmost spine vertex, C is the number of pendants attached to the center spine vertex, and R is the number of pendants attached to the rightmost spine vertex. Along with the 3 spine vertices, this caterpillar has
a total of L + R + C + 3 vertices. For the vertices on the spine, we will refer to the leftmost spine, center spine, and rightmost spine vertices at S_L, S_C, and S_R, respectively. The L pendant vertices will be named l₁, l₂, ..., l_L, the R pendant vertices will be named r₁, r₂, ..., r_R, and the C pendant vertices will be named c₁, c₂, ..., c_C.
With terminology for the vertices of the caterpillar established, we now turn to determining the minimal solvability number ms(G) for caterpillars of length 3. The simplest case occurs when ms(G) = 0, indicating that the caterpillar is naturally solvable without adding edges. This leads us to a central question: under what conditions is a caterpillar of length 3 solvable?
While there is no study specifically focused on the solvability of caterpillars of length 3, we can still draw conclusions about their solvability by examining trees with diameter 4. Beeler and Walvoort (2015) demonstrate that any tree of diameter 4 can be constructed by appending pendant vertices to a star graph with n pendants. The structural relationship between caterpillars of length 3 and trees of diameter 4 allows us to leverage known results about these trees to make deductions about caterpillar solvability. In particular, the following proposition specifies the conditions under which a caterpillar of length 3 is solvable. This result was specialized for graphs with diameter at most 4.
Proposition 3.1 [5, Theorem 3.1]: Let L ≥ 2 and L ≥ R ≥ 1. Then, Cat₃(L, C, R) is solvable if
(L + R) - 2 ≤ C ≤ (L + R) + 1.
Furthermore, the graph is k₁-solvable, where k₁ ≤ L + R - C - 1 if C ≤ (L + R) - 3. Also, it is k₂-solvable, where k₂ ≤ C - L - R if C ≥ (L + R) + 2.
We then can see that if (L + R) - 2 ≤ C ≤ (L + R) + 1 where L ≥ 2 and L ≥ R ≥ 1, then the caterpillar of length 3 has ms(G) = 0. When approaching a caterpillar of length 3, one should first consider if C is within these bounds in order to see if it is originally solvable. More importantly in regard to the minimal solvability number ms(G), these caterpillars are unsolvable if C ≤ (L + R) - 3 or if C ≥ (L + R) + 2.
Before presenting our results, we introduce a key tool for analyzing the solvability of caterpillars of length 3. Defined by Beeler and Walvoort (2015), this tool involves configuring pegs and holes so that a specific sequence of jumps removes certain pegs while others stay constant. This setup, termed a package, is associated with an elimination process called a purge, which selectively reduces pegs on the graph. Among the various purges, the Double Star Purge is particularly valuable because it enables a systematic reduction of pendants, thereby simplifying the caterpillar's structure.
In the Double Star Purge, which applies to double star graphs (caterpillars of length 2), if the starting hole is positioned in either the left or right center, we can reduce the number of pendants on each side by k ∈ N, provided k ≤ min(L, R). For example, if the hole starts in the right center, we perform the Double Star Purge by first jumping from a left pendant over the left center into the hole in the right center, followed by a jump from a right pendant over the right center into the left center. After these jumps, the number of pendants on each side is reduced by 1, and the hole returns to its original position.
For caterpillars of length 3, we can leverage the Double Star Purge by focusing on specific sides of the caterpillar. For example, we can consider only the L left and C center pendants along with the center vertices S_L and S_C so that we work with a double star. Then, we can apply the Double Star Purge to systematically simplify this side of the caterpillar. The same principle applies if we consider the R right and C center pendants, as well as S_R and S_C. This technique allows us to progressively reduce the number of pendants and approach solvability.
Also, we will consider appending an edge connecting both S_L and S_R. This edge is one of the most efficient ones we can add since a player is able to reduce the L and R pendants by using this edge to perform Double Star Purges. Because of how it makes graphs more efficiently solvable, we will refer to the edge connecting S_L and S_R as the Double Star Edge.
We will also provide an argument as to why blade edges and the double star edge are the most efficient edges to append and are the only edges we consider in this paper. Given an unsolvable caterpillar of length 3 means that C ≤ L + R - 3. One strategy when appending edges is to append the edges that guarantee reducing the most amount of left and right pendants with the effort of getting C outside of this bound, which would make our graph solvable. Whereas any other edge would reduce the number of pendants by 1, blade edges and the double star edge reduces the number of left and right pendants by more than one. For blades, when used correctly, it reduces the number of left or right pendants by 2 when the player jumps into S_L or S_R. Furthermore, with the double star edge, a player is able to reduce the number of pendants from both the left and right side of the caterpillar by k given that k < R. Doing these strategies correctly ensure that our graph becomes more solvable, showing why they may be the best strategy when appending edges and getting an accurate minimal solvability number ms(G) of caterpillars of length 3.
For the most part, caterpillars with a minimal solvability number ms(G) = 0 tend to be balanced, meaning they have a relatively equal number of left and right pendants. This pattern suggests that the closer a caterpillar is to balanced, the lower its minimal solvability number is likely to be. To better understand this relationship, we begin with the caterpillars that are most likely to have the highest minimal solvability number ms(G): those with the most extreme imbalance between left and right pendants. By establishing an upper bound in this highly unbalanced scenario, we can work closer to finding a true equality. Let us consider a caterpillar where (L=n), (R=1), and (C=0), which is the most unbalanced that a caterpillar can get.
Theorem 3.1. Let L ≥ R ≥ 1 and n∈N. Given Cat₃(n, 0, 1), it has
ms(Cat3(n,0,1))≤1+⌈4n−3⌉.
Proof. If n = 1, we have P₅, which has ms(G) = 1 according to Proposition 2.1. Now, let n ≥ 2. Put the starting hole in S_C and append the double star edge. Perform the following 2 jumps: l_n⋅S_L⋅S_C where we jump from a left pendant over the left spine into the hole in the center spine and jump from the right spine over the center spine into the left spine. The remaining pendants, peg in S<0xE2><0x82><0x99>, hole in S<0xE2><0x82><0x99> and double star edge create a sub-graph that is a caterpillar of length 2 where L = n - 1 and R = 1. By Proposition 2.4, this sub-graph has ms(G) = ⌈(n-1-1)/4⌉ = ⌈(n-3)/4⌉. Since we also added the double star edge, the number of edges we added to make the caterpillar solvable was 1 + ⌈(n-3)/4⌉, suggesting that this caterpillar has ms(G) ≤ 1 + ⌈(n-3)/4⌉.
Figure 5. A Double Star Purge.
Discussion
...
References
...
bottom of page