# Combinatorial Analysis of a Subtraction Game on Graphs

Authors: Richard Adams; Janae Dixon; Jennifer Elder; Jamie Peabody; Oscar Vega; Karen Willis
Journal: International Journal of Combinatorics
 (2016)

---

## Abstract

We define a two-player combinatorial game in which players take alternate turns; each turn consists of deleting a vertex of a graph, together with all the edges containing such vertex. If any vertex became isolated by a player’s move then it would also be deleted. A player wins the game when the other player has no moves available. We study this game under various viewpoints: by finding specific strategies for certain families of graphs, through using properties of a graph’s automorphism group, by writing a program to look at Sprague-Grundy numbers, and by studying the game when played on random graphs. When analyzing Grim played on paths, using the Sprague-Grundy function, we find a connection to a standing open question about Octal games.


---

## Body

## 1. Introduction

In this article we define a two-person game played on the vertices of a graph and then study it to find strategies for either player to win. The analysis of the game ends up depending heavily on the family of graphs considered at the time. This is why, in this article, we will consider a wide variety of tools from game theory, combinatorics, and group theory, plus some programming, to attack this problem. In the following section we will cover some basic notation and definitions that will be useful throughout the paper, as well as the actual game play.AgraphG=(V,E) is a set V of vertices and a set E of edges connecting pairs of vertices. In this work we consider only graphs that are finite, simple, and undirected. As customary, thedegree of a vertex v, denoted as deg(v), is the number of edges that are incident with v. We say that a vertex v isisolated if deg(v)=0. A graph is said to be connected if, given any two vertices u,v∈V(G), there is a path in G from u to v. Two graphs are said to bedisjoint when their vertex sets are disjoint; we will use the notation G∪H for the graph formed by two disjoint graphs, G and H. Thejoin of two graphsG and H, denoted as G+H, is the graph with vertex set V(G+H)=V(G)∪V(H) and edge-set E(G+H)=E(G)∪E(H)∪{vw;v∈V(G),w∈V(H)}. Finally, we will denotepaths,cycles, andwheels by Pn, Cn, and Wn, respectively, where n is the number of vertices in the graph, and G¯ will denote the graph with V(G¯)=V(G) and edges connecting only vertices that were not connected in G. More information about graphs may be found in [1].In order to define our game we rephrase well-known notions in combinatorial game theory for a game played on graphs. For further reading about game theory, we direct the reader to [2].Definition 1.
A two-player game is said to beimpartial if the outcome of the game depends only on which player goes first. A two-player game is said to becombinatorial if both players have perfect information, there is no chance involved, the game ends after a finite number of moves, the game is impartial, and there is no draw. A two-player game is said to benormal if the last player to make a legal move is the winner.Definition 2.
LetG and H be graphs on which a combinatorial game can be played. (1)
IfH is obtained from G after a game move, then we will call H afollower of G in the game.(2)
If, given a graphH, there is a strategy to win for the next player making a move then we will say that H is an Nposition (N is for the next one). If, given a graph H, the next player making a move does not have a strategy to win then H is a Pposition (P is for the previous one).Remark 3.
Not having a strategy to win means the other player has a strategy to win. This follows from the Sprague-Grundy Theorem; see [3, 4]. So, if G is the starting graph and Player 1 will move first, then G being an N position means Player 1 has a strategy to win the game, but if G is a P position then Player 2 has a strategy to win the game.Next we define our game, which we callGrim.Definition 4.
Given a graphH, we define alegal move of Grim on H by a player selecting and consequently deleting a vertex. When this vertex is deleted all edges adjacent to this vertex are also deleted, together with any other vertices (if any) that have become isolated because of the move.
The game starts with Player 1 moving first on a prearranged, starting position, graphG (naturally, if G had any isolated vertices these would be deleted before the first player can move). After that, the two players alternate turns, making legal moves on the follower that resulted from the previous player’s move. They play until all vertices have been deleted. We refer to the winner of the game or winner of the graph as the player who makes the last legal move.Remark 5.
Grim is a normal combinatorial two-player game. Given the nature of the game, we will also say it is a vertex deletion game.Note that changing the starting graph may change the way Grim is played completely. So, in this article we are not just studying a specific game, but a family of games. This property is commonplace in the study of games played on graphs, of which there is a wide variety; see, for example,Node Kayles in [5] and [6],Connect-it [7], andTake Turn [8] and other similar games in [9–11].Our interest in the subject of games played on graphs is due to the papers by Fukuyama (see [12, 13]), where he studies Nim on graphs.Our study of Grim is split as follows. In Section2 we look at weighted graphs and prove that an extension of Grim to these graphs is unnecessary, as the strategies that could be used to play Grim in weighted graphs are the same as those used to play Grim on certain unweighted graphs. In Section 3 we find winning strategies for when Grim is played on complete or complete multipartite graphs. In Section 4 we look at how certain symmetries in a graph could be exploited to guarantee a victory when Grim is played on such a graph. In Section 5 we study paths, cycles, and other related graphs by using Sprague-Grundy functions; in this way we discover an interesting connection between Grim played on paths and an open problem about Octal games. Finally, in Section 6 we consider random graphs in order to learn whether Player 1 has an overall better chance of winning at Grim.


