Maker-Maker Games of Rank 4 Are PSPACE-Complete

The membership in PSPACE is well known for Maker-Maker games. Let $𝒢=(V,E_L,E_R)$ be an achievement positional game with blue edges of size $2$ or $3$ and pairwise disjoint red edges of size $2$. We define the hypergraph $H=(V\cup \{u,v\},E)$, where $u$ and $v$ are new vertices and:

Note that $H$ has rank $4$, is efficiently computed from $𝒢$, and behaves the exact same as the achievement positional game ${𝒢}^{\prime }=(V\cup \{u,v\},E,E)$: the first player has a winning strategy for the Maker-Maker game on $H$ if and only if Left has a winning strategy on ${𝒢}^{\prime }$ as the first player. Therefore, to deduce the PSPACE-hardness of Maker-Maker games of rank $4$ from Theorem 3, it suffices to show that Left has a winning strategy on ${𝒢}^{\prime }$ as the first player if and only if Left has a winning strategy on $𝒢$ as the first player.

• $\mathrm{■}$

  First suppose that Left has a winning strategy on $𝒢$ as the first player. Then, playing first on ${𝒢}^{\prime }$, Left can simply start by picking $u$, which forces Right to pick $v$ because $\{u,v\}\in E$. The updated game is precisely $𝒢$, so Left has a winning strategy as the first player.

• $\mathrm{■}$

  Conversely, suppose that Left has a winning strategy $𝒮$ on ${𝒢}^{\prime }$ as the first player. We claim that $𝒮$ necessarily has Left picking $u$ as his first move. Indeed:

  • –

    Suppose that $𝒮$ instructs Left to start by picking $v$. Then Right is forced to pick $u$. After that move, $E_R$ forms a complete pairing of the updated blue edges.

  • –

    Now, suppose that $𝒮$ instructs Left to start by picking some $w\notin \{u,v\}$. Then Right has no forced move since $\{u,v\}$ is the only element of $E$ of size less than $3$. Therefore, Right can pick $u$, which forces Left to pick $v$. If Right has no forced move, then $E_R$ forms a complete pairing of the updated blue edges. If Right has a forced move i.e. there exists some (necessarily unique) $w^{\prime }$ such that $\{v,w,w^{\prime }\}\in E$, then Right picks $w^{\prime }$, and $E_R\setminus \{\{w,w^{\prime }\}\}$ forms a complete pairing of the updated blue edges after that move.

  We see that, if $𝒮$ does not instruct Left to pick $u$ as his first move, then Right can always obtain a non-losing pairing strategy by Lemma 1, contradicting the fact that $𝒮$ is winning for Left. In conclusion, $𝒮$ instructs Left to start by picking $u$, which forces Right to pick $v$. Since the updated game after these two moves is precisely $𝒢$, we conclude that Left has a winning strategy on $𝒢$ as the first player.

$◀$

1. (i)

   This is a direct consequence of the definition of regular play.

2. (ii)

   Since Right has picked ${\tau }_k$ for all $k\in ⟦1,i⟧$, all trap-edges in ${\bigcup }_{1\le k\le i}{T}_k$ are dead. Now, consider some $\{t_{i^{\prime }},{\tau }_{i^{\prime }},u\}\in T_{i^{\prime }}$ where $i^{\prime }\in ⟦i+1,n⟧$. Clearly, $t_{i^{\prime }}$ and ${\tau }_{i^{\prime }}$ are unpicked. Let $e$ be the red edge containing $u$. By definition of a trap-edge, there are three possibilities for $e$. If $e\in G_k^R$ for some $k\in ⟦i^{\prime }+1,n⟧$, then $u$ is unpicked since $k>i$. If $e$ is a destruction-edge of the form $\{b_j,d_j\}$, then $u$ is unpicked since those vertices are never picked during regular play. Finally, if $e$ is a destruction-edge of the form $\{b_j^r,d_j^r\}$ where $\text{ind}({\mathrm{\ell }}_j^r)\ge i^{\prime }$, then $u$ could only have been picked during step (2) or (4) of some round of regular play, however this is impossible: since $\text{ind}({\mathrm{\ell }}_j^r)>i$, the key vertex $v({\mathrm{\ell }}_j^r)$ has not yet been picked.

