The Largest Connected Subgraph Game

Abstract

This paper introduces the largest connected subgraph game played on an undirected graph G. In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than the order of any blue (red, resp.) connected subgraph. We first prove that, if Alice plays optimally, then Bob can never win, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give an algorithm to determine the outcome of the game in cographs in linear time.

1 Introduction

Games in which players strive to create connected structures are connection games. Several of these games are well-known, such as the game of Hex, introduced by Hein in 1942, and independently by Nash in 1948 [10]. The game of Hex is played by two players on a rhombus-shaped board tiled by hexagons, with two of the opposing sides of the board coloured red and the other two coloured blue. In each round, the first player colours an uncoloured hexagonal tile red, and then, the second player colours one blue. The first (second, resp.) player wins if they manage to connect the red (blue, resp.) sides of the board with red (blue, resp.) tiles. Another well-known connection game is the Shannon switching game, invented by Shannon in the 1950s [11]. In this game, the first player has the goal of connecting two marked vertices in a graph, while the second player wants to make sure this never happens. Traditionally, the players take turns selecting edges of the graph, with the first player winning if there is a path consisting of only the first player’s edges between the two marked vertices, but a variant where the players select vertices (and obtain all their incident edges) also exists. However, not all connection games involve connecting sides of a board or two vertices in a graph. Havannah, a board game invented by Freeling that was released in 1981, is one such game, where the players may also win by forming closed loops, with the playing board and the rules being similar to Hex. Connection games tend to be very difficult complexity-wise (a main reason they are played and studied), with the majority of them being PSPACE-complete. For example, Reisch proved that generalised Hex¹ is PSPACE-complete [16], Even and Tarjan proved that the Shannon switching game on vertices (when players select vertices instead of edges) is PSPACE-complete [9], and Bonnet, Jamain, and Saffidine proved that (generalised) Havannah is PSPACE-complete [3]. That being said, Bruno and Weinberg proved that the Shannon switching game on edges is polynomial-time solvable [5]. For more on the complexity of other connection games, see [3]. For more on connection games in general, see [4] for a book by Browne on such games.

Games in which the player with the largest score wins, are called scoring games. The score in these games is an abstract quantity usually measured in an abstract unit called points. Players may gain points in a myriad of ways, all depending on the rules of the game. For example, in the orthogonal colouring game on graphs introduced recently by Andres, Huggan, Mc Inerney, and Nowakowski [1], a player’s score is equal to the number of coloured vertices in their copy of the graph at the end of the game, i.e., each player gets one point for each coloured vertex in their copy of the graph. Recently, the papers by Larsson, Nowakowski, Neto, and Santos [12] and Larsson, Nowakowski, and Santos [13, 14] have started to build a general theory around scoring games. There have also been a number of papers on different scoring games of late, such as those authored by Changat, Lekha, Peterin, Subhamathi, and Spacapan [6], Duchêne, Gonzalez, Parreau, Rémila, and Solal [8], Micek and Walczak [15], and Shapovalov [18].

In this paper, we introduce the following 2-player connection and scoring game on graphs, which, surprisingly, has not yet been studied even though it is a very natural game. For any graph G, the largest connected subgraph game is played (on G) between the first player, Alice, and the second player, Bob. Initially, none of the vertices are coloured. Then, in each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue. Note that each vertex can only be coloured once and, once coloured, its colour cannot be modified. The game ends when all of the vertices of G have been coloured. If there is a connected red subgraph such that its order (number of vertices) is strictly greater than the order of any connected blue subgraph, then Alice wins. If there is a connected blue subgraph such that its order is strictly greater than the order of any connected red subgraph, then Bob wins. Otherwise, the order of the largest connected red subgraph is the same as the order of the largest connected blue subgraph, and, in this case, the game is a draw.

We begin by defining notations and proving some preliminary results for the largest connected subgraph game in Sect. 2, i.e., showing that Bob can never win (if Alice plays optimally), that the game is a draw in a large class of graphs that we call reflection graphs, and that recognising reflection graphs is GI-hard. Then, in Sect. 3, we prove that the game is PSPACE-complete, even in bipartite graphs of small diameter. After that, we study the game in particular graph classes, with Sect. 4 comprising the resolution of the game for paths and cycles, and Sect. 5 consisting of a linear-time algorithm for solving the game in cographs. An interesting point behind these graph classes is that they illustrate different types of playing strategies that Alice and Bob can employ. Lastly, we finish with some open questions in Sect. 6.

2 Notations and First Results

In this section, we define notations and give preliminary results for the game. For any graph G, if Alice (Bob, resp.) has a winning strategy in the largest connected subgraph game, then G is A-win (B-win, resp.). If neither Alice nor Bob has a winning strategy in the largest connected subgraph game on G, i.e., the game is a draw if both players follow optimal strategies, then G is AB-draw.

A first thing to note about this game is that it can never harm a player to have an extra turn, in the sense that an extra turn can never decrease their potential score, i.e., it can never decrease the potential order of the largest connected monochromatic subgraph they can build. This is due to the fact that colouring a vertex only impedes that vertex from being coloured in the future, but does not impede any other vertex from being coloured. This implies the following theorem.

Theorem 2.1

There does not exist a graph G that is B-win.

Proof

Towards a contradiction, assume there exists a graph G that is B-win. Consider the following strategy for Alice. In the first round, Alice colours any arbitrary vertex $v\in V(G)$. Now, one vertex is coloured and it can be assumed that Bob is the first player. Alice now plays according to the second player’s winning strategy in G. If, by this strategy, Alice is ever required to colour an already-coloured vertex, then that vertex must be red, and again, in this case, Alice colours any arbitrary uncoloured vertex. Since the only reason a vertex cannot be coloured is that it is already coloured, Alice can always follow this strategy, which is a winning strategy, a contradiction. $\square$

Now that we know that there are no B-win graphs, the next natural question to ask is whether there exist graphs that are A-win (AB-draw, resp.). It is easy to see that there are an infinite number of A-win graphs as any star (of order not equal to 2) is A-win, since, in order to win, it is sufficient for Alice to colour the universal vertex in the first round. This also illustrates that there are an infinite number of A-win graphs for which, through optimal strategies, the order of the largest connected red subgraph is arbitrarily bigger than the order of the largest connected blue subgraph. There are also an infinite number of AB-draw graphs, since any graph of even order with two universal vertices is clearly AB-draw (as, to ensure at least a draw, it is sufficient for Bob to colour a universal vertex in the first round). By adding an isolated vertex to any of the graphs mentioned in the previous sentence, we also have that there are an infinite number of AB-draw graphs of odd order. In Sect. 4, we will see that any path of order at least 11 is AB-draw, and hence, that there exists an infinite family of connected graphs of odd order that are AB-draw.

We can actually define a much richer class of graphs that are AB-draw. A reflection graph is any graph G, whose vertices can be partitioned into two sets $U=\{u_1,\ldots ,u_n\}$ and $V=\{v_1,\ldots ,v_n\}$ such that:

• 1. the subgraph G[U] induced by the vertices of U is isomorphic to the subgraph G[V] induced by the vertices of V, and the function mapping $u_i$ to $v_i$ for all $1\le i\le n$, is an isomorphism between G[U] and G[V];

• 2. for any two vertices $u_i\in U$ and $v_j\in V$, if the edge $u_iv_j$ exists, then the edge $u_jv_i$ exists (where, for any $1 \le \ell \le n$, $v_{\ell }\in V$ is the image of $u_{\ell }\in U$ by the said isomorphism).

In other words, if a graph G can be formed by taking two copies of a graph H, and adding edges between both copies of H according to the second condition above, then G is a reflection graph. It is easy to see, for example, that paths and cycles of even order, and some grids of even order, are reflection graphs.

Proposition 2.2

Paths, cycles, Cartesian grids, and king grids of even order are reflection graphs.

Proof

Note that a path of even order 2n ($n \ge 1$) can be regarded as the disjoint union of two paths $(u_1, \dots , u_n)$ and $(v_1, \dots , v_n)$ of order n, connected by the edge $u_1v_1$. Similarly, a cycle of even length 2n ($n \ge 2$) can be regarded as the disjoint union of two paths $(u_1, \dots , u_n)$ and $(v_1, \dots , v_n)$ of order n, joined by the edges $u_1v_1$ and $u_nv_n$. Thus, paths and cycles of even order are reflection graphs. Now, for a Cartesian grid H to be of even order, at least one of its two dimensions must be even. Assume, w.l.o.g., that its number of columns 2n ($n \ge 1$) is even, while its number of rows is $m \ge 1$. Then, H can be regarded as the disjoint union of two Cartesian grids $G_1$ and $G_2$ with m rows and n columns each, being joined by the edges $u_1v_1,\dots ,u_mv_m$ if we denote by $u_1,\dots ,u_m$ the consecutive vertices of the last column of $G_1$, and by $v_1,\dots ,v_m$ the consecutive vertices of the first column of $G_2$. King grids of even order can similarly be described that way (note that we also have both edges $u_iv_{i+1}$ and $u_{i+1}v_i$ for every $i \in \{1,\dots ,m-1\}$). Thus, Cartesian grids and king grids of even order are reflection graphs. $\square$