## 2. Weighted Graphs

It is not unusual to wonder whether a game played on graphs could be extended to be played on graphs with weighted vertices, maybe by thinking about the vertices of the graph as heaps of chips/tokens that can be removed one at a time by players. Of course, this way of playing Grim is similar to the way Nim is played, and thus it has been considered in the past (e.g., [14]). In this section we prove that the natural variation of Grim on weighted graphs is nothing but regular Grim on a different family of graphs.When playing Grim on a weighted graph, we only allow a vertex with weightt to be deleted after it has been selected t times or if it has been completely isolated. Thus, we can create many different games from the same graph by giving each vertex a new random weight.As we studied these graphs, we discovered that we could replace a vertex with weightt with t “regular” vertices that do not share any edges. In order to prove such a claim the concept of a blowup of a vertex becomes necessary.Definition 6.
LetG be a graph with weighted vertices. Let v∈V(G) having weight one and t∈N. A t-blowup of v is an independent set Iv={v1,v2,…,vt} of vertices of weight 1 that “takes the place” of v. More precisely, wherever there was an edge joining v to w∈V(G) there is an edge joining vj with w, for all j=1,…,t.
The graph obtained by thet-blowup of v will be denoted as G(tv). Similarly, for v,w∈V(G) and s,t∈N we denote a “double blowup” G(tv)(sw) as G(tv,sw). For multiple blowups we extend in the natural way the notation set of double blowups.Note thatG(1v)=G, for all v∈V(G).Lemma 7.
Lett∈N. Let G be a graph with weighted vertices, and let v∈V(G) have weight t. We denote by G(v) the t-blowup of the graph obtained by reducing the weight of v to one. Then, the outcome of playing Grim on G or on G(v) is the same.Proof.
LetI={v1,…,vt} be the independent set used to obtain G(v). There are two possible ways to delete v while playing on G; thus we look at the following two cases.
Case 1 . Try to isolate v in G. Using the same moves needed to remove all of v’s neighbors in G we can isolate every vertex in I (in G(v)).
Case 2 . Remove v in G by repeatedly using it in the game. In order to remove v from G, it has to be selected t times. To fully remove I from G(v), each of the t vertices in I must be selected and removed. Thus removing I from G(v) requires an equivalent process as that needed to remove v from G.
Therefore, game play withv or with I will involve the same strategies. Finally, replacing v with I will not affect the other vertices in the graph, and thus it will not affect playing with them.An easy induction argument proves the main theorem of this section.Theorem 8.
LetG be a weighted graph with V(G)={v1,…,vn} and with ti being the weight of vertex vi, for all i=1,…,n. We denote by G(v1,v2,…,vn) the (t1,t2,…,tn)-blowup of the graph obtained by reducing (if possible) the weight of each vertex of G to one. Then, the outcome of playing Grim on G or on G(v1,…,vn) is the same.We conclude that Grim on weighted graphs does not need to be studied separately, and so from now on the game discussed is always Grim played on unweighted graphs.Before we move on, we would like to let the reader know that we will often use the word graph to mean the game played on that graph (as in “Player 1 wins graphG”). Most proofs in the following sections somehow describe the specific strategy to be used to win.