3. (iii)

   Let $e=\{v({\mathrm{\ell }}_j^r),a_j^r,d_j^r\}$ be a link-edge. First, suppose that $\text{ind}({\mathrm{\ell }}_j^r)\le i$, i.e. $v({\mathrm{\ell }}_j^r)$ has already been picked. If Right has picked $v({\mathrm{\ell }}_j^r)$, then $e$ is dead. If Left has picked $v({\mathrm{\ell }}_j^r)$, then Right has been forced to kill $e$ by picking $a_j^r$ during step (4) of round $\text{ind}({\mathrm{\ell }}_j^r)$ of regular play. Finally, if $\text{ind}({\mathrm{\ell }}_j^r)>i$, then $e$ is intact as $v({\mathrm{\ell }}_j^r)$ has not yet been picked.

4. (iv)

   All destruction-edges of the form $\{b_j,d_j\}$ are intact since those vertices are never picked during regular play. Consider a destruction-edge of the form $e=\{b_j^r,d_j^r\}$. Assume $\text{ind}({\mathrm{\ell }}_j^r)\le i$, otherwise $e$ is clearly intact. If Left has picked $v({\mathrm{\ell }}_j^r)$, then Left has also killed $e$ by playing the greedy move $d_j^r$ during step (4) of round $\text{ind}({\mathrm{\ell }}_j^r)$ of regular play. If Right has picked $v({\mathrm{\ell }}_j^r)$ and $\text{ind}({\mathrm{\ell }}_j^r)\le i-1$, then Left has been forced to kill $e$ by picking $d_j^r$ during step (2) of round $\text{ind}({\mathrm{\ell }}_j^r)+1$ of regular play. If Right has picked $v({\mathrm{\ell }}_j^r)$ and $\text{ind}({\mathrm{\ell }}_j^r)=i$, then $e$ is intact as the corresponding greedy move has not yet been played (it will during round $i+1$ of regular play if ).

5. (v)

   The fact that Left has not picked any vertex in butterfly-edges and that the butterfly-edges $\{b_j,b_j^4,b_j^5\}$ and $\{b_j,b_j^5,b_j^6\}$ are intact for all $j\in ⟦1,m⟧$ is a direct consequence of the definition of regular play. Now, let $j\in ⟦1,m⟧$. If Left has picked $v({\mathrm{\ell }}_j^1)$, $v({\mathrm{\ell }}_j^2)$ and $v({\mathrm{\ell }}_j^3)$, then, by definition of regular play, Right has played no move inside the butterfly-edges in $B_j$ and Left has killed the destruction-edges $\{b_j^1,d_j^1\}$, $\{b_j^2,d_j^2\}$ and $\{b_j^3,d_j^3\}$ with greedy moves. If $v({\mathrm{\ell }}_j^r)$ is unpicked for some $r\in ⟦1,3⟧$, then $\text{ind}({\mathrm{\ell }}_j^r)>i$ so $\{b_j^r,d_j^r\}$ is intact. Finally, suppose that Left has picked $v({\mathrm{\ell }}_j^r)$ for some $r\in ⟦1,3⟧$, which implies that $\text{ind}({\mathrm{\ell }}_j^r)\le i$. If $\text{ind}({\mathrm{\ell }}_j^r)\le i-1$, then Right has killed $\{b_j,b_j^1,b_j^2\}$ or $\{b_j,b_j^2,b_j^3\}$ by playing the greedy move $b_j^r$ during step (2) of round $\text{ind}({\mathrm{\ell }}_j^r)+1$ of regular play. If $\text{ind}({\mathrm{\ell }}_j^r)=i$, then $\{b_j^r,d_j^r\}$ is intact.

$\mathrm{⊲}$

We now show that regular play leads to the desired result for the game, i.e. Left wins correspond to Falsifier wins.

First, suppose that Falsifier has a winning strategy $𝒮$ for 3-QBF on $\varphi$ as the first player. We define the following winning strategy for Left on $𝒢$ as the first player. During Phase 1, for all $i\in ⟦1,n⟧$, Left chooses $\mu (x_i)$ according to $𝒮$ and depending on $\mu (x_1),\mu (y_1),\mathrm{\dots },\mu (x_{i-1}),\mu (y_{i-1})$, so that $\mu$ falsifies some clause $c_j$ of $\varphi$. By definition of $\mu$, this means Left has picked $v({\mathrm{\ell }}_j^1)$, $v({\mathrm{\ell }}_j^2)$ and $v({\mathrm{\ell }}_j^3)$. Therefore, by item (v) of Claim 5, the edges in $B_j$ form an intact blue butterfly and all red edges intersecting that butterfly are dead apart from $\{b_j,d_j\}$. As Left is next to play, he picks $b_j$. After that, Right may stall by playing inside intact red edges (in which case Left picks the other vertex of the red edge each time), but at some point she will have to pick some $u$ that does not threaten a win in one move. By symmetry, assume $u\notin \{b_j^4,b_j^5,b_j^6\}$. Left then picks $b_j^5$ and will win the game by picking $b_j^4$ or $b_j^6$ with his next move.