The next theorem proves that reflection graphs are AB-draw.

Theorem 2.3

Any reflection graph G is AB-draw.

Proof

We define a “copying” strategy for Bob which guarantees a draw. Let $U=\{u_1,\dots ,u_n\}$ and $V=\{v_1,\dots ,v_n\}$ be a partitioning of the vertices of G that satisfies the two conditions required for G to be a reflection graph. Bob’s copying strategy is as follows. In every round, when Alice colours a vertex $u_i\in U$ ($v_i\in V$, resp.), Bob colours its image $v_i\in V$ ($u_i\in U$, resp.). By Bob’s strategy, it is easy to see that Bob can always play in this way. Moreover, by the symmetry of the graph, for every vertex coloured red (blue, resp.) in U, its image is coloured blue (red, resp.) in V. Hence, once all vertices are coloured, by the symmetry of the graph and the second condition for reflection graphs concerning the edges between vertices of U and V, there is a blue isomorphic copy of any connected red subgraph in G. Thus, the game ends in a draw. $\square$

It turns out that recognising reflection graphs is not an easy problem. We show that it is GI-hard, essentially showing that it is unlikely to be polynomial-time solvable as there exist problems in GI (notably the Graph Isomorphism problem) which are good candidates for being NP-intermediate, i.e., in the class NPI, which is the complexity class of problems that are in NP but that are neither NP-hard nor in P. Note that the class NPI is non-empty if and only if P $\ne$ NP.

Theorem 2.4

Given a graph G, deciding if G is a reflection graph is GI-hard.

Proof

The reduction is from the Graph Isomorphism problem, in which, given two input graphs $G_1$ and $G_2$, one has to decide whether $G_1$ and $G_2$ are isomorphic. We may further assume that $G_1$ and $G_2$ are each connected and of odd order, which is one of the input restrictions for which the problem remains hard. Indeed, note that we obtain an equivalent instance of the problem (with the desired properties), upon adding, if needed, one or two universal vertices to both $G_1$ and $G_2$.

We construct a graph H in polynomial time, such that $G_1$ and $G_2$ are isomorphic if and only if H is a reflection graph. The graph H we construct is simply $G_1+G_2$, the disjoint union of $G_1$ and $G_2$. Let us prove the two directions of the equivalence.

First, we prove the forward direction. Assume that the vertices of $G_1$ and $G_2$ are $u_1,\dots ,u_n$ and $v_1,\dots ,v_n$, respectively, ordered in such a way that there is an isomorphism between $G_1$ and $G_2$ where $v_i$ is the image of $u_i$, for all $1 \le i \le n$. Note that no edge joins a vertex from $G_1$ and a vertex from $G_2$. Then, $G_1\cup G_2=H$ is a reflection graph with $U=V(G_1)$ and $V=V(G_2)$. The reflection property is trivial in that case.

Now, we prove the other direction. Assume that H is a reflection graph with parts $U=\{u_1,\dots ,u_n\}$ and $V=\{v_1,\dots ,v_n\}$ such that the function mapping $u_i$ to $v_i$ (for all $1 \le i \le n$) is an isomorphism between H[U] and H[V]. If U is precisely $V(G_1)$ while V is precisely $V(G_2)$, then we get that $H[U]=G_1$ and $H[V]=G_2$ are isomorphic, by the definition of a reflection graph. So, assume this is not the case.

For all $1 \le i \le n$, note that either

• (1) $u_i \in V(G_1)$ and $v_i \in V(G_2)$,

• (2) $u_i \in V(G_2)$ and $v_i \in V(G_1)$,

• (3) $u_i,v_i \in V(G_1)$, or

• (4) $u_i,v_i \in V(G_2)$.

We consider all i’s in turn, and possibly switch vertices of U and V as follows:

• If $u_i$ and $v_i$ satisfy Condition 1) above, then we do nothing.

• If $u_i$ and $v_i$ satisfy Condition 2) above, then we move $u_i$ from U to V, and, conversely, move $v_i$ from V to U, resulting in a partition of V(H) into two equally sized parts $U'$ and $V'$. Note that, considering the ordering $u_1',\dots ,u_n'$ and $v_1',\dots ,v_n'$ of $U'$ and $V'$ (where $u_j'=u_j$ and $v_j'=v_j$ for all $1\le j\le n$ such that $i\ne j$, and $u_i'=v_i$ and $v_i'=u_i$), respectively, we have that H is also a reflection graph with respect to the two parts $U'$ and $V'$. Indeed, by the isomorphism and reflection properties, we have that $u_i$ was neighbouring $u_{i_1},\dots ,u_{i_k}$ in U (and so, $v_i$ was neighbouring $v_{i_1},\dots ,v_{i_k}$ in V) and $v_{j_1},\dots ,v_{j_k}$ in V (and so, $v_i$ was neighbouring $u_{j_1},\dots ,u_{j_k}$ in U), which translates, for $U'$ and $V'$, into $u_i'$ neighbouring $v_{j_1},\dots ,v_{j_k}$ in $V'$ (and so, $v_i'$ neighbouring $u_{j_1},\dots ,u_{j_k}$ in $U'$) and $u_{i_1},\dots ,u_{i_k}$ in $U'$ (and so, $v_i'$ neighbouring $v_{i_1},\dots ,v_{i_k}$ in $V'$).

• If $u_i$ and $v_i$ satisfy Condition 3) or 4) above, then we get a contradiction to one of the original assumptions on $G_1$ and $G_2$. Indeed, assume, w.l.o.g., that $u_i$ and $v_i$ satisfy Condition 3), i.e., both $u_i$ and $v_i$ originate from $G_1$. Note that, because $G_1$ and $G_2$ are each connected and of odd order, there must be a pair $u_j,v_j$ such that, w.l.o.g., $u_j \in V(G_1)$ and $v_j \in V(G_2)$. Furthermore, since $G_1$ is connected, for such a pair $u_j,v_j$, it can be assumed, w.l.o.g., that at least one of $u_iu_j$ and $v_iu_j$ is an edge. If the former edge exists, then the contradiction arises from the fact that, since H is a reflection graph, we must have the edge $v_iv_j$ as well, which is not possible since $v_i \in V(G_1)$ and $v_j \in V(G_2)$. If the latter edge exists, then, because H is a reflection graph, the edge $u_iv_j$ also exists, hence, an edge between $G_1$ and $G_2$, which again is a contradiction.

Once all i’s have been treated this way, H remains a reflection graph, and a direct isomorphism between $G_1$ and $G_2$ is deduced. $\square$

3 Complexity

In this section, we show that the largest connected subgraph game is PSPACE-complete, even when restricted to bipartite graphs of small diameter. Our reduction is via POS CNF, which was shown to be PSPACE-complete in [17], and is as follows:

Definition 3.1

(POS CNF) A 2-player game, where the input consists of a set of variables $X=\{x_1,\ldots ,x_n\}$ and a conjunctive normal form (CNF) formula $\phi$ consisting of clauses $C_1,\ldots ,C_m$ that each contain only variables from X, all of which appear in their positive form (hence, the term POS). In each round, the first player, Alice, first sets a variable (that is not yet set) to true, and then, the second player, Bob, sets a variable (that is not yet set) to false. Once all the variables have been assigned a truth value, Alice wins if $\phi$ is true, and Bob wins if $\phi$ is false.

Fig. 1

An example of the construction of the graph G in the proof of Theorem 3.2, where, among other variables, the clause $C_1$ contains the variable $x_1$, the clause $C_2$ contains the variables $x_1$ and $x_2$, and the clause $C_m$ contains the variables $x_2$ and $x_n$

Theorem 3.2

Given a graph G, deciding if G is A-win is PSPACE-complete, even if G is bipartite and has a diameter of 5.

Proof