## 3. Complete and Complete Multipartite Graphs

In this section we obtain specific strategies to win at Grim for complete graphs and complete multipartite graphs. We start with a theorem about complete graphs.Lemma 9.
Letn∈N. Then, Kn is N position if and only if n is even.Proof.
The casen=1 is immediate, as no game is ever played. For n>1, all moves are equivalent in a complete graph, and a move will always yield a complete graph, so the game always lasts n-1 moves.Grim played on complete bipartite graphs will be analyzed next.Theorem 10.
Letm,n∈N. Then, the following hold. (1)
K1,n is an N position.(2)
Assumem,n>1. Then, Km,n is an N position if and only if m+n is odd.Proof.
The first claim is immediate. For the second claim we start by settling a base case.
ForK2,2, whatever move Player 1 makes, the follower is always K1,2. By part 1, Player 2 wins this graph.
Now we proceed by induction onk=m+n. Part 1 and the base case considered above tell us that we have the result for k=3,4. So, assume the result holds for m+n=k≥4. Consider Ka,b, where a+b=k+1.
Case 1 . If k+1 is odd, then k+1≥5. WLOG assume that a>2 and let Player 1 move by creating the follower Ka-1,b. Since both a-1,b>1 we use the induction hypothesis to determine that Player 1 wins Ka,b.
Case 2 . If k+1 is even, then k+1≥6. If WLOG a=2 then Player 1 would not want to move to create the follower K1,b, as this would be won by Player 2. However, if they moved to create the follower K2,b-1 then they would lose anyway, by induction, as 2,b-1>1. Now, if a,b>2 then whatever move Player 1 makes they would lose by induction, as a-1,b-1≥2.In the rest of this section we extend Theorem10 to most multipartite graphs. At this point we would like to remark that the only way to delete a vertex in a complete multipartite graph and, by doing so, isolate other vertices would be when we were making a move on K1,n, which is a graph already studied in Theorem 10. This unique situation indicates that we should take a closer look at graphs that may have K1,n as a follower; K1,1,n is the only one of those graphs that has not been already studied in Theorem 10. Looking at the behavior of K1,n we obtained our next result.Lemma 11.
Letm,n∈N, and G=K1,m,n. Then, (1)
ifm=1, then G is an N position if and only if n is even.(2)
Ifm=2 and n≥2, then G is an N position.(3)
Ifm,n≥2, then G is an N position if and only if m+n is even.Proof.
We start by noticing that the casem=n=1 is immediate. We will prove the case m=1, n>1 by induction on n. Our base cases are K1,1,1 and K1,1,2. We know that the first graph is a P position, and, clearly, Player 1 wins K1,1,2 by leaving the follower K1,1,1 after their first move. For n>2, Player 1 should start by leaving K1,1,n-1 as a follower (otherwise Player 2 would win the game immediately). Player 2 could leave K1,n-1 or K1,1,n-2 as a follower. In the first case, Player 1 wins G, and in the second case induction forces the result we wanted.
Let us assume thatm=2 and n≥2. If n is even then Player 1 leaves K2,n as a follower, which by Theorem 10 is won by Player 1. If n is odd then Player 1 leaves K1,1,n as a follower, and thus they win G by using the strategy discussed above.
Finally, assumem,n≥3. Since none of the players would like to leave K1,2,k as a follower then the winners of these graphs will alternate depending on n being even or odd. Thus we look at the “base case” K1,3,3, which is an N position by Theorem 10, to get the desired result.The complete tripartite graphs “missing” from Lemma11 and most of the other complete multipartite graphs are considered in the following theorem.Theorem 12.
LetG=Kn1,n2,…,nt, where t>2 and ni≥2, for all i=1,…,t. Then, G is a P position if and only if V(G) is even.Proof.
LetG=Kn1,n2,…,nt, where t>2 and ni≥2, for all i=1,…,t. We define S={ni;ni≡1(mod2)}.
Suppose thatV(G) is even and ni≥2, for all i=1,…,t. Note that S is either 0 or even.
Case 1 . Consider S=0; that is, each partition of G contains an even number of vertices. The strategy for Player 2 is as follows: the game starts with Player 1 deleting any vertex from the graph. Since the partition where this vertex was will have at least one more vertex in it, Player 2 deletes a vertex in it. In this way, Player 2 always has an available move in the same partition that Player 1 has chosen to play on. Hence, Player 2 is always the last person to delete a vertex from every partition of G, and thus they will always have the last move in the game, as they will be the only person able to play in the state K1,ni, when that time comes.
Case 2 . Consider |S|=2k, for some nonzero k∈N. Now the strategy for Player 2 is twofold: if Player 1 moves in an “even” partition of G then Player 2 follows the strategy in Case 1, but if Player 1 deletes a vertex in an “odd” partition then Player 2 deletes a vertex in one of the other odd partitions (there would be an odd number of them available). Note that after one move by each player, the follower obtained would be either a graph that Case 1 considers or G that would have S=2(k-1), and thus an induction argument would finish the proof. Note that the base case(s) of this induction could be tracked down to knowing who wins Kodd,odd or Keven,even, which are both P positions by Theorem 10.
Now suppose thatV(G) is odd and ni≥2, for all i=1,…,t. Since there must be some ni∈S, the strategy for Player 1 is to delete any vertex in a partition with an odd number of vertices. In this way, they would leave a follower with an even number of vertices that also has every partition containing more than 1 vertex. For this follower, Player 1 will move second and thus will win the graph.We now look at a specific family of multipartite graphs allowing singletons as partitions.Lemma 13.
LetG=K1,n2,…,nt, where 3<t, 1≤k≤t, and ni≥2, for all i=2,…,t. Then, G is a P position if and only if V(G) is even and ni>2, for all i.Proof.
IfV(G) is odd then Player 1 leaves Kn2,…,nt as a follower, which is a P position (by Theorem 12), and thus Player 1 wins G. Now, if V(G) is even then Player 1 would not want to leave Kn2,…,nt as a follower, as in this case, by Theorem 12, Player 2 would win G. Hence, Player 1 would leave WLOG K1,n2-1,n3,…,nt as a follower. If n2>2 then by the previous case we would get that Player 2 wins G. If we allow r-1>0 of ni to be equal to 2 then, after rearrangement if needed, we get G=K1,2,…,2,nr+1,…,nt, where nr+1,…,nt>2. Note that r<t because V(G) is even. In this case, Player 1 leaves K1,2,…,2,nr+1-1,…,nt as a follower, and thus Player 1 wins G using the strategy discussed for the case V(G) odd.There are several complete multipartite graphs that we have not studied and we will not study in this paper; these, after a rearrangement if needed, have the formK1,…,1,nk+1,…,nt, where 3<t, 1≤k≤t, and ni≥2, for all i=k+1,…,t. Some of them may be studied very easily; for example, K1,…,1 is a P position if and only if t is odd. The conditions needed to understand others are much more complex. For instance, if k>1 and k>αk,t=(nk+1+⋯+nt)-(t-k), then K1,…,1,nk+1,…,nt is a P position if and only if k and αk,t have different parity.On the other hand, in order to understand the casek≤αk,t we need to look at these two parameters and also tohow much bigger than k the quantity αk,t is.Also, unlike most of the graphs studied in this section,K1,n and K1,2,n are always won by Player 1 independent of the parity of n. This situation is not that uncommon in the graphs we have not studied here; for instance, the family of graphs of the form K1,1,3,n, for n≥3, are also won by Player 1 by leaving the follower K1,3,n for n even and K1,1,2,n for n odd. There are several other families, similar to K1,1,3,n, that may be proven to be won by Player 1 only.All of this suggests that a complete theory of how Grim would play on multipartite graphs allowing singletons as partitions is very complex, and thus we plan to study it separately in a future article.Other “standard” families of graphs can be studied in a similar fashion to what has been done in this section with complete and complete multipartite graphs. However, as it was seen in this section and we will see again in Section5, the analysis of Grim gains complexity quickly. Hence, in the following sections we will study Grim on graphs by using a less direct set of techniques.