Now, suppose that Satisfier has a winning strategy $𝒮$ for 3-QBF on $\varphi$ as the second player. We define the following non-losing (actually, drawing) strategy for Right on $𝒢$ as the second player. During Phase 1, for all $i\in ⟦1,n⟧$, Right chooses $\mu (y_i)$ depending on $\mu (x_1),\mu (y_1),\mathrm{\dots },\mu (x_i)$ and according to $𝒮$, so that $\mu$ ends up satisfying $\varphi$. By Claim 5 applied to $i=n$, all blue edges that are not butterfly-edges are dead. Moreover, for all $j\in ⟦1,m⟧$, the clause $c_j$ being satisfied means that Right has picked at least one of $v({\mathrm{\ell }}_j^1)$, $v({\mathrm{\ell }}_j^2)$ or $v({\mathrm{\ell }}_j^3)$, so item (v) of Claim 5 ensures that one of the butterfly-edges $\{b_j,b_j^1,b_j^2\}$ and $\{b_j,b_j^2,b_j^3\}$ is dead or some destruction-edge among $\{b_j^1,d_j^1\}$, $\{b_j^2,d_j^2\}$ and $\{b_j^3,d_j^3\}$ is intact. Also recall that the destruction-edge $\{b_j,d_j\}$ is intact for all $j\in ⟦1,m⟧$ by Claim 5. As Left is next to play, he picks some $u$. Since Left had not picked any vertex in butterfly-edges before, Right’s move is not forced. For all $j\in ⟦1,m⟧$ (in any order) such that $u\notin \{b_j,d_j\}$, Right picks $b_j$, forcing Left to pick $d_j$. If $u\notin {\bigcup }_{1\le j\le m}\{b_j,d_j\}$, then all blue edges are dead and the proof is over. Otherwise, let $j_0$ be the unique index such that $u\in \{b_{j_0},d_{j_0}\}$. Assume $u=b_{j_0}$, otherwise Right kills all remaining blue edges by picking $b_{j_0}$ herself. Recall that, either one of the butterfly-edges $\{b_{j_0},b_{j_0}^1,b_{j_0}^2\}$ and $\{b_{j_0},b_{j_0}^2,b_{j_0}^3\}$ was already dead by the end of Phase 1, or some destruction-edge $\{b_{j_0}^r,d_{j_0}^r\}$ was intact. In the latter case, Right picks $b_{j_0}^r$, forcing Left to pick $d_{j_0}^r$, so that one of the butterfly-edges $\{b_{j_0},b_{j_0}^1,b_{j_0}^2\}$ and $\{b_{j_0},b_{j_0}^2,b_{j_0}^3\}$ is now dead. Right picks $b_{j_0}^5$. At most one butterfly-edge is not dead at this point, and that edge has two unpicked vertices, so Right will kill it with her next move. $\mathrm{⊲}$

Let ${𝒢}^{\prime }=(V^{\prime },E_L^{\prime },E_R^{\prime })$ be the updated game, and let $i\in ⟦1,n⟧$ be the current round of regular play. There are three types of moves for Right in regular play: forced move, greedy move, or “decision move” between $y_i^{𝖳}$ and $y_i^{𝖥}$.

• $\mathrm{■}$

  Let us first consider the case where regular play suggests a forced move. Clearly, Left is indeed threatening to win in one move (recall that, by picking $x_i^{𝖳}$ or $x_i^{𝖥}$ at the beginning of the round, Left has “activated” every edge of the form ${\{u,u^{\prime }\}}^{(i)}$ into an actual blue edge of size $2$: $\{u,u^{\prime }\}$ in ${𝒢}^{\prime }$). Therefore, the only way Right’s move would not actually be forced is if Right could win in one move herself, but this is not the case since regular play has Left defending all of Right’s threats.