Since the number of rounds is exactly $\lceil |V(G)|/2\rceil$ and there are at most |V(G)| possible moves for a player in any round, the decision problem is in PSPACE. To prove the problem is PSPACE-hard, we give a reduction from POS CNF. By adding a dummy variable (if necessary), it is easy to see that POS CNF remains PSPACE-hard even if the number of variables n is odd. From an instance $\phi$ of POS CNF where n is odd, we construct, in polynomial time, an instance G of the largest connected subgraph game such that Alice wins in $\phi$ if and only if G is A-win. Let $x_1,\ldots ,x_n$ be the variables and let $C_1,\ldots ,C_m$ be the clauses of $\phi$. The construction of G is as follows (see Fig. 1 for an illustration): for each variable $x_i$ ($1\le i\le n$), there is a vertex $x_i$, and, for each clause $C_j$ ($1\le j\le m$), there are 6 vertices $C^1_j,\ldots ,C^6_j$. For all $1\le i\le n$ and $1\le j\le m$, if the variable $x_i$ appears in the clause $C_j$, then there is the edge $x_iC^q_j$ for all $1\le q\le 6$. In addition to this, there are the vertices u, $v_1$, $v_2$, $w_1$, $w_2$, and $y_1,\ldots ,y_{n+6m-2}$, and the edges $w_1v_1$, $v_1u$, $uv_2$, and $v_2w_2$. Furthermore, for all $1\le i\le n$, there is the edge $ux_i$, and, for all $1\le \ell \le n+6m-2$, there are the edges $w_1y_{\ell }$ and $w_2y_{\ell }$. This completes the construction. To simplify the proof, let P be the subgraph of G induced by the vertices $x_i$ ($1\le i\le n$) and $C^q_j$ ($1\le q\le 6$ and $1\le j\le m$), and let Q be the subgraph of G induced by the vertices in $V(G)\setminus (V(P)\cup \{u\})$. Note that u separates P from Q. To simplify the upcoming calculations, let $b= (n-1)/2+3m+1 = \lfloor n/2 \rfloor +3m+1$ since n is odd.

We start by proving the first direction, that is, if Alice wins in $\phi$, then G is A-win. We describe a winning strategy for Alice. In what follows, whenever Alice cannot follow her strategy, she simply colours any arbitrary vertex and resumes her strategy for the subsequent moves of Bob. Alice first colours u. Now, Bob can only construct connected blue subgraphs in P or Q since u separates them. For all $1\le j\le m$, whenever Bob colours a vertex in $\{C^1_j,\ldots ,C^6_j\}$, then Alice also colours a vertex in $\{C^1_j,\ldots ,C^6_j\}$, so in what follows, we may assume that Bob does not colour such a vertex. There are two cases depending on Bob’s next move.

• Bob colours a vertex in Q. Then, Alice colours the vertex $x_i$ that corresponds to the variable $x_i$ she wants to set to true in her winning strategy in $\phi$. Now, whenever Bob colours a vertex $x_p$ ($1\le p\le n$ and $p\ne i$), Alice assumes Bob set the variable $x_p$ to false in $\phi$ and colours the vertex in $\{x_1,\ldots ,x_n\}$ corresponding to her winning strategy in $\phi$. Otherwise, whenever Bob colours a vertex in Q, then Alice colours a vertex in Q. Note that, by this strategy, Alice ensures a connected red subgraph of order at least $\lceil n/2\rceil +3m+1=b+1$ since she colours half the variable vertices (rounded up since Alice starts in these vertices), half the clause vertices, and u, and since she followed a winning strategy in $\phi$, this subgraph is indeed connected. Furthermore, she ensures that any connected blue subgraph in P is of order at most $\lfloor n/2\rfloor +3m=b-1$, and hence, Bob must construct his largest connected blue subgraph in Q if he wants to manage a draw.

  If Alice colours $v_1$ or $v_2$ she wins, since then she ensures a connected red subgraph of order at least $\lceil n/2\rceil +3m+2=b+2$, while she ensures that any connected blue subgraph in Q is of order at most $b+1$. Indeed, $|V(Q)|=n+6m+2$, Bob first colours one vertex in Q, and then each subsequent time he colours a vertex in Q, Alice does the same, and thus, Bob colours at most $1+ \lceil (n+6m+1)/2 \rceil = 1+ (n+1)/2+3m=b+1$ vertices in Q.

  Thus, Bob must have coloured $v_1$ and $v_2$ in the first two rounds. Now, Alice colours $w_2$ (so that $v_2$ cannot be part of a large connected blue subgraph since u is red), and she wins since she ensures that any connected blue subgraph in Q is of order at most $\lceil (|V(Q)|-3)/2 \rceil +1 = \lceil (n+6m-1)/2 \rceil +1 =b$ (recall that n is odd).

• Bob colours a vertex in $\{x_1,\ldots ,x_n\}$. Then, Alice colours $w_2$.

  First, let us assume that Bob does not colour $v_2$ during his second turn,. Then, Alice will colour $v_2$ in the next round and win with the following strategy: whenever Bob colours a vertex

  • in $\{w_1,v_1\}$, then Alice colours the other vertex in $\{w_1,v_1\}$;

  • $y_{\ell }$ ($1\le \ell \le n+6m-2$), then Alice colours a vertex $y_k$ ($1\le k\le n+6m-2$ and $\ell \ne k$);

  • $x_i$ ($1\le i\le n$), then Alice colours a vertex $x_p$ ($1\le p\le n$ and $i\ne p$).

  In this way, Alice has coloured $u,v_2$, and $w_2$. Moreover, she coloured at least half (rounded down) of the $n+6m-2+n-2$ vertices $y_{\ell }$ and $x_i$ that remained uncoloured after Bob’s second turn (at most two vertices $y_{\ell }$ and $x_i$ could have been coloured blue during Bob’s first two turns, and the half is rounded down since Alice plays in second in this set of vertices). In total, this guarantees a connected red subgraph of order at least $3+\lfloor (n+6m-2+n-2)/2\rfloor =n+3m+1>b+1$ without counting any of the vertices $C^q_j$ ($1\le q\le 6$, $1\le j\le m$). Regarding Bob, any connected blue subgraph in P has order at most $2+\lceil (|V(P)|-2)/2 \rceil$ (since, except for the first two turns of Bob, Alice always answers in P when Bob colours a vertex in P), i.e., at most

  $$\begin{aligned}&2+\lceil (n+6m-2)/2 \rceil = 2 + \lceil n/2 \rceil + 3m -1 = 1+(n+1)/2+3m = (n-1)/2+3m+2=b+1 .\end{aligned}$$

  Moreover, any connected blue subgraph in Q has order at most $\lceil (|V(Q)|-3)/2 \rceil +1=\lceil (n+6m-1)/2\rceil +1=(n-1)/2+3m+1=b$. Hence, Alice wins in this case.

  Second, let us assume that Bob colours $v_2$ during his second turn. Now, Alice colours $w_1$ and Bob is forced to colour $v_1$ for the same reasons as above. Alice now colours $y_1$ and then she follows the strategy just previously described above (the one for the case where Bob did not colour $v_2$). In this way, Alice ensures a connected red subgraph containing $w_2,w_1$, and half of the vertices $y_{\ell }$ (rounded up), i.e., a connected red subgraph of order at least $\lceil (n+6m-2)/2\rceil +2=\lceil n/2\rceil +3m+1=b+1$ in Q. Regarding Bob, any connected blue subgraph in P has at most $\lceil (|V(P)|-1)/2 \rceil +1$ vertices (the first vertex that Bob coloured, plus half of the remaining vertices in P), i.e., at most $\lceil (n+6m-1)/2 \rceil +1 = (n-1)/2+3m+1=b$ vertices, and any connected blue subgraph in Q has at most one vertex. Hence, Alice wins in this case as well, and this concludes the proof of the first direction.

Now, we prove the other direction, that is, if Bob wins in $\phi$, then G is AB-draw. We give a strategy for Bob that guarantees the game in G is a draw. In what follows, whenever Bob cannot follow his strategy, he simply colours any arbitrary vertex and resumes his strategy for the subsequent moves of Alice. Part of Bob’s strategy is as follows: whenever Alice colours

• a vertex in $\{C^1_j,\ldots ,C^6_j\}$ for some $1\le j\le m$, then Bob also colours a vertex in $\{C^1_j,\ldots ,C^6_j\}$;

• a vertex $x_i$ for some $1\le i\le n$, then Bob assumes Alice set the variable $x_i$ to true in $\phi$ and colours the vertex in $\{x_1,\ldots ,x_n\}$ corresponding to his winning strategy in $\phi$.

Hence, we just need to describe a strategy for Bob in $Q'$, the subgraph of G induced by the vertices in $V(Q)\cup \{u\}$. W.l.o.g., we may assume that the first vertex Alice colours in $Q'$ is neither $v_2$ nor $w_2$. Then, Bob colours $w_2$. Now, if the first two vertices Alice colours in $Q'$ are:

• $w_1$ and $v_1$, then Bob colours u. Now, Alice must colour $v_2$, as otherwise, Bob wins as in the proof of the first direction where Alice wins if she manages to colour $w_2$, $v_2$, and u. Then, Bob colours $y_k$ for some $1\le k\le n+6m-2$. Now, whenever Alice colours a vertex $y_{\ell }$ ($1\le \ell \le n+6m-2$), then Bob colours a vertex $y_k$ ($1\le k\le n+6m-2$ and $\ell \ne k$);