## 4. Automorphisms

Certain symmetries in a graph can be exploited to obtain strategies for winning at Grim. In this section we prove a couple of results of this type, and then we apply them to a few families of graphs.Definition 14.
A functionσ is said to be anautomorphism of a graph G if σ permutes the vertices of G while preserving incidence. The group (under composition) of all the automorphisms of G is denoted as Aut(G).Theorem 15.
LetG be a graph, and assume that Aut(G) has an element σ of order 2 such that v≠σ(v) and vσ(v)∉E(G), for all v∈V(G). Then, G is a P position.Proof.
Letσ∈Aut(G) be such that v≠σ(v) and vσ(v)∉E(G), for all v∈V(G). We will prove that if Player 1 moves by selecting a vertex v, then Player 2 can always move by selecting σ(v).
We will proceed by contradiction. Suppose that at a certain stage of the game and for the first time, Player 1 moves by selecting a vertexv leaving a follower that does not contain σ(v). If σ(v) was already deleted when Player 1 made their move, then either σ(v) was deleted by Player 2, which would contradict that v had not been deleted at this point, or σ(v) was deleted by becoming isolated, which would force (as σ∈Aut(G)) v to be isolated. In either case, the situation is impossible. So, the only option would be that σ(v) gets isolated at the time of deleting v. But v and σ(v) are not adjacent, so deleting v cannot isolate σ(v).Corollary 16.
LetG be a graph with no isolated vertices, and assume that Aut(G) has an element σ of order 2 such that v0=σ(v0), for exactly one v0∈V(G), and vσ(v)∉E(G), for all v∈V(G). Then, G is an N position.Proof.
Player 1 starts the game by deletingv0, leaving a follower that is a P position by Theorem 15. Hence, G is an N position.The following corollary summarizes a few applications of Theorem15 and Corollary 16.Corollary 17.
Letn∈N. (1)
Ifn is odd and n≥3, then Pn is an N position.(2)
Ifn is even and n≥4, then Cn is a P position.(3)
Ifn is odd and n≥5, then Wn is an N position.(4)
G∪G is a P position, for all nonempty graphs G.Proof.
(1) Use Corollary16 with σ the reflection across the middle vertex of Pn.
(2) ModelCn with a regular n-gon. Use Theorem 15 with σ defined by reflecting every vertex across the center of the polygon.
(3) Use the same function in the proof of (2), but now apply Corollary16, as the center of the wheel is fixed.
(4) Use Theorem15 with σ the identification between the two copies of G.Theorem15 and Corollary 16 can also be used in the study of Cartesian products of graphs.Definition 18.
LetG and H be two disjoint graphs. TheCartesian product of G and H, denoted as G□H, is defined by V(G□H)=V(G)×V(H) and edges given by the following:(1)
(x,y) is adjacent to (w,z) if x=w and y and z are adjacent in H;(2)
(x,y) is adjacent to (w,z) if y=z and x and w are adjacent in G, where x,w∈V(G) and y,z∈V(H).Corollary 19.
Letn>1, G1,…,Gn be graphs and G=G1□⋯□Gn. (1)
IfG1,…,Gn satisfy the hypothesis in Theorem 15, then, G is a P position.(2)
IfG1,…,Gn satisfy the hypothesis in Corollary 16, then G is an N position.Proof.
(1) Letσi∈Aut(Gi) be the automorphism satisfying the hypothesis in Theorem 15. It is easy to see that σ defined by(1)σv1,…,vn=σ1v1,…,σnvnis an automorphism of G also satisfying the hypothesis in Theorem 15. The result follows.
The proof for (2) uses the very same ideas, so we omit it.An attempt to find strategies that allow us to determine who would winG□H, for arbitrary graphs G and H, was made but it failed because we realized that keeping track of all the possible avenues the game could take was an impossible task. A natural approach to how to “keep track” of what happens in a game is discussed in the following section.