• $\mathrm{■}$

  Now, we consider the case where regular play suggests a greedy move $b_j^r$ during step (2), which implies that $\text{ind}({\mathrm{\ell }}_j^r)=i-1$ and that Right has picked $v({\mathrm{\ell }}_j^r)$ during round $i-1$ of regular play. Note that neither player is threatening a win in one move. Therefore, to show that this is a valid greedy move as per Lemma 2, it suffices to show that $d_j^r\notin e$ for all $e\in E_L^{\prime }$. The only blue edges containing $d_j^r$ in the original game were the link-edge $\{v({\mathrm{\ell }}_j^r),a_j^r,d_j^r\}$ and some trap-edges. The link-edge $\{v({\mathrm{\ell }}_j^r),a_j^r,d_j^r\}$ is dead since Right has picked $v({\mathrm{\ell }}_j^r)$. Now, consider a trap-edge $e=\{t_k,{\tau }_k,d_j^r\}$ for some $k\in ⟦1,n⟧$. By definition of the trap-edges, we have $\text{ind}({\mathrm{\ell }}_j^r)\ge k$. Since $\text{ind}({\mathrm{\ell }}_j^r)=i-1$, we have , so Right has already killed $e$ by picking ${\tau }_k$ during round $k$ of regular play.

• $\mathrm{■}$

  Finally, consider the case where regular play suggests picking $y_i^{𝖳}$ or $y_i^{𝖥}$ (the updated variable gadget is pictured in Figure 4). Suppose that Right picks some $u\in V^{\prime }\setminus \{y_i^{𝖳},y_i^{𝖥}\}$: we show that Left has a winning strategy after that move. We can assume that there exists $e\in E_R^{\prime }$ of the form $e=\{u,u^{\prime }\}$, otherwise Left has no forced move and wins in two moves by picking $y_i^{𝖳}$ for instance since $\{y_i^{𝖳},y_i^{𝖥}\},\{y_i^{𝖳},{\zeta }_i\}\in E_L^{\prime }$ (we say that $(y_i^{𝖥},y_i^{𝖳},{\zeta }_i)$ is a blue $P_3$). Let us determine the set $E_R^{\prime }$. We know which red edges were intact by the end of round $i-1$ of regular play thanks to Claim 5, moreover some more red edges were killed during steps (1) and (2) of round $i$: $\{x_i^{𝖳},w_i\}$, $\{x_i^{𝖥},w_i^{\prime }\}$, $\{s_i,t_i\}$, and all $\{b_j^r,d_j^r\}$ such that $\text{ind}({\mathrm{\ell }}_j^r)=i-1$ and Right has picked $v({\mathrm{\ell }}_j^r)$. All in all, we get:

  $$E_R^{\prime }=\{\{y_i^{𝖳},{\omega }_i\},\{y_i^{𝖥},{\omega }_i^{\prime }\},\{{\zeta }_i,{\zeta }_i^{\prime }\},\{{\tau }_i,{\delta }_i\}\}\cup \bigcup _{k=i+1}^n{G}_k^R\cup \bigcup _{j=1}^m\{\{b_j,d_j\}\}\cup \bigcup _{\begin{array}{c}1\le j\le m\\ 1\le r\le 3\\ \text{ind}({\mathrm{\ell }}_j^r)\ge i\end{array}}\{\{b_j^r,d_j^r\}\}.$$

  1. 1)

     Case $e\notin \{\{y_i^{𝖳},{\omega }_i\},\{y_i^{𝖥},{\omega }_i^{\prime }\},\{{\zeta }_i,{\zeta }_i^{\prime }\},\{{\tau }_i,{\delta }_i\}\}$. This is where the trap-edges come into play. Left has triggered the trap-edges in $T_i$ by picking $t_i$ earlier. If Right had followed regular play, then she would have ended up picking ${\tau }_i$ after a sequence of forced moves, thus defusing these traps. However, she has not, and she will lose the game. Indeed, by definition of $T_i$, there exists the trap-edge $\{t_i,{\tau }_i,u^{\prime }\}$. Left now picks $u^{\prime }$ (forced move). Since Left had picked $t_i$ during step (1), Right is forced to pick ${\tau }_i$. In turn, Left is forced to pick ${\delta }_i$ because $\{{\tau }_i,{\delta }_i\}\in E_R^{\prime }$, then Right is forced to pick ${\lambda }_i$ because $\{{\delta }_i,{\lambda }_i\}\in E_L^{\prime }$. Since ${\lambda }_i$ is in no red edge, Left has no forced move and wins using the blue $P_3$ $(y_i^{𝖥},y_i^{𝖳},{\zeta }_i)$ for instance.

  2. 2)

     Case $e\in \{\{y_i^{𝖳},{\omega }_i\},\{y_i^{𝖥},{\omega }_i^{\prime }\},\{{\zeta }_i,{\zeta }_i^{\prime }\},\{{\tau }_i,{\delta }_i\}\}$ i.e. $u\in \{{\omega }_i,{\omega }_i^{\prime },{\zeta }_i,{\zeta }_i^{\prime },{\tau }_i,{\delta }_i\}$. All options lead to a sequence of forced moves, at the end of which Left can use a blue $P_3$ to win:
     
     
     
     
     
     