• $w_1$ and $v_2$, then Bob colours $y_{\ell }$ for some $1\le \ell \le n+6m-2$. Now, whenever Alice colours a vertex in $\{v_1,u\}$, then Bob colours the other vertex in $\{v_1,u\}$. Otherwise, whenever Alice colours a vertex $y_{\ell }$ ($1\le \ell \le n+6m-2$), then Bob colours a vertex $y_k$ ($1\le k\le n+6m-2$ and $\ell \ne k$);

• $w_1$ and u, then Bob colours $v_1$. Now, whenever Alice colours a vertex in $\{y_1,\ldots ,y_{n+6m-2},v_2\}$, then Bob colours another vertex in $\{y_1,\ldots ,y_{n+6m-2},v_2\}$;

• $w_1$ and $y_k$ for some $1\le k\le n+6m-2$, then Bob colours $v_2$. Now, Alice must colour u, as otherwise, Bob wins as in the proof of the first direction where Alice wins if she manages to colour $w_2$, $v_2$, and u. Then, Bob colours $v_1$. Now, whenever Alice colours a vertex $y_{\ell }$ ($1\le \ell \le n+6m-2$), then Bob colours a vertex $y_p$ ($1\le p\le n+6m-2$ and $\ell \ne p$);

• any other combination, then Bob colours $w_1$. Now, whenever Alice colours a vertex in $\{y_1,\ldots ,y_{n+6m-2},v_1,v_2,u\}$, then Bob colours a different vertex in $\{y_1,\ldots ,y_{n+6m-2},v_1,v_2\}$ (note that u is not included here).

In the first two cases above, there is a connected blue component in Q (consisting of $w_2$ and half of the vertices $y_{\ell }$, rounded up since Bob starts in these vertices) of order at least $\lceil (n+6m-2)/2\rceil +1=(n-1)/2 +3m+1=b$. In the third case above, there is a connected blue component in Q of order at least $\lfloor (n+6m-2+1)/2\rfloor +1= (n-1)/2 +3m+1=b$ (consisting of $w_2$ and half of the vertices $y_{\ell }$ and $v_2$, rounded down since Alice starts in these vertices). In the fourth case above, there is a connected blue component in Q of order at least $\lfloor (n+6m-3)/2\rfloor +2=(n-1)/2 +3m+1=b$ (the two vertices $w_2$ and $v_2$, plus half, rounded down, of the vertices $y_{\ell }$ minus the first one coloured by Alice). In the last case above, there is a connected blue component in Q of order at least $\lfloor (n+6m-2)/2\rfloor +2=\lfloor n/2\rfloor +3m+1=(n-1)/2 +3m+1=b$ (indeed, if $\alpha ,\beta$ are the first two vertices in $Q'$ coloured by Alice, then Bob colours at least $w_1,w_2$, and half of the vertices in $\{y_1,\ldots ,y_{n+6m-2},v_1,v_2\} \setminus \{\alpha ,\beta \}$ rounded down). To summarise, in each of the cases, Bob has ensured that there is a connected blue component in Q of order at least b.

Regarding Alice, in the first two cases above, any connected red component in Q is of order at most $\lfloor (n+6m-2)/2\rfloor +2= (n-1)/2 +3m+1=b$ (consisting of at most $w_1,v_1$, and half of the vertices $y_{\ell }$ rounded down). In the third case above, any connected red component in Q is of order at most $\lceil (n+6m-2)/2\rceil +1=\lceil n/2\rceil +3m= (n-1)/2 +3m+1=b$ (consisting of at most $w_1$ and half of the vertices $y_{\ell }$ rounded up). In the fourth case above, any connected red component in Q is of order at most $\lceil (n+6m-3)/2\rceil +2= (n-1)/2 +3m+1=b$ (consisting of at most $w_1$, one vertex $y_k$, and half of the remaining $n+6m-3$ vertices $y_{\ell }$ rounded up). In the last case above, any connected red component in Q is of order at most 1. To summarise, in each of the cases, Bob has ensured that any connected red component in Q is of order at most b. Hence, if Alice is to win, she must have constructed a connected red component of order at least $b+1$ in $P'$, the subgraph of G induced by $V(P)\cup \{u,v_1,v_2\}$ (since, by Bob’s strategy, it can never be that u, $v_1$, and $w_1$ (u, $v_2$, and $w_2$, resp.) are all red). Since Bob follows a winning strategy in $\phi$ whenever Alice colours a vertex in $\{x_1,\ldots ,x_n\}$, there is at least one j ($1\le j\le m$) for which none of the vertices in $C^1_j,\ldots ,C^6_j$ are adjacent to a red vertex. Hence, any connected red component in $P'$ is of order at most $\lceil (n+6m-6)/2\rceil +3=\lceil n/2\rceil +3m=(n-1)/2 +3m+1=b$. Thus, in G, there is a connected blue component of order at least b and any connected red component is of order at most b. Hence, Alice does not win in any of the cases and this concludes the proof of the second direction. $\square$

4 Paths and Cycles

In this section, we deal with the case of n-vertex paths $P_n=(v_1,\ldots ,v_n)$ and n-vertex cycles $C_n=(v_1,\ldots ,v_n)$. Recall that every path and cycle of even order is a reflection graph by Proposition 2.2, and thus, is AB-draw by Theorem 2.3. Here, we finish the case of paths and cycles by dealing with the case of paths and cycles of odd order.

We begin with two technical lemmas for specific cases in paths, which will be used in the proofs for paths and cycles of odd order. In the following proofs in this section, we often divide the main path $P_n$ into two subpaths Q and $Q'$, and say that Alice “follows” Bob, that is, when Bob plays in Q (in $Q'$, resp.), Alice then plays in the same subpath Q (in $Q'$, resp.). The precise way Alice answers to Bob’s moves in Q (in $Q'$, resp.) is described in the proofs and depends on the different cases. Note that, when following this strategy, Alice may be unable to colour a desired vertex (either because Q, resp., $Q'$, has no uncoloured vertex anymore, or because the desired vertex is already coloured red). In such a case, Alice colours any arbitrary uncoloured vertex of the main path. The same applies for when we say that Bob “follows” Alice. Lastly, for any path $P_n$, let us orient the path from left to right (from its end $v_1$ to its other end $v_n$), so that we can make use of the notions of left and right.

The next two lemmas (Lemmas 4.1 and 4.2) are both stated using first and second player rather than Alice and Bob since they will sometimes be used with Alice as the first player and sometimes with Bob as the first player.

Lemma 4.1

For all $n\ge 1$, for the path $P_n$, the second player has a strategy that ensures that the largest connected subgraph of the first player is of order at most 2, even if one of the ends of $P_n$ is initially coloured by the first player and it is the first player’s turn.

Proof

Assume, w.l.o.g., that Alice is the first player, Bob is the second player, and $v_1$ is initially coloured red. Whenever Alice colours a vertex $v_j$ with $2\le j\le n$, Bob colours $v_{j-1}$ if it is uncoloured. If $v_{j-1}$ is already coloured, then Bob colours the closest (in terms of its distance in the path) uncoloured vertex that is to the right of $v_j$. Towards a contradiction, assume that there exist 3 consecutive red vertices, denoted by $x_1,x_2,x_3$ from left to right in $P_n$. By Bob’s strategy, concerning the 3 vertices $x_1,x_2,x_3$, Alice must have coloured $x_1$ first, then $x_2$, and then, $x_3$, as otherwise, Bob would have coloured at least one of them. But when Alice colours $x_2$, since $x_1$ is already coloured, then Bob will colour the closest uncoloured vertex to the right of $x_2$, which must be $x_3$ since it is uncoloured as it must get coloured by Alice after she colours $x_2$, and thus, we have a contradiction. $\square$

Lemma 4.2

Let $x \ge 1$ and $n \ge x$. Consider any path $P_n$ with x vertices initially coloured by the second player, and let y be the maximum order of an initial connected component of the second player.

• If $y=x$ and, either the component of the second player contains no ends of $P_n$ or $x=1$, then, if the first player starts, they have a strategy ensuring that the second player cannot create a connected component of order more than $x+1$;

• otherwise, if the first player starts, then they have a strategy ensuring that the second player cannot create a connected component of order more than x.

Proof

Assume, w.l.o.g., that Alice is the first player and Bob is the second player. We prove the lemma by induction on x. First, let us consider the case $x=1$. We prove this case by induction on n. If $n=1$, then the result is obvious, so let us focus on the general case. Without loss of generality, let $v_j$ ($1 \le j < n$) be the vertex initially coloured blue. Then, Alice first colours $v_{j+1}$. Let $Q=(v_1,\ldots ,v_j)$ and $Q'=(v_{j+2},\ldots ,v_n)$ (it may be that $Q'$ is empty and/or Q is restricted to one vertex). From now on, Alice “follows” Bob, that is, when Bob plays in Q (in $Q'$, resp.), Alice then plays in Q (in $Q'$, resp.), and both games are considered independently (since $v_{j+1}$ is coloured red). Considering Q as a path with one of its ends initially coloured blue, and applying Lemma 4.1 to it (with Bob as the first player), Alice has a strategy ensuring that Bob cannot create a connected blue component of order more than 2 in Q. On the other hand, after the first move of Bob in $Q'$, it is a path of order less than n with one vertex initially coloured blue and it is the turn of Alice. Thus, by induction (on n), Alice has a strategy ensuring that Bob cannot create a connected blue component of order more than 2 in $Q'$. Overall, Alice ensures that the largest connected blue component has order at most $2=x+1$. Hence, the claim holds for $x=1$.