## 5. The Sprague-Grundy Function

One of the most useful tools in the study of combinatorial games is the Sprague-Grundy function. We proceed to define it, in the context of Grim, and then we focus our efforts on finding its values for paths.Definition 20.
LetN0=N∪{0} and G be a graph. We define F(G) to be the set of all followers of G (in the game Grim). TheSprague-Grundy function of G is a function SG:V→N0, defined recursively as follows:(2)SGG=min⁡n∈N0;n≠SGH,∀H∈FG.
If we define the minimal excludant or mex of a set of nonnegative integers as the smallest nonnegative integer not in the set, then we may write(3)SGG=mex⁡SGH;H∈FG.Remark 21.
S G ( G ) = 0 if and only if G is a P position.The process to calculate the Sprague-Grundy values by hand is laborious, so we wrote a program in Visual FoxPro to compute the Sprague-Grundy value of Grim on paths. We focused on paths because in Corollary17 we learned that odd paths are N positions, but when wanting to look at even paths no pattern seemed to exist.Using our program, we were able to compute all the values ofSG(Pn) (a library of these values may be obtained at http://www.gamecalledgrim.com) for up to n=107. Using these results we know that if n≤107, then SG(Pn)=0 only when(4)n∈4,12,20,30,46,72,98,124,150,176,314,408,which is something Lącko and Lącki (in unpublished work; see [15]) had also determined (although they consider P1 as P position while we do not consider P1 as graph where we would play Grim, as all isolated vertices in a graph are deleted before a game starts). Moreover, they also claim that SG(Pn)≠0 for all values in the range 107≤n≤108. The obvious question, at this point, is whether or not there are any other even paths with SG(Pn)=0. It turns out that the answer to this question is related to a different open problem in game theory.Definition 22.
AnOctal game is a normal impartial game played on heaps of chips. A move consists of taking a number of chips from a single heap, eliminating them, and then redistributing the remaining chips in the heap (if any left) into 0 (all chips in the heap were eliminated), 1 (leave the remaining chips intact), or 2 heaps; this number is fixed in advance for the game and depends only on how many chips were eliminated in the move. Given that there are several variables to determine at the beginning of the game, the rules of the game are encoded into a string of digits as follows.
If in a move we removek chips from a heap and we are allowed to break the remaining ones into a heaps then we say that χk(a)=1. In the case that we were not allowed to break the remaining ones into a heaps we say that χk(a)=0. The code of the game is d=0.d1d2…, where(5)dk=χk020+χk121+χk222.
It follows that since6=21+22, the gameOctal.6 is a game in which every move consists of one chip being removed from a heap and what remains of that heap must be left in exactly 1 or 2 nonempty heaps.
Several Octal games have Sprague-Grundy sequences that after a while become periodic (see [16], e.g.); it is not known whether Octal.6 has a period. This is relevant to us because the terms in the sequences of Sprague-Grundy numbers for Grim on paths and Octal.6 are the same (see Theorem 23 below). Thus our question about values of n for which SG(Pn)=0 becomes a problem about when Octal.6 is won by Player 2, which is an open problem (e.g., see [17]).
In order to create some intuition on the reader about our next result, we notice that we can identify removing a chip from a heap in Octal.6 with deleting a vertex in a path (under Grim rules). More explicitly, depending on what vertex we delete, we always leave one or two paths left; these two paths would be the equivalent of the two heaps left after removing a chip in Octal.6.Theorem 23.
The Sprague-Grundy sequence of values of Grim played on paths is equivalent to the Sprague-Grundy sequence of values of Octal.6.Proof.
Letn∈N, On be Octal.6 played on a heap of size n and Pn be Grim played on a path on n vertices. We will prove that SG(Pn)=SG(On). We will do this by induction on n.
Forn=1 we get that both games are trivial and thus SG(P1)=SG(O1)=0. We now assume that SG(Pi)=SG(Oi), for all i≤n.
First we notice that the followers ofPn+1 and On+1 are (6)FPn+1=Pn,Pn-1∪P1,Pn-2∪P2,…FOn+1=On,On-1∪O1,On-2∪O2,….
Using Nim Sum (see [2]), denoted as +N below, to evaluate the Sprague-Grundy number of the followers of Pn+1 and On+1, we get(7)SGPn+1=mexSGPn,SGPn-1+NSGP1,SGPn-2+NSGP2,…SGOn+1=mexSGOn,SGOn-1+NSGO1,SGOn-2+NSGO2,….
Using the inductive hypothesis and Nim Sum we get that(8)SGPn=SGOnSGPn-1+NSGP1=SGOn-1+NSGO1⋮
Hence,SG(Pn+1)=SG(On+1).If we knew all the values in the sequence{SG(Pn)}n=1∞ we would also know several other Sprague-Grundy sequences. We present two results of this type, without a proof, in the following corollaries.Corollary 24.
The Sprague-Grundy sequence for Grim on cycles is given by(9)SGCn=1ifSGPn-1=00otherwise.In particular, Cn is a P position when n is even.Finally, we get a result about wheels that depends on whatever knowledge we had about paths.Definition 25.
Awheel graph on n vertices is defined by Wn=Cn-1+K1. K1 is called the center of the wheel.Corollary 26.
Letn≥4; then Wn is an N position if and only if Pn-2 is an N position.Proof.
W n has only two followers: Cn-1, obtained from deleting the center of the wheel and Wn-1′, obtained by deleting a vertex different from the center of Wn.
If Player 1 winsPn, then they can win Wn+2 by removing the center vertex and leaving Cn+1 as a follower; this then forces Player 2 to leave Pn as a follower, which is an N position.
If Player 2 winsPn, then since Wn+2 has only two followers and both of them are one deleted vertex away from Pn, Player 2 can leave Pn as a follower after their first move.


## 6. Grim on Random Graphs

We are interested in understanding what happens when Grim is played on a random graph. Our main reason is that evidence in previous sections has shown that the game seems to favor Player 1 overall. In order to do this, we will use Erdős-Rényi random graphs.Definition 27.
Letn∈N and 0≤p≤1. AnErdős-Rényi random graphG(n,p) is defined by having n vertices and, for any pair of vertices, the existence of an edge connecting them has probability p.
In this section, we will work on identifying probabilitiesp for which Player 1 and Player 2 have equal chances of winning a random graph G(n,p).Remark 28.
The probability ofany given graph on n vertices and k edges to exist is given by pk(1-p)n2-k. So, if p=0.5, then all possible graphs on n vertices have equal probability to exist, this value being (1/2)n2.Definition 29.
Thewinning probability of Player 1, denoted as W1(p), is a function that describes the probability for Player 1 to win on a random graph, for a fixed n and a given edge probability p. It is of the form(10)W1p=∑GXGPG, where the sum runs through all graphs (including the empty graph, which is a P position), P(G)=pk(1-p)n2-k for a graph on k edges, and(11)XG=1ifSGG≠00ifSGG=0.Thewinning probability of Player 2, denoted by W2(p), may be defined similarly.As an illustration, let us consider Erdős-Rényi random graphs onn=3 vertices with edges generated with probability p. We know that there are eight 3-vertex graphs. Out of these eight graphs, Player 1 would win all the three graphs with one edge and all the three graphs with 2 edges and lose the one complete graph and the empty graph. Hence, the winning probabilities are(12)W1p=3p1-p2+3p21-pW2p=1-p3+p3.Note that settingW1(p)=W2(p) yields the quadratic equation 6p2-6p+1=0, which has solutions(13)p=3±36;they are approximately 0.21 and 0.79.Thus, Player 1 and Player 2 have an equal chance of winning on a 3-vertex graph if the chance of each edge appearing is about21% or 79%. Moreover, looking at the graph of W1(p)-W2(p) we get that Player 2 has more than a 50% chance of winning as long as(14)p<3-36or3+36<p.On the other hand, if we now consider Erdős-Rényi random graphs onn=4 vertices, we get that the winning probability for Player 2 is(15)W2p=3p21-p4+16p31-p3+1-p5,which is equal to 0.5 for p~0.16 and always below 0.5 after.Our examples suggest the following theorem.Theorem 30.
Letn be odd. For Erdős-Rényi random graph G(n,p), there exists 0<p0<1 such that W2(p)≥0.5, for all p≥p0.Proof.
We will get a lower bound forW2(p) and use it to derive the existence of p0. Note that, by Remark 28, we get(16)W2p≥pn2.
We set this bound equal to 0.5 and solve forp. We get the solution(17)p0=141/n2-n, which is in (0,1), for every n.
Sincep0<p implies 0.5=p0n2<pn2, we get that W2(p)≥0.5, for all p≥p0.Notice that as the number of vertices gets large, the bound for the value ofp0 given in the proof of Theorem 30 approaches 1 and thus, overall, Player 1 has increasingly better chances to win. It would be good to find an explicit expression for the least possible p0, but this seems to be a really hard problem, as we do not know which graphs are P positions.



---

*Source: 1476359-2016-08-29.xml*