$\mathrm{⊲}$

Note that, if there exists a clause $c_j$ such that Left has already picked $v({\mathrm{\ell }}_j^1)$, $v({\mathrm{\ell }}_j^2)$ and $v({\mathrm{\ell }}_j^3)$, then Left can follow regular play until the end of Phase 1 (making arbitrary choices for the remaining key vertices) and win the game. Indeed, Claim 7 already tells us that Right has no interest in deviating from regular play, and Left will win during Phase 2 as we have seen in the proof of Claim 6. Therefore, we assume that there is no clause $c_j$ such that Left has already picked $v({\mathrm{\ell }}_j^1)$, $v({\mathrm{\ell }}_j^2)$ and $v({\mathrm{\ell }}_j^3)$. This assumption will only be used once in this proof.

Let ${𝒢}^{\prime }=(V^{\prime },E_L^{\prime },E_R^{\prime })$ be the updated game, and let $i\in ⟦1,n⟧$ be the current round of regular play. Since $E_R^{\prime }$ forms a complete pairing of $(V^{\prime },E_R^{\prime })$, Lemma 1 ensures that Left can play any move and still have a non-losing pairing strategy after that move. In particular, to establish optimality of the move(s) that regular play suggests for Left, it suffices to show that any other move for Left gives Right a drawing strategy. There are three types of moves for Left in regular play: forced move, greedy move, or “decision move” between $x_i^{𝖳}$ and $x_i^{𝖥}$.

• $\mathrm{■}$

  Let us start by checking that Left cannot win in one move. This is clear for the blue guide-edges and the link-edges, as regular play clearly has Right defending these threats. As for the butterfly-edges, Left never even picks one of their vertices during regular play. Now, consider a trap-edge $\{t_{i^{\prime }},{\tau }_{i^{\prime }},u\}\in T_{i^{\prime }}$, and assume that Right has not yet picked ${\tau }_{i^{\prime }}$ (otherwise that edge is already dead), which implies that $i^{\prime }\ge i$. We claim that $u$ is also unpicked, so that Left cannot win in one move with that edge. To show this, we consider all three cases for the red edge $e$ that contains $u$, according to the definition of $T_i^{\prime }$.

  • –

    First of all, suppose that $e\in G_k^R$ for some $k\in ⟦i^{\prime }+1,n⟧$. Since $k>i$, $u$ is clearly unpicked.

  • –

    Next, suppose that $e=\{b_j,d_j\}$ for some $j\in ⟦1,m⟧$. Since those vertices are never picked during regular play, $u$ is unpicked.

  • –

    Finally, suppose that $e=\{b_j^r,d_j^r\}$ for some $j\in ⟦1,m⟧$ and $r\in ⟦1,3⟧$ such that $\text{ind}({\mathrm{\ell }}_j^r)\ge i^{\prime }$. Assume that $v({\mathrm{\ell }}_j^r)$ has been picked, otherwise $u$ is clearly unpicked. In particular, we necessarily have $\text{ind}({\mathrm{\ell }}_j^r)=i^{\prime }=i$. If Right has picked $v({\mathrm{\ell }}_j^r)$, then she will not play the greedy move $b_j^r$ until round $i+1$ of regular play. If Left has picked $v({\mathrm{\ell }}_j^r)$, then he will not play the greedy move $d_j^r$ until step (4) of the current round $i$ of regular play. Note that step (4) has not been reached yet, otherwise step (3) would have been over, so Right would have already picked ${\tau }_i={\tau }_{i^{\prime }}$.

  We see that $u$ is unpicked in each case. In conclusion, Left cannot win in one move. In particular, every forced move suggested by regular play is indeed forced, as Right is clearly threatening to win in one move.