Fig. 2

Case in the proof of Lemma 4.2 where $y=x=3$, $B=(v_i,\ldots ,v_{i+x-1})$ and contains no ends of $P_n$, and $i>2$ (first case when $x>1$). On her first turn, depicted in (a), Alice colours $v_{i+x}$. If Bob creates a connected component of order $x+1$ by colouring $v_{i-1}$ on his next turn, then Alice colours $z=v_{i-2}$, as depicted in (b). Otherwise, Alice colours $z=v_{i-1}$, as shown in (c) (Color figure online)

Let $x>1$ and let us assume by induction that the previous statement holds for all $x'<x$.

• Let us first assume that $y=x>1$ and the connected blue component B contains no ends of $P_n$, say $B=(v_i,\ldots ,v_{i+x-1})$, $1<i<n-x+1$. Alice first colours $v_{i+x}$ (see Fig. 2a). If Bob colours $v_{i-1}$ on his next turn (in which case there is a connected blue component of order $x+1$), then Alice colours $z=v_{i-2}$ (unless $i=2$, in which case Alice colours any arbitrary uncoloured vertex). Otherwise, Alice colours $z=v_{i-1}$ (in which case the largest connected blue component is of order x). Let $Q=(v_1,\ldots ,z)$ and $Q'=(v_{i+x+1},\ldots ,v_n)$ (it may be that Q and/or $Q'$ are empty, and, in particular, Q is empty if $z\notin \{v_{i-2},v_{i-1}\}$). See Fig. 2b, c for an illustration of the current configuration of coloured vertices. From now on, Alice “follows” Bob, that is, when Bob plays in Q (in $Q'$, resp.), Alice then plays in Q (in $Q'$, resp.), and both games are considered independently (since z and $v_{i+x}$ are coloured red). After the next move of Bob in Q ($Q'$, resp.), it is a path of order less than n with at most $2\le x$ vertices initially coloured blue and it is Alice’s turn. Thus, by induction (on n), Alice has a strategy ensuring that Bob cannot create a connected blue component of order more than $x+1$ in Q ($Q'$, resp.). Overall, Alice ensures that the largest connected blue component in $P_n$ is of order at most $x+1$. Hence, the claim holds in this case.

• Next, let us assume that $y=x> 1$ and the connected blue component B contains one end of $P_n$, i.e., $B=(v_1,\ldots ,v_x)$. Alice first colours $v_{x+1}$. Then, Bob colours any vertex in the subpath $Q=(v_{x+2},\ldots ,v_n)$ (assuming Q is not empty). Therefore, Q initially has one blue vertex and it is Alice’s turn. By the base case of the induction ($x=1$), Alice can ensure that the largest connected blue component in Q is of order at most 2. Overall, the largest connected blue component in $P_n$ is of order at most x. Hence, the claim holds in this case.

• Finally, let us assume that $y<x$. Let $(v_i,\ldots ,v_{i+y-1})$ be a largest connected blue component such that there is an initial blue vertex $v_j$ with $j>i+y$. Alice first colours $v_{i+y}$. Let $Q=(v_1,\ldots ,v_{i+y-1})$ and $Q'=(v_{i+y+1},\ldots ,v_n)$ (it may be that $Q'$ is empty). From now on, Alice “follows” Bob, that is, when Bob plays in Q (in $Q'$, resp.), Alice then plays in Q (in $Q'$, resp.), and both games are considered independently (since $v_{i+y}$ is coloured red). After the next move of Bob in Q ($Q'$, resp.), it is a path of order less than n with at most $y+1\le x$ vertices initially coloured blue (and if there is a connected blue component with x vertices, it must be in Q and it contains the end $v_{i+y-1}$ of the path Q) and it is Alice’s turn. Thus, by induction (on n), Alice has a strategy ensuring that Bob cannot create a connected blue component of order more than x in Q ($Q'$, resp.). Overall, Alice ensures that the largest connected blue component in $P_n$ is of order at most x. Hence, the claim holds in this case, and in general, since this is the last case.

$\square$

We can now deal with the general case of paths of odd order.

Theorem 4.3

For all $n\ge 1$, the path $P_n$ is A-win if and only if $n \in \{1,3,5,7,9\}$.

Proof

Note that, by Theorem 2.1, we need to prove that $P_n$ is A-win if $n \in \{1,3,5,7,9\}$, and $P_n$ is AB-draw otherwise. Let $P_n=(v_1,\ldots ,v_n)$. If n is even, then $P_n$ is AB-draw by Theorem 2.3 since $P_n$ is a reflection graph by Proposition 2.2. It is easy to see that, if $n \le 7$ and n is odd, then Alice wins by first colouring the center of $P_n$. If $n=9$, a winning strategy for Alice is described in Fig. 3. Hence, from now on, let us assume that $n\ge 11$ is odd.

Fig. 3

Winning strategy for Alice in $P_9$. The squares represent the vertices $v_1$ to $v_9$ from left to right. A number i in a red (blue, resp.) square indicates this vertex is the ith vertex coloured by Alice (Bob, resp.). Each arrow corresponds to a move of Bob and then one of Alice. The last moves in each case are omitted as it is easy to check the last possibilities (Color figure online)

In the main strategy that follows, we require that there are at least five vertices to the left or to the right of the first vertex Alice colours, and that is why it does not apply to the paths of odd order less than 11. We will now describe a strategy for Bob which ensures a draw.

Fig. 4

Second case in the proof of Theorem 4.3 where $\ell =j-2$. Bob begins by colouring $v_{j-4}$, as shown in (a). b The case in which Alice then colours $v_{j-3}$. c The case in which Alice then colours $v_t$ for $1\le t\le j-6$ (in the illustration, $t<j-6$) (Color figure online)