• $\mathrm{■}$

  Now, we consider the case where regular play suggests a greedy move $d_j^r$ during step (4), which implies that $\text{ind}({\mathrm{\ell }}_j^r)=i$ and that Left has picked $v({\mathrm{\ell }}_j^r)$ during the current round $i$ of regular play. We have just shown that Left cannot win in one move, moreover Right is clearly not threatening to win in one move either. Therefore, to show that this is a valid greedy move as per Lemma 2, it suffices to show that the only edge (red or blue) containing $a_j^r$ in ${𝒢}^{\prime }$ is the blue edge $\{a_j^r,d_j^r\}$. This is immediate, as the only edge (red or blue) containing $a_j^r$ in $𝒢$ is the blue edge $\{v({\mathrm{\ell }}_j^r),a_j^r,d_j^r\}$.

• $\mathrm{■}$

  Finally, we consider the case where regular play suggests picking $x_i^{𝖳}$ or $x_i^{𝖥}$. In particular, this means that round $i$ of regular play is just starting, so Claim 5 applied to $i-1$ describes ${𝒢}^{\prime }$ exactly. Suppose that Left picks some $u\in V^{\prime }\setminus \{x_i^{𝖳},x_i^{𝖥}\}$ instead: we want to show that Right now has a drawing strategy. It is important to note that, by Claim 5, $\{x_i^{𝖳},x_i^{𝖥}\}$ is the only blue edge of size less than $3$ in ${𝒢}^{\prime }$, so that Right’s next move is not forced. In an ideal scenario, Right would like to do the following (not necessarily in that order):

  • –

    Kill all remaining blue guide-edges, by picking $x_k^{𝖳}$ and $x_k^{𝖥}$ for all $k\in ⟦i,n⟧$;

  • –

    Kill all remaining trap-edges, by picking $t_k$ or ${\tau }_k$ for all $k\in ⟦i,n⟧$;

  • –

    Kill all remaining link-edges, by picking every unpicked $d_j^r$;

  • –

    Kill all remaining butterfly-edges, by picking $b_j$ for all $j\in ⟦1,m⟧$.

  The idea is that all these vertices are in some intact red edge, so Right wants to pick all of them while forcing all of Left’s moves. However, the vertex $u$ that Left has just picked may be one of these vertices, or the forced move associated with one of these vertices. Therefore, Right must adapt her plan to the vertex $u$.

  1. (1)

     Case $u\in {\bigcup }_{1\le k\le n}(V_k\setminus \{x_k^{𝖳},x_k^{𝖥}\})$. Let $k_0\in ⟦1,n⟧$ (unique) such that $u\in V_{k_0}$.

     • –

       Right first kills all remaining trap-edges. If $u\in \{t_{k_0},s_{k_0},w_{k_0},w_{k_0}^{\prime }\}$, then Right picks ${\tau }_{k_0}$ (which forces Left to pick ${\delta }_{k_0}$). Otherwise, Right picks $t_{k_0}$ (which forces Left to pick $s_{k_0}$). This way, she makes sure that $u$ does not contribute to a threat with the blue guide-edges in $G_{k_0}^L$. Then, for all $k\in ⟦i,n⟧\setminus \left\{k_0\right\}$, she picks $t_k$ (which forces Left to pick $s_k$).

     • –

       Right then kills all remaining butterfly-edges, by picking $b_j$ (which forces Left to pick $d_j$) for all $j\in ⟦1,m⟧$.

     • –

       Right now kills all remaining link-edges, by picking every unpicked $d_j^r$ (which forces Left to pick $b_j^r)$.

     • –

       Finally, Right kills all remaining blue guide-edges. For all $k\in ⟦i,n⟧\setminus \left\{k_0\right\}$, she picks $x_k^{𝖳}$ then $x_k^{𝖥}$ (which forces Left to pick $w_k$ then $w_k^{\prime }$). Note that the move $x_k^{𝖥}$ was actually forced for Right because of the blue guide-edge $\{w_k,s_k,x_k^{𝖥}\}$. She does the same for $k_0$, except that she picks $x_{k_0}^{𝖥}$ first and $x_{k_0}^{𝖳}$ second if $u=w_{k_0}$. This way, the only move which does not force Left’s answer is played last, when all blue edges are already dead.

  2. (2)

     Case $u\in ({\bigcup }_{1\le j\le m}{C}_j)\setminus ({\bigcup }_{i\le k\le n}\{x_k^{𝖳},x_k^{𝖥},y_k^{𝖳},y_k^{𝖥}\})$. Let $j_0\in ⟦1,m⟧$ (unique) such that $u\in C_{j_0}$.

     • –

       Right first kills all remaining trap-edges, by picking $t_k$ (which forces Left to pick $s_k$) for all $k\in ⟦i,n⟧$.

     • –

       Right then kills all remaining blue guide-edges, by picking $x_k^{𝖳}$ then $x_k^{𝖥}$ (which forces Left to pick $w_k$ then $w_k^{\prime }$) for all $k\in ⟦i,n⟧$.

     • –

       Right now kills all remaining link-edges, by picking $y_k^{𝖳}$ and $y_k^{𝖥}$ (which forces Left to pick ${\omega }_k$ and ${\omega }_k^{\prime }$ respectively) for all $k\in ⟦i,n⟧$.

     • –

       Finally, Right kills all remaining butterfly-edges. For this, she starts by picking $b_j$ (which forces Left to pick $d_j$) for all $j\in ⟦1,m⟧\setminus \left\{j_0\right\}$. If $u\ne b_{j_0}$, then Right simply picks $b_{j_0}$ next to kill the last butterfly-edges. If $u=b_{j_0}$, then we use the assumption made at the beginning of the proof of this claim: one of $v({\mathrm{\ell }}_{j_0}^1)$, $v({\mathrm{\ell }}_{j_0}^2)$ or $v({\mathrm{\ell }}_{j_0}^3)$ has not been picked by Left. By Claim 5, this means that one of the destruction-edges $\{b_{j_0}^1,d_{j_0}^1\}$, $\{b_{j_0}^2,d_{j_0}^2\}$ and $\{b_{j_0}^3,d_{j_0}^3\}$ is intact, or that one of the butterfly-edges $\{b_{j_0},b_{j_0}^1,b_{j_0}^2\}$ and $\{b_{j_0},b_{j_0}^2,b_{j_0}^3\}$ is dead. As we have seen in the proof of Claim 6, this allows Right to hold on to a draw.

  3. (3)

     Case $u\in {\bigcup }_{i+1\le k\le n}\{x_k^{𝖳},x_k^{𝖥}\}$. By symmetry, assume $u=x_{k_0}^{𝖳}$ for some $k_0\in ⟦i+1,n⟧$.

     • –

       Right first kills all remaining butterfly-edges, by picking $b_j$ (which forces Left to pick $d_j$) for all $j\in ⟦1,m⟧$. Left never threatens to win in one move with a trap-edge during the process, as $t_k$ and ${\tau }_k$ are both unpicked for all $k\in ⟦i,n⟧$.

     • –

       Right then kills all remaining link-edges, by picking every unpicked $d_j^r$ (which forces Left to pick $b_j^r$). Again, the trap-edges are not an issue.

     • –

       Right now kills all remaining blue guide-edges in $G_k^L$ and trap-edges in $T_k$ for all $k\in ⟦i,n⟧\setminus \left\{k_0\right\}$, by picking $x_k^{𝖳}$, $x_k^{𝖥}$ then $t_k$ (which forces Left to pick $w_k$, $w_k^{\prime }$ then $s_k$ respectively). Note that, since Right has now picked $x_{k_0-1}^{𝖳}$ and $x_{k_0-1}^{𝖥}$, the blue guide-edges $\{x_{k_0}^{𝖳},x_{k_0}^{𝖥},x_{k_0-1}^{𝖳}\}$ and $\{x_{k_0}^{𝖳},x_{k_0}^{𝖥},x_{k_0-1}^{𝖥}\}$ are dead. Therefore, the updated variable gadget associated with $x_{k_0}$ and $y_{k_0}$ is as pictured in Figure 7. The blue edge $\{t_{k_0},{\tau }_{k_0}\}$ comes from trap-edges in $T_{k_0}$ (for example, think of any trap-edge of the form $\{t_{k_0},{\tau }_{k_0},d_j\}$, since Left has picked $d_j$ while Right was killing the butterfly-edges).

       

     • –

       Finally, Right kills all remaining blue guide-edges in $G_{k_0}^L$ and trap-edges in $T_{k_0}$. She plays the following moves, which kill all remaining blue edges apart from the updated blue edge $\{w_{k_0},s_{k_0}\}$:

       Right picks $w_{k_0}$ or $s_{k_0}$ with her next move to finish the job.