Let $v_j$, with $1\le j\le n$, be the first vertex coloured by Alice. Since $n\ge 11$, there are at least five vertices to the left or right of $v_j$, say, w.l.o.g., to the left of $v_j$, i.e., $6\le j\le n$. Bob colours $v_{j-1}$. Let $Q=(v_1,\ldots ,v_{j-1})$ and $Q'=(v_j,\ldots ,v_n)$. From now on, Bob “follows” Alice, that is, when Alice plays in Q (in $Q'$, resp.), Bob then plays in Q (in $Q'$, resp.), and both games are considered independently (since $v_{j-1}$ is coloured blue and $v_j$ is coloured red). Considering $Q'$ as a path with one of its ends initially coloured red, and applying Lemma 4.1 to it (with Alice as the first player), Bob has a strategy ensuring that Alice cannot create a connected red component of order more than 2 in $Q'$. Let $v_{\ell }$ be the first vertex that Alice colours in Q. We distinguish two cases:

• 1. $\ell \ne j-2$. Then, Bob colours $v_{j-2}$. During the next rounds, whenever Alice plays in Q, while it is possible, Bob colours a neighbour of the connected blue component containing $v_{j-1}$ and $v_{j-2}$. When it is not possible anymore, either the connected blue component is of order $\lceil (j-1)/2 \rceil \ge 3$ (in which case the largest connected red component in Q is of order $\lfloor (j-1)/2\rfloor$ and so, Alice does not win) or it is of order x with $2\le x<(j-1)/2$ and it is Bob’s turn. In the latter case, the connected blue component in Q consists of the vertices $v_{j-x},\ldots ,v_{j-1}$, and $v_{j-x-1}$ is red since Bob cannot colour a neighbour of the connected blue component. Let $R=(v_1,\ldots ,v_{j-x-1})$ and note that there are exactly x red vertices in R including $v_{j-x-1}$ (one of its ends). Then, applying Lemma 4.2 to R (with Bob as the first player), Bob has a strategy ensuring that Alice cannot create a connected red component of order more than x in R. As usual, whenever Bob cannot follow his strategy, he simply colours any arbitrary vertex. Hence, the game in $P_n$ ends in a draw in this case.

• 2. $\ell =j-2$. Then, Bob colours $v_{j-4}$ (illustrated in Fig. 4a). Now, if Alice colours $v_{j-3}$, then Bob colours $v_{j-5}$ (as shown in Fig. 4b), and vice versa, and this guarantees that there is a connected blue component of order at least 2. Otherwise, if Alice colours a vertex $v_t$ with $1\le t\le j-6$, then Bob colours $v_{t+1}$, unless $v_{t+1}$ is already coloured, in which case, Bob colours $v_{t-1}$. In the latter case, Bob can ensure a draw since he can ensure that Alice cannot create a connected red component of order more than 2 in $R^*=(v_1,\ldots ,v_{t-1})$ by Lemma 4.1 (with Alice as the first player). So, assume we are in the former case. Let $R=(v_1,\ldots ,v_t)$ and $R'=(v_{t+1},\ldots ,v_{j-5})$ (see Fig. 4c). From now on, Bob “follows” Alice (unless Alice colours $v_{j-5}$, in which case, Bob colours $v_{j-3}$), that is, when Alice plays in R (in $R'$, resp.), Bob then plays in R (in $R'$, resp.), and both games are considered independently (since $v_t$ is coloured red and $v_{t+1}$ is coloured blue). Considering R as a path with one of its ends initially coloured red, and applying Lemma 4.1 to it (with Alice as the first player), Bob has a strategy ensuring that Alice cannot create a connected red component of order more than 2 in R. Bob plays in $R'$ assuming that $v_{j-5}$ is already coloured red, and applying Lemma 4.1 to it (with Alice as the first player), Bob has a strategy ensuring that Alice cannot create a connected red component of order more than 2 in $R'$. As usual, whenever Bob cannot follow his strategy, he simply colours any arbitrary vertex. It is easy to see that, in this case, the largest connected blue (red, resp.) subgraph is of order at least 2 (at most 2, resp.).

This concludes the proof for $n\ge 11$. $\square$

Now, we address the largest connected subgraph game in cycles. We again start with a technical lemma for a specific case in paths, which we will use in the proof for cycles.

Lemma 4.4

Let $x \ge 3$, $n \ge x+1$, and let $n-x$ be odd. Consider any path $P_n$ with x vertices, including both ends, initially coloured blue. If Alice starts, then she has a strategy ensuring that Bob cannot create a connected blue component of order more than $x-1$ in $P_n$.

Proof

The first case, $x=3$, is proven by induction on n. If $n=4$, the result obviously holds, so assume that $n>4$ and that the induction holds for all $n'<n$.

• First, assume that the initial blue vertices are $v_1,v_2$, and $v_n$. Then, Alice colours $v_3$. Then, Bob colours any uncoloured vertex in $Q=(v_4,\ldots ,v_n)$. Now, Q has two blue vertices (and if there is a connected blue component of order 2 in Q, it contains the end $v_n$ of Q). By Lemma 4.2 (with Alice as the first player), Alice can ensure that Bob cannot create a connected blue component with more than two vertices in Q. Overall, Bob cannot create a connected blue component of order at least 3 in $P_n$.

• Next, let $v_1,v_j,v_n$ (with $2<j<n-1$) be the initial blue vertices. W.l.o.g. (up to reversing the path), assume that j is even (note that n is even since $n-x=n-3$ is odd). Then, Alice colours $v_{j+1}$. Let $Q=(v_1,\ldots ,v_{j})$ and $Q'=(v_{j+2},\ldots ,v_n)$ (it may be that $Q'$ is just the vertex $v_n$). From now on, Alice “follows” Bob, that is, when Bob plays in Q (in $Q'$, resp.), Alice then plays in Q (in $Q'$, resp.), and both games are considered independently (since $v_{j+1}$ is coloured red). For the game in $Q'$, applying Lemma 4.1 (with Bob as the first player), Alice can ensure the largest connected blue component is of order at most 2 in $Q'$. For the game in Q, by induction on $n'=|Q|<n$ (note that, because $n'=j$ is even, after the first turn of Bob in Q, the hypotheses hold for $x=3$ in Q), Alice can ensure the largest connected blue component is of order at most 2 in Q. Overall, Bob cannot create a connected blue component of order at least 3 in $P_n$.

Now, let us assume that $x>3$.

First, if there is a connected blue component of order $x-1$ containing $v_1$, then Alice colours $v_x$, and then she can ensure, by Lemma 4.1 (with Bob as the first player), that Bob cannot create a connected blue component with more than two vertices in $(v_{x+1},\ldots ,v_n)$.

Next, assume that there exists a connected blue component $(v_j,\ldots ,v_{j+x-3})$ of order $x-2$ not containing any end of $P_n$. By symmetry (up to reversing the path), let $j\le n-j-x+4$. Alice first colours $v_{j-1}$. Let $Q=(v_1,\ldots ,v_{j-2})$ and $Q'=(v_{j},\ldots ,v_n)$. From now on, Alice “follows” Bob, that is, when Bob plays in Q (in $Q'$, resp.), Alice then plays in Q (in $Q'$, resp.), and both games are considered independently (since $v_{j-1}$ is coloured red). Since $j \le n-j-x+4$, we get that $2j-4 \le n-x$. Since $n-x$ is odd, it implies that $2j-4 \le n-x-1$, and so, we get $j \le n-j-x+3$. Finally, since $j\ge 3$ (as the connected blue component $(v_j,\ldots ,v_{j+x-3})$ does not contain $v_1$ which is also blue), it follows that $n-j+1 \ge x+1$. Therefore, $Q'=(v_j,\ldots ,v_n)$ is of order at least $x+1$. When Bob plays in Q, Alice can ensure, by Lemma 4.1 (with Bob as the first player), that Bob cannot create a connected blue component with more than two vertices in Q. When Bob first plays in $Q'$, then $Q'$ becomes a path of order at least $x+1$ with x initial blue vertices, and its largest connected blue component contains its end $v_j$ and is of order at most $x-1$. By Lemma 4.2 (with Alice as the first player), Alice can ensure that Bob does not create a connected blue component of order more than $x-1$ in $Q'$.

Otherwise, there must be an uncoloured vertex $v_j$ such that at most $x-2$ blue vertices are on the left (on the right, resp.) of $v_j$. Then, Alice first colours $v_j$. Let $Q=(v_1,\ldots ,v_{j-1})$ and $Q'=(v_{j+1},\ldots ,v_n)$. From now on, Alice “follows” Bob, that is, when Bob plays in Q (in $Q'$, resp.), Alice then plays in Q (in $Q'$, resp.), and both games are considered independently (since $v_{j}$ is coloured red). By Lemma 4.2 (with Alice as the first player), Alice can ensure, both in Q and $Q'$, that Bob does not create a connected blue component with at least x vertices (note that after the first turn of Bob in Q ($Q'$, resp) it contains at most $x-1$ blue vertices including at least one of its ends). $\square$

Theorem 4.5

For all $n\ge 3$, the cycle $C_n$ is A-win if and only if n is odd.

Proof

If n is even, then $C_n$ is a reflection graph by Proposition 2.2, and so, is AB-draw by Theorem 2.3. Let us now assume that n is odd. We describe a winning strategy for Alice. If $n \le 5$, the result is obvious, so let us assume that $n>5$.

First, let us assume (independently of how this configuration eventually appears) that after $x\ge 3$ rounds, the vertices $v_1,\ldots ,v_x$ have been coloured red, the vertices $v_n$ and $v_{x+1}$ are coloured blue, and any $x-2$ other vertices in $\{v_{x+2},\ldots ,v_{n-1}\}$ are coloured blue (see Fig. 5 for an illustration). Note that it is now Alice’s turn. By Lemma 4.4, Alice may ensure that Bob cannot create a connected blue component of order at least x in the subgraph induced by $(v_{x+1},\ldots ,v_n)$. Therefore, in that situation, Alice wins.

Fig. 5

First case in the proof of Theorem 4.5 where, after $x=4$ rounds, the vertices $v_1,\ldots ,v_x$ are red, the vertices $v_n$ and $v_{x+1}$ are blue, and $x-2$ other vertices in $\{v_{x+2},\ldots ,v_{n-1}\}$ are blue (in this illustration, these vertices are $v_{n-1}$ and $v_{x+2}$) (Color figure online)

Now, let Alice first colour the vertex $v_1$. If Bob does not colour a neighbour of $v_1$ (say Bob colours $v_j$ with $3<j<n$, since $n>5$), then, on her second turn, Alice colours $v_2$. During the next rounds, while it is possible, Alice colours a neighbour of the connected red component. When it is not possible anymore, either the connected red component is of order $\lceil n/2 \rceil$ or it is of order at least 3 and we are in the situation of the above paragraph. In both cases, Alice wins.

Therefore, after Alice colours her first vertex (call it $v_2$), Bob must colour some neighbour of it (say $v_1$). By induction on the number $t \ge 1$ of rounds, let us assume that the game reaches, after t rounds, a configuration where, for every $1 \le i \le t$, the vertices $v_{2i-1}$ are coloured blue and the vertices $v_{2i}$ are coloured red. If $t=\lfloor n/2 \rfloor$, then Alice finally colours $v_n$ (recall that n is odd) and wins. Otherwise, let Alice colour $v_{2t+2}$.

• If Bob then colours $v_{2t+1}$, then we are back to the previous situation for $t'=t+1$. Then, eventually, Alice wins by induction on $n-2t$.

• If Bob does not colour $v_{2t+1}$, then Alice colours $v_{2t+1}$ and then continues to grow the connected red component containing $v_{2t+1}$ while possible. When it is not possible anymore, note that contracting the vertices $v_2$ to $v_{2t}$ to a single red vertex, we are back to the situation of the first paragraph of this proof (with a connected red component of order at least 3) and, therefore, Alice wins.

$\square$

5 Cographs

In the previous case of paths and cycles, we have seen examples where playing optimally depends more on positional play with respect to the previously coloured vertices and the graph’s properties, since the sparse structure of the graph makes it very easy for the players to stop the expansion of the opponent’s largest connected component. As a consequence, in such cases it is likely that the players must, at some point, stop growing their largest connected component, and start growing a new one. Obviously, such a strategy is likely to be far less viable in graph classes that are denser. In such denser graphs, the game actually tends to turn into a rather different one, where the players grow a single connected component each, that they have to keep “alive” for as long as possible. We illustrate these thoughts with the case of cographs, which leads us to introduce a few more notations to describe a linear-time algorithm deciding the outcome of the largest connected subgraph game in such instances.

A graph G is a cograph if it is $P_4$-free, i.e., if it does not contain any path with four vertices as an induced subgraph. The class of cographs can also be defined recursively as follows. The one-vertex graph $K_1$ is a cograph. Let $G_1$ and $G_2$ be two cographs. Then, the disjoint union $G_1+G_2$ is a cograph. Moreover, the join $G_1 \oplus G_2$, obtained from $G_1+G_2$ by adding all the possible edges between the vertices of $G_1$ and the vertices of $G_2$, is also a cograph. Note that a decomposition of a cograph (i.e., a building sequence of unions and joins performed from single vertices) can be computed in linear time [7].

To simplify notation in the theorem and its proof to follow, let ${{\mathcal {A}}}^*$ be the set of graphs G such that there exists a strategy for Alice that ensures a connected red component of order $\left\lceil \frac{|V(G)|}{2}\right\rceil$, regardless of Bob’s strategy. That is, ${{\mathcal {A}}}^*$ is the set of graphs such that Alice has a strategy to ensure a single connected red component.

Theorem 5.1

Let G be a cograph. There exists a linear-time algorithm that decides whether G is A-win or AB-draw, and whether $G\in \mathcal{A}^*$ or not.

Proof

The proof is by induction on $n=|V(G)|$. More precisely, we describe a recursive algorithm. If $n=1$, then G is clearly A-win and $G\in {{\mathcal {A}}}^*$.

Let us now assume that $n>1$. There are two cases to be considered. Either $G= G_1 \oplus G_2$ for some cographs $G_1$ and $G_2$, or $G = G_1+\ldots +G_m$, where, for every $1 \le i \le m$ ($m\ge 2$), $G_i$ is either a single vertex or is a cograph obtained from the join of two other cographs. For every $1 \le i \le m$, let us assume by induction that it can be computed in time linear in $|V(G_i)|$, whether $G_i$ is A-win or AB-draw and whether $G_i\in {{\mathcal {A}}}^*$ or not. Let us show, now, how to decide if G is A-win or AB-draw, and whether $G\in {{\mathcal {A}}}^*$ or not, in constant time.

• 1. Let us first assume that $\varvec{G=G_1\oplus G_2}$. There are three cases to be distinguished.

  • (a) If n is odd (so we may assume that $|V(G_2)|\ge 2$), then G is A-win and $G \in {{\mathcal {A}}}^*$.

    We describe a winning strategy for Alice. Alice first colours a vertex in $G_1$. In the second round, Alice colours a vertex in $G_2$ (it is possible since $|V(G_2)|\ge 2$). Then, Alice colours any uncoloured vertex in each of the remaining rounds. Regardless of Bob’s strategy, Alice ends with all the $\lceil \frac{n}{2} \rceil$ red vertices belonging to the same connected component. Since n is odd, G is A-win, and $G \in {{\mathcal {A}}}^*$.

  • (b) If $|V(G_1)|,|V(G_2)|\ge 2$ and n is even, then G is AB-draw and $G \in {{\mathcal {A}}}^*$.

    We describe a drawing strategy for Bob. W.l.o.g., Alice first colours a vertex in $G_1$. Then, Bob first colours a vertex in $G_1$ (it is possible since $|V(G_1)|\ge 2$). In the second round, Bob colours a vertex in $G_2$ (it is possible since $|V(G_2)|\ge 2$). Then, Bob colours any uncoloured vertex in each of the remaining rounds. Regardless of Alice’s strategy, Bob ends with all the n/2 blue vertices belonging to the same connected component. Since n is even, Alice cannot have a larger connected red component. Hence, G is AB-draw and $G \in {{\mathcal {A}}}^*$.

  • (c) Finally, let us assume that $|V(G_1)|=1$ (let u be the single vertex of $G_1$) and n is even (so $|V(G_2)|$ is odd). There are two cases to be considered.

    • i. If $G_2\notin {{\mathcal {A}}}^*$, then G is A-win and $G \in {{\mathcal {A}}}^*$.

      We describe a winning strategy for Alice. Alice first colours u. Then, she plays in $G_2$ as the second player, and thus, she can ensure that any connected blue component is of order less than $\left\lceil \frac{|V(G_2)|}{2} \right\rceil =\lceil \frac{n-1}{2}\rceil$ in $G_2$ since $G_2\notin {{\mathcal {A}}}^*$. Since u is a universal vertex, regardless of Bob’s strategy, Alice ensures a connected red component of order n/2, and so G is A-win and $G \in {{\mathcal {A}}}^*$.

    • ii. If $G_2\in {{\mathcal {A}}}^*$, then G is AB-draw and $G \in {{\mathcal {A}}}^*$.

      We describe a drawing strategy for Bob. If Alice first colours a vertex of $G_2$, then Bob colours u, and then Bob colours any uncoloured vertex of $G_2$ in each of the subsequent rounds. Then, Bob ensures a connected blue component of order n/2, and so G is AB-draw and $G \in {{\mathcal {A}}}^*$.

      Otherwise, if Alice starts by colouring u, then Bob can play as the first player in $G_2$ and, in doing so, ensure a connected blue component of order $\lceil \frac{n-1}{2}\rceil =n/2$ in $G_2$. Then, again G is AB-draw and $G \in {{\mathcal {A}}}^*$.

• 2. Now, let us assume that $\varvec{G=G_1+\ldots +G_m}$ where, for every $1 \le i \le m$ ($m\ge 2$), $G_i$ is either a single vertex or is a cograph obtained from the join of two other cographs. For all $1\le i\le m$, if $G_i$ is a cograph obtained from the join of two other cographs, then let those two cographs be $G_i'$ and $G_i''$, and let $|V(G_i')|\ge |V(G_i'')|$. Also, let $n_i = |V(G_i)|$ for every $1 \le i \le m$, and let us assume that $n_1 \ge \ldots \ge n_m$.

  To simplify the case analysis to follow, we will show that we can make several assumptions. First note that, if $n_1=1$, then G is AB-draw (since $n_2=1$ as $m\ge 2$) and $G\in {{\mathcal {A}}}^*$ if and only if $G=G_1+G_2$. Hence, we may assume that $n_1>1$. Second, if $n_2=1$, then the result of the game in G is the same as the result of the game in $G_1$, and this result is known since $G_1$ is a join (recall Case 1 of the proof). Moreover, in this case, $G\in {{\mathcal {A}}}^*$ if and only if $n_1$ is odd and $G=G_1+G_2$. Hence, we may also assume that $n_2>1$. Lastly, in what follows, for any of the winning strategies described for Alice, whenever Bob colours a vertex in $G_j$ for $3\le j\le m$, Alice also colours a vertex in $G_j$ on her next turn. The same holds for any of the drawing strategies for Bob (with Bob and Alice reversed), except for Case 2(e)ii, in which case the same only holds for $4\le j\le m$. This guarantees that a player never has a connected component of order more than $\lceil \frac{n_j}{2}\rceil$ in $G_j$ for $3\le j\le m$ (except for Case 2(e)ii in which case the same only holds for $4\le j\le m$). Let us remark that Alice will always have a connected red component of order at least $\lceil \frac{n_1}{2}\rceil$ in all of the winning strategies described for Alice below, and Bob will always have a connected blue component of order at least $\lceil \frac{n_1}{2}\rceil$ in all of the drawing strategies described for Bob below. Hence, for all of the cases except Case 2(e)ii, we can assume that $G=G_1+G_2$, and for Case 2(e)ii, we can assume that $G=G_1+G_2+G_3$. In what follows, if a player cannot follow their strategy in a round, unless otherwise stated, they simply colour any arbitrary vertex in that round and then resume their strategy for the subsequent rounds.

  There are five cases to be considered, and recall that we assume that $n_1>1$ and $n_2>1$ as stated above, which implies that $G_1''$ and $G_2''$ exist. Note also that in Case 2(e)iii below, the statement involves $n_3$, which is not defined if $m=2$; in such cases, we consider that $n_3=0$, i.e., regard $G_3$ as an empty graph. Moreover, since Bob always has a strategy where, for each $1\le i\le m$, he colours at least $\lfloor \frac{n_i}{2}\rfloor$ vertices of $G_i$ blue, and since $n_2>1$, then $G\notin {{\mathcal {A}}}^*$ in all five of the following cases. Thus, all that remains to show is the outcome of the game on G for each of the cases.

  • (a) If $n_1=n_2$, then G is AB-draw.

    We describe a drawing strategy for Bob. Assume, w.l.o.g., that Alice first colours a vertex in $G_1$. Bob then colours a vertex in $G_2''$. Then, whenever Alice colours a vertex in $G_1$ ($G_2$, resp.), Bob also colours a vertex in $G_1$ ($G_2$, resp.). In particular, if Bob is to colour a vertex in $G_2$, then he colours one in $G_2'$ first if possible, and if not, then he colours a vertex in $G_2''$, and lastly, if that is not possible, he colours a vertex in $G_1$. Similarly, if Bob is to colour a vertex in $G_1$ by this strategy, but cannot since all of the vertices of $G_1$ are coloured, then he colours one in $G_2'$ first if possible, and if not, then he colours a vertex in $G_2''$.

    If $n_1$ is odd, then by this strategy, Bob ensures a connected blue component of order $\frac{n_2-1}{2}+1=\frac{n_1-1}{2}+1$ in $G_2$ and that the largest connected red component in G is of order at most $\frac{n_1-1}{2}+1$.

    If $n_1$ is even, then by this strategy, if Alice colours the last vertex in $G_1$, then Bob ensures a connected blue component of order $\lceil \frac{n_2-1}{2}\rceil +1=\lceil \frac{n_1-1}{2}\rceil +1$ in $G_2$ and that the largest connected red component in G is of order at most $\lceil \frac{n_1-1}{2}\rceil +1$. If, on the other hand, Alice did not colour the last vertex in $G_1$, and so, she coloured the last vertex in $G_2$, then Bob ensures a connected blue component of order $\lceil \frac{n_2-2}{2}\rceil +1=\frac{n_1}{2}$ in $G_2$ and that the largest connected red component in G is of order at most $\frac{n_1}{2}$. Hence, G is AB-draw.

  • (b) If $n_1>n_2$ and $n_1$ is odd, then G is A-win.

    We describe a winning strategy for Alice. Alice first colours a vertex in $G_1$. Then, whenever Bob colours a vertex in $G_1$ ($G_2$, resp.), Alice colours a vertex in $G_1$ ($G_2$, resp.). By Case 1(a), Alice has a winning strategy in $G_1$ ensuring a connected red component of order at least $\lceil \frac{n_1}{2}\rceil$. By Case 1, Alice ensures that any connected blue component in $G_2$ is of order at most $\lceil \frac{n_2}{2}\rceil < \lceil \frac{n_1}{2}\rceil$. Hence, G is A-win.

  • (c) If $n_1>n_2$, $n_1$ is even, and $|V(G_1'')|\ge 2$, then G is AB-draw.

    We describe a drawing strategy for Bob. Whenever Alice colours a vertex in $G_1$ ($G_2$, resp.), Bob also colours a vertex in $G_1$ ($G_2$, resp.). By Case 1(b), Bob has a drawing strategy in $G_1$ ensuring a connected blue component of order at least $\frac{n_1}{2}$. By Case 1, Bob ensures that any connected red component in $G_2$ is of order at most $\lceil \frac{n_2}{2}\rceil \le \frac{n_1}{2}$. Hence, G is AB-draw.

  • (d) If $n_1>n_2$, $n_1$ is even, $|V(G_1'')|=1$, and $G_1'\in {{\mathcal {A}}}^*$, then G is AB-draw.

    We describe a drawing strategy for Bob. Whenever Alice colours a vertex in $G_1$ ($G_2$, resp.), Bob also colours a vertex in $G_1$ ($G_2$, resp.). By Case 1(c)ii, Bob has a drawing strategy in $G_1$ ensuring a connected blue component of order at least $\frac{n_1}{2}$. By Case 1, Bob ensures that any connected red component in $G_2$ is of order at most $\lceil \frac{n_2}{2}\rceil \le \frac{n_1}{2}$. Hence, G is AB-draw.

  • (e) If $n_1>n_2$, $n_1$ is even, $|V(G_1'')|=1$, and $G_1'\notin {{\mathcal {A}}}^*$, then there are three cases to be considered.

    • i. If $n_1>n_2+1$, then G is A-win.

      We describe a winning strategy for Alice. Alice first colours a vertex in $G_1$. Then, whenever Bob colours a vertex in $G_1$ ($G_2$, resp.), Alice colours a vertex in $G_1$ ($G_2$, resp.). By Case 1(c)i, Alice has a winning strategy in $G_1$ ensuring a connected red component of order at least $\frac{n_1}{2}$, and that any connected blue component in $G_1$ is of order less than $\frac{n_1}{2}$. By Case 1, Alice ensures that any connected blue component in $G_2$ is of order at most $\lceil \frac{n_2}{2}\rceil <\frac{n_1}{2}$. Hence, G is A-win.

    • ii. If $n_1=n_2+1=n_3+1$, then G is AB-draw.

      We describe a drawing strategy for Bob. Whenever Alice colours a vertex in $G_1$, Bob also colours a vertex in $G_1$. By Case 1, this ensures that $\frac{n_1}{2}$ of the vertices in $G_1$ are red and $\frac{n_1}{2}$ of them are blue. The first time that Alice colours a vertex $v\in V(G_2)\cup V(G_3)$, assume, w.l.o.g., that $v\in V(G_2)$. Bob then colours a vertex in $G_3''$. Then, whenever Alice colours a vertex in $G_2$ ($G_3$, resp.), Bob also colours a vertex in $G_2$ ($G_3$, resp.). In particular, if Bob is to colour a vertex in $G_3$, then he colours one in $G_3'$ first if possible, and if not, then he colours a vertex in $G_3''$, and lastly, if that is not possible, he colours a vertex in $G_2$. As in Case 2(a), by this strategy, Bob ensures a connected blue component of order $\lceil \frac{n_3}{2}\rceil =\frac{n_1}{2}$ in $G_3$ and that any connected red component in $G_2$ is of order at most $\lceil \frac{n_2}{2}\rceil =\frac{n_1}{2}$. Hence, G is AB-draw.

    • iii. If $n_1=n_2+1$ and $n_2>n_3$, then G is A-win.

      We describe a winning strategy for Alice. Alice first colours the vertex in $G_1''$. Then, Alice colours vertices in $G_1$ as long as she can. By Case 1(c)i, she ensures that any connected blue component in $G_1$ is of order less than $\frac{n_1}{2}$. If it is Alice’s turn, there is a connected red component of order $n_1-k$ in $G_1$ for some $0\le k \le \frac{n_1}{2}$, and it is the first round in which she can no longer colour vertices in $G_1$, then Bob coloured k vertices in $G_1$ and $n_1-2k$ vertices in $G_2$. Then, any connected blue component in $G_2$ is of order at most $\lceil \frac{n_2-n_1+2k-1}{2}\rceil +n_1-2k=n_1-k-1<n_1-k$. Hence, G is A-win.

The statement of the theorem then follows since a decomposition of a cograph can be computed in linear time. $\square$

6 Further Work

Several directions for further work are of interest. For example, it would be interesting to study the game in other graph classes such as trees and interval graphs. Since some grids (e.g., Cartesian grids, king grids, etc.) of even order are AB-draw (by Proposition 2.2 and Theorem 2.3), grids of odd order could also be subject to a dedicated focus. Just as reflection graphs define a quite diverse class of graphs that are AB-draw, another direction could be to find large and interesting classes of graphs that are A-win. Graphs of odd order in which Alice can always construct a single connected red component are A-win, and so, perhaps a class of dense graphs of odd order would be a prime candidate.

As illustrated with the cases of paths and cycles, and cographs, there is not a unique way to play the largest connected subgraph game, as Alice and Bob, depending on the graph’s properties, might have several strategical options to choose from. Each such strategy is already interesting by itself, and could thus be subject to a dedicated focus as further work on the topic. For instance, the strategies we have developed in cographs could be investigated through a Maker-Breaker variant of the largest connected subgraph game, where Alice selects remaining vertices one at a time while Bob deletes non-selected vertices, the eventual goal for Alice being to get the largest connected subgraph possible, while Bob aims at minimising the order of the largest connected subgraph.