Proof. The reduction from (a) to (b) is trivial since hypergraphs are special cases of marked hypergraphs. For the reduction from (b) to (c), let \(H\) be a marked hypergraph of rank \(k\) and define the \(k\)-uniform marked hypergraph \(H_0\) obtained from \(H\) as follows: for each edge \(e\) of \(H\), we create \(k-|e|\) new marked vertices, and we add them to \(e\). It is clear that \(H\) is a Maker win if and only if \(H_0\) is a Maker win. For the reduction from (c) to (a), we reverse this idea. Let \(H\) be a \(k\)-uniform marked hypergraph, and let \(H_0\) be the hypergraph of rank \(k\) obtained from \(H\) by removing all marked vertices and replacing each edge \(e\) of \(H\) by \(e \setminus M(H)\). It is clear that \(H\) is a Maker win if and only if \(H_0\) is a Maker win. ◻

Proof. Let \(P \in \{\text{Maker},\text{Breaker}\}\) be the player who has a winning strategy \(\Sigma\) on \(H\). We design the following strategy for \(P\) when playing on \(H_0\). \(P\) follows the strategy \(\Sigma\), except when the opponent picks \(a\) (resp. \(b\)) in which case \(P\) answers by picking \(b\) (resp. \(a\)). It can happen that \(a\) and \(b\) are the only non-marked vertices left, in which case \(P\) picks one arbitrarily and the opponent has to pick the other. In all cases, Maker and Breaker share the vertices \(a\) and \(b\). Therefore, for each \(e \in F\), the vertices of \(e\) all end up marked if and only if the vertices of either \(e_a\) or \(e_b\) all end up marked. Since all the other edges are common to both \(H\) and \(H_0\), we can conclude that an edge of \(H_0\) ends up with all its vertices marked if and only if some edge of \(H\) does. All in all, this strategy is indeed winning for \(P\) on \(H_0\) since \(\Sigma\) is on \(H\). ◻

Proof. This is essentially the famous "strategy-stealing" argument [4]. Suppose Maker has a strategy \(\Sigma\) to win within \(t\) rounds on \(H\). Playing on \(H^{+x}\), in which \(x\) is an "extra" (i.e., an extra marked vertex compared to \(H\)), Maker follows the strategy \(\Sigma\). At some point, she will be instructed to pick the extra, which she cannot do as it is already marked in reality: instead, she picks an arbitrary non-marked vertex, which becomes the new extra. Continuing so, all throughout the game, the marked vertices are a superset of what they would be if the game was played on \(H\): it is the same set plus the extra. Therefore, within the first \(t\) rounds, some edge will be fully marked. ◻

Proof. Suppose Maker has a strategy \(\Sigma\) to win in at most \(t\) rounds on \(X\). Playing on \(H\), Maker simply makes all her picks inside \(X\), following the strategy \(\Sigma\). Whenever Breaker picks a vertex outside \(X\), Maker pretends that Breaker has picked some arbitrary non-marked \(y \in V(X)\) instead, so as to get a normal game on \(X\) (i.e., a game with alternating turns). Maker will get a fully marked edge of \(X\) in at most \(t\) rounds, as she cannot win any later than she would have if Breaker had actually made all his picks inside \(X\). ◻

Proof. Suppose that Maker picks \(x \in V(H) \setminus M(H)\) such that \(I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}(H)}\right) = \varnothing\). We must show that, no matter what vertex \(y \in V(H^{+x}) \setminus M(H^{+x})\) Breaker picks as an answer, \(H^{+x-y}\) is a Maker win. Since \(y \not\in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}(H)}\right)\), there exists \(D \in x\mathcal{D}(H)\) such that \(y \not\in V(D)\). Therefore, \(D^{+x}\) is a subhypergraph of \(H^{+x-y}\), and it is a Maker win by definition of a danger at \(x\). By Proposition [prop95subwin] (Subhypergraph Monotonicity), \(H^{+x-y}\) is a Maker win, which concludes. ◻

Proof. The first property comes from the fact that \(x\mathcal{D}'(H) \subseteq x\mathcal{D}(H)\) hence \(I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}(H)}\right) \subseteq I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}'(H)}\right)\). Let us now prove the second property. Suppose \(J(\mathcal{D},H)\) holds. Let \(x \in V(X)\setminus M(X)\): we want to show that there exists \(y \in I_{X^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}(X)}\right)\). By \(J(\mathcal{D},H)\), there exists \(y' \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}(H)}\right)\). If \(y' \in V(X)\), then \(y = y'\) is suitable since \(x\mathcal{D}(X) \subseteq x\mathcal{D}(H)\). If \(y' \not\in V(X)\), then in particular \(x\mathcal{D}(X)=\varnothing\) (indeed, if there existed \(D_0 \in x\mathcal{D}(X) \subseteq x\mathcal{D}(H)\), then we would have \(y' \in V(D_0) \subseteq V(X)\)), therefore any \(y \in V(X^{+x})\setminus M(X^{+x})\) is suitable. ◻

Proof. The "only if" direction is given by Proposition [prop95cn], so we show the "if" direction. Suppose \(J(\mathcal{D}_{\mathrm{all}},H)\) holds. Maker picks some \(x \in V(H) \setminus M(H)\), and we must show that there exists an answer \(y \in V(H^{+x}) \setminus M(H^{+x})\) by Breaker such that \(H^{+x-y}\) is a Breaker win. Breaker may pick any \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_{\mathrm{all}}(H)}\right)\). Since \(y \not\in V(H^{-y})\), we have \(H^{-y} \not\in x\mathcal{D}_{\mathrm{all}}(H)\), i.e., \(H^{-y}\) is not a danger at \(x\) in \(H\). By definition of a danger at \(x\), this means \((H^{-y})^{+x}\) is a Breaker win, which concludes since \((H^{-y})^{+x}=H^{+x-y}\). ◻

Proof. Since \(H\) is 2-uniform, the fact that \(H\) is not a trivial Maker win exactly means that \(M(H)=\varnothing\), i.e., \(H\) is a graph. Also note that a \(\mathcal{D}_{\mathrm{triv}}\)-danger at a vertex \(x\) is nothing but an edge of the graph that is incident to \(x\). The property \(J(\mathcal{D}_{\mathrm{triv}},H)\), which by definition signifies the absence of any \(\mathcal{D}_{\mathrm{triv}}\)-fork in the graph \(H\), is therefore equivalent to \(H\) having maximum degree at most 1. This obviously characterizes graphs that are a Maker win: if \(H\) has a vertex \(x\) of degree at least 2, then Maker starts by picking \(x\) and wins in the next round, otherwise Breaker wins by always picking the only neighbor of the vertex Maker has just picked (or an arbitrary vertex if that neighbor is already marked or does not exist). ◻

Proof. Let \((D,x_0) \in \mathcal{D}_1\). We want to show that \(D^{+x_0}\) is a Maker win. This comes from the fact that we are in one of the two situations pictured on the right of Figure 8. As we have just seen, when playing on \(D^{+x_0}\), Maker can pick \(x_1,\ldots,x_{i-1}\) successively (which forces Breaker to pick \(y_1,\ldots,y_{i-1}\) successively in the meantime), then pick \(x_i\) and win in the next round by picking whichever of \(y_i\) or \(u\) has not been picked by Breaker. ◻

Proof. Let \((D,x) \in \widehat{\mathcal{D}_1}\), with a decomposition \((z , \mathcal{F}_D = \mathcal{S}_z \cup \mathcal{T}_z \cup \mathcal{P}_{zx})\). Since \(D = \langle \mathcal{F}_D \rangle\), we know \(\mathcal{F}_D \neq \varnothing\): let \(X \in \mathcal{F}_D\), and let \(e \in E(X)\). By definition, every element of \(\mathcal{F}_D\) has at most one marked vertex, so \(|M(e)|\leq 1\). Moreover, by item [item95chapeau2] of the definition of \(\widehat{\mathcal{D}_1}\), \(e\) cannot contain both \(x\) and a marked vertex, because \(e\) would otherwise constitute a \(\mathcal{D}_1\)-danger at \(x\) (\(x\)-snake of length 1). Therefore, \(|e \setminus (M(e) \cup \{x\})| \geq 2\), from which \(|V(D^{+x}) \setminus M(D^{+x})| \geq 2\). Now, since \(\mathcal{F}_D^{+x}\) is a \(\mathcal{D}_1\)-fork at \(z\) in \(D^{+x}\), property \(J(\mathcal{D}_1,D^{+x})\) does not hold. Therefore, \(D^{+x}\) is a Maker win, i.e., \((D,x)\) is a danger. ◻

Proof. Let us first show that (b) \(\implies\) (a). Suppose for a contradiction that \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_1(H)}\right)\) and that \(J(\mathcal{D}_1,H^{+x-y})\) holds, but \(y \not\in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H)}\right)\). Then there exists \(D \in x\widehat{\mathcal{D}_1}(H)\) such that \(y \not\in V(D)\). This means \(D^{+x}\) is a subhypergraph of \(H^{+x-y}\). As a consequence, since \(J(\mathcal{D}_1,H^{+x-y})\) holds, \(J(\mathcal{D}_1,D^{+x})\) must hold as well. This contradicts Proposition [prop95D1chapeau].
Now, let us show that (a) \(\implies\) (b). Suppose that \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H)}\right)\). Since \(\mathcal{D}_1 \subseteq \mathcal{D}_2\), this obviously implies \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_1(H)}\right)\), but suppose for a contradiction that \(J(\mathcal{D}_1,H^{+x-y})\) does not hold. This means there exists a \(\mathcal{D}_1\)-fork \(\mathcal{F}\) at some \(z \in V(H^{+x-y}) \setminus M(H^{+x-y})\) in \(H^{+x-y}\). We define the partition \(\mathcal{F}= \mathcal{S}_z \cup \mathcal{T}_z \cup \mathcal{S}_{zx}\) as follows:

• The collection \(\mathcal{S}_z\) (resp. \(\mathcal{T}_z\)) contains all \(X \in \mathcal{F}\) such that \(X\) is a \(z\)-snake (resp. a \(z\)-tadpole) and \(x \not\in V(X)\). The elements of \(\mathcal{S}_z \cup \mathcal{T}_z\) are "old" \(\mathcal{D}_1\)-dangers at \(z\), i.e., ones that were already present in \(H\).

• The collection \(\mathcal{S}_{zx}\) contains all \(X \in \mathcal{F}\) such that \(x \in V(X)\). Since \(x\) is marked in \(H^{+x-y}\) (from which the collection \(\mathcal{F}\) is taken), every \(X \in \mathcal{S}_{zx}\) is necessarily a \(zx\)-snake with \(M(X)=\{x\}\). The elements of \(\mathcal{S}_{zx}\) are "new" \(\mathcal{D}_1\)-dangers at \(z\), i.e., ones that did not exist in \(H\). We assume that \(\mathcal{S}_{zx} \neq \varnothing\), as \(\mathcal{F}\) would otherwise be a \(\mathcal{D}_1\)-fork at \(z\) in \(H\), contradicting the fact that \(J(\mathcal{D}_1,H)\) holds (this is the only moment where this assumption is used in this proof).

Let \(\mathcal{P}_{zx}\) be the collection of all \(zx\)-chains in \(H\) that the elements of \(\mathcal{S}_{zx}\) come from, i.e., the collection with the same elements as \(\mathcal{S}_{zx}\) except that \(x\) is non-marked in all of them. Let \(D=\langle \mathcal{F}_D \rangle\), where \(\mathcal{F}_D = \mathcal{S}_z \cup \mathcal{T}_z \cup \mathcal{P}_{zx}\). Note that \(x \in V(D)\) since \(\mathcal{P}_{zx} \neq \varnothing\). On the other hand, since all elements of \(\mathcal{F}\) are subhypergraphs of \(H^{+x-y}\), we know all elements of \(\mathcal{F}_D\) are subhypergraphs of \(H^{-y}\), so \(y \not\in V(D)\). Let us verify that \((D,x) \in \widehat{\mathcal{D}_1}\), with decomposition \((z,\mathcal{F}_D)\). For item [item95chapeau1], all that is left to check is that \(\mathcal{F}_D^{+x}\) is a \(\mathcal{D}_1\)-fork at \(z\) in \(D^{+x}\): since \(\mathcal{F}_D^{+x} = \mathcal{F}\) and \(D^{+x} \subseteq H^{+x-y}\), this immediately follows from the fact that \(\mathcal{F}\) is a \(\mathcal{D}_1\)-fork at \(z\) in \(H^{+x-y}\). As for item [item95chapeau2], it is impossible that \(D\) contains a \(\mathcal{D}_1\)-danger at \(x\) since \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_1(H)}\right)\) and \(y \not\in V(D)\). All in all, items [item95chapeau1] and [item95chapeau2] are both satisfied, so \((D,x) \in \widehat{\mathcal{D}_1}\). This contradicts the fact that \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H)}\right)\) and \(y \not\in V(D)\). ◻

Proof. Let \(\alpha \in \{1,2\}\), and suppose \(J(\mathcal{D}_{\alpha},H)\) does not hold. Maker picks \(x_1\) such that \(I_{H^{+x_1}}\mathopen{}\mathclose{\left(x_1\mathcal{D}_{\alpha}(H)}\right)=\varnothing\), and Breaker picks \(y_1\), so that the updated marked hypergraph after one round of play is \(H^{+x_1-y_1}\). Since \(I_{H^{+x_1}}\mathopen{}\mathclose{\left(x_1\mathcal{D}_{\alpha}(H)}\right)=\varnothing\), there exists some \(D \in x_1\mathcal{D}_{\alpha}(H)\) such that \(y_1 \not\in V(D)\).

• Case 1: \(D\) is an \(x_1\)-snake (resp. an \(x_1\)-cycle). Then, \(D^{+x_1}\) is a nunchaku (resp. a necklace) in \(H^{+x_1-y_1}\), which concludes.

• Case 2: \(D=T\) is an \(x_1\)-tadpole that is not a cycle. Then, let \(x_2\) be the only vertex in \(V(P_T) \cap V(C_T)\). Maker picks \(x_2\), and Breaker picks some \(y_2\), so that the updated marked hypergraph after two rounds of play is \(H^{+x_1-y_1+x_2-y_2}\). Either \(y_2 \not\in V(P_T)\), in which case \(P_T^{+x_1+x_2}\) is a nunchaku in \(H^{+x_1-y_1+x_2-y_2}\), or \(y_2 \not\in V(C_T)\), in which case \(C_T^{+x_2}\) is a necklace in \(H^{+x_1-y_1+x_2-y_2}\). This concludes.

• Case 3 (which can only happen if \(\alpha=2\)): \((D,x_1) \in \widehat{D_1}\) with a maximal decomposition \((x_2,\mathcal{F}_D)\). Then \(\mathcal{F}_D^{+x_1}\) is a \(\mathcal{D}_1\)-fork at \(x_2\) in \(H^{+x_1-y_1}\). Maker picks \(x_2\), and Breaker picks some \(y_2\). By definition of a \(\mathcal{D}_1\)-fork, there exists \(D' \in x_2\mathcal{D}_1(H^{+x_1-y_1})\) such that \(y_2 \not\in V(D')\). If \(D'\) is an \(x_2\)-snake (resp. an \(x_2\)-cycle), then we get a nunchaku (resp. a necklace) in \(H^{+x_1-y_1+x_2-y_2}\) like in Case 1. If \(D'=T\) is an \(x_2\)-tadpole, then Maker picks the only vertex \(x_3\) in \(V(P_T) \cap V(C_T)\) like in Case 2, and we get a nunchaku or a necklace in \(H^{+x_1-y_1+x_2-y_2+x_3-y_3}\) whatever Breaker’s pick \(y_3\).

 ◻

Proof. Let \(a,b\) be such that \(P\) is an \(ab\)-chain, and write \(\overrightarrow{aPb}=(a,e_1,\ldots,e_L,b)\).

• Firstly, suppose \(u=v\). Then that single vertex forms the only \(uv\)-chain in \(P\).

• Secondly, suppose \(u \neq v\) and there exists some \(1 \leq i \leq L\) such that \(\{u,v\}\subseteq e_i\) (note that \(i\) is unique since two distinct edges of a chain cannot intersect on two vertices). Then \((u,e_i,v)\) represents a \(uv\)-chain. Moreover, if some walk \(\overrightarrow{W'}\) represents a \(uv\)-chain in \(P\), then we have \(u \in \mathrm{start}(\overrightarrow{W'})\) and \(v \in \mathrm{end}(\overrightarrow{W'})\), so \(\mathrm{start}(\overrightarrow{W'})=\mathrm{end}(\overrightarrow{W'})=e_i\) hence the uniqueness.

• Finally, suppose \(u \neq v\) and no edge of \(P\) contains both \(u\) and \(v\). For \(x \in \{u,v\}\), define \(j(x)=\min\{1 \leq i \leq L \mid x \in e_i\}\) and \(j'(x)=\max\{1 \leq i \leq L \mid x \in e_i\}\): note that \(j'(x)=j(x)+1\) if \(x \in \mathrm{inn}(P)\) and \(j'(x)=j(x)\) otherwise. Up to swapping the roles of \(u\) and \(v\), assume \(j(u) \leq j(v)\): we actually have \(j(u) < j(v)\), otherwise \(e_{j(u)}=e_{j(v)}\) would contain both \(u\) and \(v\). Since \(j'(u) \in \{j(u),j(u)+1\}\), this yields \(j'(u) \leq j(v)\) hence \(j'(u) < j(v)\) for the same reason. We define \(\overrightarrow{W}= (u,e_{j'(u)},e_{j'(u)+1},\ldots,e_{j(v)},v)\), and we claim that \(\overrightarrow{W}\) is a walk that represents a \(uv\)-chain. Indeed:

  • The fact that \(\overrightarrow{aPb}\) is a linear walk by definition of a chain, coupled with the fact that \(u \in e_{j'(u)}\) and \(v \in e_{j(v)}\), implies that \(\overrightarrow{W}\) is a linear walk.

  • The fact that the walk \(\overrightarrow{aPb}\) is simple by definition of a chain, coupled with the maximality of \(j'(u)\) and the minimality of \(j(v)\), implies that \(\overrightarrow{W}\) is also simple.

  Let us now address uniqueness. Let \(\overrightarrow{W'}= (u,e_{i_1},e_{i_2},\ldots,e_{i_t},v)\) be a walk representing a \(uv\)-chain in \(P\), where \(i_1,\ldots,i_t\) are pairwise distinct indices in \(\{1,\ldots,L\}\). Since \(u \in e_{i_1}\) and \(v \in e_{i_t}\), we have \(i_1 \in \{j(u),j'(u)\}\) and \(i_t \in \{j(v),j'(v)\}\). We have seen that \(j'(u)<j(v)\), so \(i_1<i_t\). For all \(1 \leq s \leq t-1\), we have \(|e_{i_s} \cap e_{i_{s+1}}|=1\) by definition of a chain hence \(|i_s-i_{s+1}|=1\). Since \(i_1<i_t\) and the indices \(i_1,\ldots,i_t\) are pairwise distinct, this implies \(i_{s+1}=i_s+1\) for all \(1 \leq s \leq t-1\). To conclude that \(\overrightarrow{W'}=\overrightarrow{W}\), it only remains to show that \(i_1=j'(u)\) and \(i_t=j(v)\). We have mentioned that \(i_1 \in \{j(u),j'(u)\}\): if \(i_1=j(u)=j'(u)-1\), then \(e_{i_2}=e_{j'(u)} \ni u\), hence a repetition in \(\overrightarrow{W'}\) which contradicts the definition of a chain. Therefore \(i_1=j'(u)\), and an analogous reasoning yields \(i_t=j(v)\).

 ◻

Proof. Let us first address the case where \(C\) is of length 2. If \(w \in \mathrm{out}(C)\), then write \(E(C)=\{\{w_1,w,w_2\},\{w_1,u,w_2\}\}\): \(C^{-w}\) consists of the edge \(\{w_1,u,w_2\}\), which forms a \(w_1w_2\)-chain. If \(w \in \mathrm{inn}(C)\), then write \(E(C)=\{\{w,u_1,w_1\},\{w,u_2,w_1\}\}\): \(C^{-w}\) consist of the three isolated vertices \(w_1=w_2\), \(u_1\) and \(u_2\).
Now assume that \(C\) is of length at least 3. Let \(e\) be the edge of \(C\) containing both \(w\) and \(w_1\), and write \(\overrightarrow{(w_1-e)C}=(w_1,e=e_1,e_2\ldots,e_L,w_1)\). We have \(e_1 \cap e_L = \{w_1\}\). If \(w \in \mathrm{out}(C)\), then \(e_1=\{w_1,w,w_2\}\) so \(e_1 \cap e_2=\{w_2\}\). If \(w \in \mathrm{inn}(C)\), then \(e_1 \cap e_2=\{w\}\) hence \(e_2 \cap e_3 = \{w_2\}\) since \(w_2\) is adjacent to \(w\). Therefore, defining \(i=2\) if \(w \in \mathrm{out}(C)\) and \(i=3\) if \(w \in \mathrm{inn}(C)\), the only edges of \(C\) containing \(w_2\) are \(e_{i-1}\) and \(e_i\). We define \(\overrightarrow{W}=(w_2,e_i,\ldots,e_L,w_1)\), and we claim that \(\overrightarrow{W}\) is a linear simple walk. Indeed:

• By definition of a cycle, the walk \(\overrightarrow{(w_1-e)C}\) is linear since \(C\) is of length at least 3, and \(w_1\) is its only repeated vertex with \(\{1 \leq i \leq L, w_1 \in e_i\}=\{1,L\}\). Therefore, its subsequence \((e_i,\ldots,e_L,w_1)\) is also a linear walk, and has no repeated vertices since it does not contain the edge \(e_1\).

• The addition of \(w_2\) at the start of \((e_i,\ldots,e_L,w_1)\) preserves the fact that it is a linear walk since \(w_2 \in e_i\), and also preserves the absence of any repeated vertex since \(w_2 \not\in e_j\) for all \(j>i\).

Therefore, by definition, \(\overrightarrow{W}\) represents a \(w_2w_1\)-chain. We can now conclude:

• If \(w \in \mathrm{out}(C)\), then \(V(C^{-w}) = V(C) \setminus \{w\} = e_2 \cup \ldots \cup e_L = V(\overrightarrow{W})\) and \(E(C^{-w}) = E(C) \setminus \{e_1\} =\{e_2,\ldots,e_L\}=E(\overrightarrow{W})\), so \(C^{-w}\) is the \(w_1w_2\)-chain represented by \(\overrightarrow{W}\).

• If \(w \in \mathrm{inn}(C)\), then let \(u_1\) and \(u_2\) be the outer vertices of \(C\) in \(e_1\) and \(e_2\) respectively: we have \(V(C^{-w}) = V(C) \setminus \{w\} = (e_3 \cup \ldots \cup e_L) \cup \{u_1,u_2\} = V(\overrightarrow{W}) \cup \{u_1,u_2\}\) and \(E(C^{-w}) = E(C) \setminus \{e_1,e_2\} =\{e_3,\ldots,e_L\}=E(\overrightarrow{W})\), so \(C^{-w}\) is the union of the \(w_1w_2\)-chain represented by \(\overrightarrow{W}\) and the two isolated vertices \(u_1\) and \(u_2\).

 ◻

Proof. First of all, note that a \(uv\)-chain in \(C\) that does not contain \(w\) is exactly a \(uv\)-chain in \(C^{-w}\). Assume \(u \neq v\), otherwise the result is trivial. If \(w \in \mathrm{out}(C)\), then \(C^{-w}\) is a chain according to Substructure Lemma [lemma95subchain2], which contains a unique \(uv\)-chain by Substructure Lemma [lemma95subchain1]. Now assume \(w \in \mathrm{inn}(C)\): then \(C^{-w}\) is the union of a chain \(P\) and two isolated vertices \(u_1,u_2\) that are the two outer vertices of \(C\) adjacent to \(w\) according to Substructure Lemma [lemma95subchain2]. If \(u \in \{u_1,u_2\}\) or \(v \in \{u_1,u_2\}\), then there obviously cannot exist a \(uv\)-chain in \(C^{-w}\). Otherwise \(u,v \in V(P)\), so there exists a unique \(uv\)-chain in \(P\) (and in \(C^{-w}\) as a result) by Substructure Lemma [lemma95subchain1]. ◻

Proof. If \(C\) is of length 2 and \(\mathrm{out}(C)=\{u,v\}\), then there are no \(uv\)-chains in \(C\), because \(|e_u \cap e_v|=2\) where \(e_u\) (resp. \(e_v\)) denotes the only edge of \(C\) containing \(u\) (resp. \(v\)). Otherwise, there exists \(w \in \mathrm{out}(C) \setminus \{u,v\}\): by Substructure Lemma [lemma95subchain3], there exists a unique \(uv\)-chain in \(C\) that does not contain \(w\), so in particular \(C\) contains a \(uv\)-chain. ◻

Proof. Note that \(w \not\in V(P_T)\), so that Substructure Lemma [lemma95subchain1] concludes if \(u,v \in V(P_T)\). If \(u,v \in V(C_T)\), then Substructure Lemma [lemma95subchain3] concludes. Therefore, assume \(u \in V(P_T)\) and \(v \in V(C_T)\). Let \(b\) be the only vertex in \(V(P_T) \cap V(C_T)\). By Substructure Lemma [lemma95subchain1], there exists a \(ub\)-chain \(P_{ub}\) in \(P_T\), that does not contain \(w\) since \(w \not\in V(P_T)\). By Substructure Lemma [lemma95subchain3], there exists a \(bv\)-chain \(P_{bv}\) in \(C_T\) that does not contain \(w\). Since \(V(P_{ub}) \cap V(P_{bv})=\{b\}\), it is clear that \(\overrightarrow{uP_{ub}b} \oplus \overrightarrow{bP_{bv}v}\) represents a \(uv\)-chain in \(T\) that does not contain \(w\). ◻

Proof. If \(C_T\) is of length 2 and \(\mathrm{out}(C_T)=\{u,v\}\), then there are no \(uv\)-chains in \(T\), because \(|e_u \cap e_v|=2\) where \(e_u\) (resp. \(e_v\)) denotes the only edge of \(T\) containing \(u\) (resp. \(v\)). Otherwise, there exists \(w \in \mathrm{out}(C) \setminus \{u,v\}\): by Substructure Lemma [lemma95subchain4], there exists a \(uv\)-chain in \(T\) that does not contain \(w\), so in particular \(T\) contains a \(uv\)-chain. ◻

Proof. Let \(b\) be the only vertex in \(V(P_T) \cap V(C_T)\). Since \(u \not\in \mathrm{out}(C_T)\), we have \(u \in \mathrm{inn}(C_T)\) or \(u \in V(P_T)\). If \(u \in \mathrm{inn}(C_T)\), then \(C_T\) is a \(u\)-cycle (recall that a \(u\)-cycle is a particular case of a \(u\)-tadpole). If \(u \in V(P_T)\), then there exists a \(ub\)-chain \(P_{ub}\) in \(P_T\) by Substructure Lemma [lemma95subchain1], so \(\overrightarrow{uP_{ub}b} \oplus \overrightarrow{bC_T}\) represents a \(u\)-tadpole. ◻

Proof. Let us start by showing the existence of \(z \in Z \cap V(X)\) such that there exists a \(uz\)-chain in \(X\). If \(X\) is a chain, then any \(z \in Z \cap V(X)\) is suitable by Substructure Lemma [lemma95subchain1]. If \(X\) is a tadpole, then any \(z \in Z \cap V(X)\) is suitable by Substructure Lemma [lemma95subchain4bis], unless \(C_X\) is of length 2 and \(u \in \mathrm{out}(C_X)\) in which case we choose \(z \in Z \cap V(X) \setminus (\mathrm{out}(C_X) \setminus \{u\})\) as allowed by the assumption.
Let \(z \in Z \cap V(X)\) minimizing the length of a shortest \(uz\)-chain in \(X\), and let \(P\) be a shortest \(uz\)-chain in \(X\). We define \(\mathbf{P}_{Z}(u,X) = P\), which we now prove has the desired properties. Clearly, \(P\) is of positive length if and only if \(u \not\in Z\). Assume \(u \not\in Z\). Consider the walk \(\overrightarrow{uP}\vert_Z\): recall that, as per Notation [notation95walk], this is the walk \(\overrightarrow{uP}\) “cut” at the first edge that intersects \(Z\). In particular, the only edge of \(\overrightarrow{uP}\vert_Z\) that intersects \(Z\) is \(\mathrm{end}(\overrightarrow{uP}\vert_Z)\), so \(|\mathrm{end}(\overrightarrow{uP}\vert_Z) \cap Z| \in \{1,2\}\). Therefore, it suffices to show that \(\overrightarrow{uP}\vert_Z=\overrightarrow{uP}\) to finish the proof. Let \(z' \in \mathrm{end}(\overrightarrow{uP}\vert_Z)\). The walk \(\overrightarrow{uP}\vert_Z\) induces a \(uz'\)-chain, which cannot be shorter than \(P\) by minimality of \(z\), hence why \(\overrightarrow{uP}\vert_Z=\overrightarrow{uP}\). ◻

Proof. By definition of a projection, we have \(|e^* \cap V(P_{ab})|\in \{1,2\}\). Let \(u \in e^* \setminus V(P_{ab})\). All ways that \(e^*\) might intersect \(P_{ab}\) are summarized in Tables 1 and 2. There are no \(au\)-chains \(P_{au}\) in \(P_{ab} \cup e^*\), otherwise the walk \(\overrightarrow{cP_c}\vert_{\{u\}} \oplus \overrightarrow{uP_{au}a}\) would represent a \(ca\)-chain in \(P_{ab} \cup P_c\), contradicting the assumption of the lemma. Therefore, we are necessarily in the bottom-left case of Table 2, which means that: \(|e^* \cap V(P_{ab})|=2\), \(e^* \perp \overrightarrow{aPb}\), there is a \(b\)-tadpole in \(P_{ab} \cup e^*\), and there is a \(bu\)-chain \(P_{bu}\) in \(P_{ab} \cup e^*\). The walk \(\overrightarrow{cP_c}\vert_{\{u\}} \oplus \overrightarrow{uP_{bu}b}\) represents a \(cb\)-chain in \(P_{ab} \cup P_c\). ◻

Proof. The second item is exactly Union Lemma [Lemma1]. The first item is Union Lemma [Lemma1] where the roles of \(a\) and \(b\) are reversed. ◻

Proof. We distinguish between two cases:

• First suppose \(a \in e^*\). Since \(e^* \neq \mathrm{start}(\overrightarrow{aP_{ab}b})\), all ways that \(e^*\) might intersect \(P_{ab}\) are summarized in Tables 3 and 4. Since there are no \(a\)-cycles in \(P_{ab} \cup P_a \supseteq P_{ab} \cup e^*\) by assumption, we are necessarily in the bottom-left case of Table 4, so \(e^* \perp \overrightarrow{aPb}\) and there is a \(b\)-tadpole in \(P_{ab} \cup e^*\).

• Now suppose \(a \not\in e^*\), meaning the projection \(\mathbf{P}_{V(P_{ab}) \setminus \{a\}}(a,P_a)\) is of length at least 2. Write \(\mathrm{start}(\overrightarrow{aP_a})=\{a,c,c'\}\) where \(c \in \mathrm{inn}(P_a)\), as in Figure 20. Define the \(c\)-chain \(P_c = P_a^{-a-c'}\): we have \(c \not\in V(P_{ab})\) and \(e^* = \mathrm{end}(\overrightarrow{c\mathbf{P}_{V(P_{ab})}(c,P_c)})\), so the idea is to apply Union Lemma [Lemma1] to \(P_{ab}\) and \(P_c\). If there was a \(ca\)-chain \(P_{ca}\) in \(P_{ab} \cup P_c\), then \((a,\mathrm{start}(\overrightarrow{aP_a}),c) \oplus \overrightarrow{cP_{ca}a}\) would represent an \(a\)-cycle in \(P_{ab} \cup P_a\), contradicting the assumption of the lemma. Therefore, there are no \(ca\)-chains in \(P_{ab} \cup P_c\), so Union Lemma [Lemma1] ensures that \(e^* \perp \overrightarrow{aPb}\) and that there is a \(b\)-tadpole in \(P_{ab} \cup e^*\).

 ◻

Proof. Up to replacing \(P_c\) by the projection \(\mathbf{P}_{V(T)}(c,P_c)\), assume that \(e^*\) is the only edge of \(P_c\) intersecting \(T\). Let \(b\) be the only vertex in \(V(P_T) \cap V(C_T)\).

Claim [claim95Lemma3] implies that \(V(P_T)\setminus \{a\} \neq \varnothing\), i.e., \(P_T\) is of positive length, i.e., \(T\) is not a cycle. It also implies that \(V(P_c) \cap V(P_T) \neq \varnothing\), so we can apply Union Lemma [Lemma1] with \(P_c\) and the \(ab\)-chain \(P_{ab}=P_T\). Since there are no \(ca\)-chains in \(T \cup P_c \supseteq P_T \cup P_c\) by assumption, Union Lemma [Lemma1] tells us that: \(|e^* \cap V(P_T)|=2\), \(e^* \perp \overrightarrow{aP_Tb}\), and there is a \(cb\)-chain \(P_{cb}\) in \(P_T \cup P_c\). Since \(|e^* \cap V(P_T)|=2\), we have \(e^* \cap (V(C_T) \setminus \{b\})=\varnothing\), hence \(V(P_{cb}) \cap V(C_T)=\{b\}\). Therefore \(P_{cb} \cup C_T\) is a \(c\)-tadpole in \(T \cup P_c\), which concludes. ◻

Proof. Let \(X\) be a \(u\)-snake or \(u\)-tadpole in \(H\). If \(M(X)=\varnothing\), then \(X\) is necessarily a \(u\)-tadpole, and \(X \in u\mathcal{D}_1(H)\). Therefore, assume that \(M(X) \neq \varnothing\), so that the \(u\)-snake \(S = \mathbf{P}_{M(X)}(u,X) \subseteq X\) is well defined. Note that we may have \(S \neq X\) even in the case where \(X\) is a snake, because the definition of a snake allows for extra marked vertices. By definition of a projection, the only edge of \(S\) that intersects \(M(X)\) is \(\mathrm{end}(\overrightarrow{uS})\). Moreover, since \(H\) is not a trivial Maker win, that edge contains exactly one marked vertex, hence \(|M(S)|=1\), i.e., \(S \in u\mathcal{D}_1(H)\).
The final assertion of this proposition ensues immediately: all \(u\)-snakes and \(u\)-tadpoles in \(H\) contain some \(D \in u\mathcal{D}_1(H)\), and \(u' \in V(D)\) since \(u' \in I_{H^{+u}}\mathopen{}\mathclose{\left(u\mathcal{D}_1(H)}\right)\). ◻

Proof. We prove the contrapositive. Suppose that there exists a subhypergraph \(X\) of \(H\) that is an \(m\)-snake or an \(m\)-tadpole for some \(m \in M(H)\).

• Case 1: \(M(X)=\{m\}\). In particular, \(X\) is necessarily a tadpole.

  • First suppose that \(X=C\) is a cycle. Let \(x \in \mathrm{inn}(C) \setminus \{m\}\): it is clear that \(C\) is the union of two \(xm\)-snakes \(S\) and \(S'\) such that \(M(S)=M(S')=\{m\}\) and \(V(S) \cap V(S')=\{x,m\}\) (the two "halves" of the cycle). Therefore, \(\{S,S'\}\) is a \(\mathcal{D}_0\)-fork at \(x\) in \(C \subseteq H\), so \(J(\mathcal{D}_0,H)\) does not hold and neither does \(J(\mathcal{D}_1,H)\).

  • Now, suppose that \(X=T\) is a tadpole which is not a cycle. Let \(x\) be the only vertex in \(V(P_T) \cap V(C_T)\). Since \(P_T\) is an \(xm\)-snake with \(M(P_T)=\{m\}\), and \(C_T\) is an \(x\)-cycle with \(M(C_T)=\varnothing\), we see that \(\{P_T,C_T\}\) is a \(\mathcal{D}_1\)-fork at \(x\) in \(T \subseteq H\), so \(J(\mathcal{D}_1,H)\) does not hold.

• Case 2: \(M(X) \setminus \{m\} \neq \varnothing\). The \(m\)-snake \(N = \mathbf{P}_{M(X) \setminus \{m\}}(m,X) \subseteq X\) is well defined. By definition of a projection, the only edge of \(N\) that intersects \(M(X) \setminus \{m\}\) is \(\mathrm{end}(\overrightarrow{mN})\). Moreover, since \(H\) is not a trivial Maker win, that edge contains exactly one marked vertex (call it \(m'\)), so \(N\) is an \(mm'\)-nunchaku of length at least 2. Let \(x \in \mathrm{inn}(N)\): it is clear that \(N\) is the union of an \(xm\)-snake \(S\) and an \(xm'\)-snake \(S'\) such that \(M(S)=\{m\}\), \(M(S')=\{m'\}\) and \(V(S) \cap V(S')=\{x\}\) (the two "halves" of the nunchaku). Therefore, \(\{S,S'\}\) is a \(\mathcal{D}_0\)-fork at \(x\) in \(N \subseteq H\), so \(J(\mathcal{D}_0,H)\) does not hold and neither does \(J(\mathcal{D}_1,H)\).

 ◻

Proof. Let us prove properties (a) through (f) in that order.

1. By definition of a decomposition, \(\mathcal{F}_D^{+x}\) is a \(\mathcal{D}_1\)-fork at \(z\) in \(D^{+x}\), i.e., \(I_{D^{+x}}\mathopen{}\mathclose{\left(\mathcal{F}_D^{+x}}\right)=\{z\}\). This implies that \(I_{D}\mathopen{}\mathclose{\left(\mathcal{F}_D}\right) \subseteq \{z,x\}\): in other words, apart from \(z\) and maybe \(x\), no non-marked vertex of \(D\) is contained in all elements of \(\mathcal{F}_D\).

2. By definition, each element of \(\mathcal{F}_D\) has at most one marked vertex, so \(D\) is not a trivial Maker win.

3. Thanks to property [item5], we can apply Proposition [prop95snakeinside] with \(H=D\) and \(u=x\). It ensures that \(D\) contains no \(x\)-snakes and no \(x\)-tadpoles, as it would otherwise contain a \(\mathcal{D}_1\)-danger at \(x\), contradicting the definition of \(\widehat{\mathcal{D}_1}\).

4. It is impossible that \(\mathcal{P}_{zx} = \varnothing\), because we would get \(D=\langle \mathcal{S}_z \cup \mathcal{T}_z \rangle\), contradicting the fact that \(D\) contains \(x\) while the subhypergraphs in the collection \(\mathcal{S}_z \cup \mathcal{T}_z\) do not.

Using property [item4], let \(P_{zx}\) be a shortest chain in \(\mathcal{P}_{zx}\), and define \(v = o(x,\overrightarrow{xP_{zx}z})\) and \(w = o(z,\overleftarrow{xP_{zx}z})\). This chain will help us prove properties [item3] and [item7]. Note that \(M(P_{zx})=\varnothing\) by definition of the collection \(\mathcal{P}_{zx}\).

5. Suppose for a contradiction that \(\mathcal{S}_z=\mathcal{T}_z=\varnothing\). By maximality of the decomposition, this exactly means that all \(\mathcal{D}_1\)-dangers at \(z\) in \(D\) contain \(x\). Also note that \(D=\langle \mathcal{P}_{zx} \rangle\), so \(M(D)=\varnothing\). We are going to use the chain \(P_{zx}\). By property [item2], there exists \(P^{\overline{v}} \in \mathcal{F}_D=\mathcal{P}_{zx}\) such that \(v \not\in V(P^{\overline{v}})\). We have \(\mathrm{start}(\overrightarrow{xP^{\overline{v}}z}) \neq \mathrm{start}(\overrightarrow{xP_{zx}z}) \ni v\) and \(V(P^{\overline{v}}) \cap (V(P_{zx}) \setminus \{x\}) \supseteq \{z\} \neq \varnothing\), so we can apply Union Lemma [Lemma2]: since \(P_{zx} \cup P^{\overline{v}} \subseteq D\) contains no \(x\)-cycles by property [item6], it contains a \(z\)-tadpole \(T\). If \(x \not\in V(T)\) as on the left of Figure 23, then \(T\) contradicts the fact that all \(\mathcal{D}_1\)-dangers at \(z\) in \(D\) contain \(x\). If \(x \in V(T)\), then the only possibility is that the projection \(\mathbf{P}_{V(P_{zx}) \setminus \{x\}}(x,P^{\overline{v}})\) consists of a single edge \(e\) as illustrated on the right of Figure 23: since \(v \not\in e\), we get a \(zx\)-chain \(P'_{zx}\) that is strictly shorter than \(P_{zx}\), also a contradiction.

   

6. We are going to use the chain \(P_{zx}\) again. By property [item2], there exists \(X^{\overline{w}} \in \mathcal{F}_D\) such that \(w \not\in V(X^{\overline{w}})\). We claim that \(V(X^{\overline{w}}) \cap (V(P_{zx}) \setminus \{z\}) \neq \varnothing\) in all cases, indeed:

   • If \(X^{\overline{w}} \in \mathcal{P}_{zx}\), then this is obvious because \(x \in V(X^{\overline{w}})\).

   • If \(X^{\overline{w}} \in \mathcal{T}_z\), then this is true because otherwise \(P_{zx} \cup X^{\overline{w}}\) would be an \(x\)-tadpole in \(D\), contradicting property [item6].

   • If \(X^{\overline{w}} \in \mathcal{S}_z\), then this is true because otherwise \(P_{zx} \cup X^{\overline{w}}\) would be an \(x\)-snake in \(D\), contradicting property [item6].

   Therefore, the projection \(P = \mathbf{P}_{V(P_{zx}) \setminus \{z\}}(z,X^{\overline{w}})\) is well defined. Since \(w \not\in V(P)\) and \(w \in \mathrm{start}(\overleftarrow{xP_{zx}z})\), we have \(\mathrm{start}(\overrightarrow{zP}) \neq \mathrm{start}(\overleftarrow{xP_{zx}z})\) so we can apply Union Lemma [Lemma2]: since \(P_{zx} \cup P \subseteq D\) contains no \(x\)-tadpoles by property [item6], it contains a \(z\)-cycle.

 ◻

Proof. We prove all three assertions separately:

• Since \(s \in I_{H^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(H)}\right)\) and \(H\) is not a trivial Maker win by assumption, Proposition [prop95snakeinside] applies with \(u=z\) and \(u'=s\), hence the first assertion.

• By definition of \(I_{H^{+z}}\mathopen{}\mathclose{\left(\cdot}\right)\), we have \(s \not\in M(H^{+z})=M(H) \cup \{z\}\). Moreover, we know \(x \not\in I_{H^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(H)}\right)\) by Proposition [prop95structure][item3], so \(s \neq x\) hence the second assertion.

• Since \(s \in V(D) \setminus (M(D)\cup\{x,z\})\), there exists some \(X^{\overline{s}} \in \mathcal{F}_D\) such that \(s \not\in V(X^{\overline{s}})\) by Proposition [prop95structure][item2]. Since \(\mathcal{S}_z \cup \mathcal{T}_z \subseteq z\mathcal{D}_1(H)\), all elements of \(\mathcal{S}_z \cup \mathcal{T}_z\) must contain \(s\), so necessarily \(X^{\overline{s}} \in \mathcal{P}_{zx}\). Finally, let \(P^{\overline{s}}_1,P^{\overline{s}}_2 \in \mathcal{P}_{zx}\) be such that \(s \not\in V(P^{\overline{s}}_1)\) and \(s \not\in V(P^{\overline{s}}_2)\). Suppose for a contradiction that \(\mathrm{start}(\overrightarrow{xP^{\overline{s}}_1z}) \neq \mathrm{start}(\overrightarrow{xP^{\overline{s}}_2z})\): by Union Lemma [Lemma2], \(P^{\overline{s}}_1 \cup P^{\overline{s}}_2 \subseteq D\) contains an \(x\)-cycle (contradicting Proposition [prop95structure][item6]) or a \(z\)-tadpole (which does not contain \(s\), also a contradiction). Similarly, suppose for a contradiction that \(\mathrm{end}(\overrightarrow{xP^{\overline{s}}_1 z}) \neq \mathrm{end}(\overrightarrow{xP^{\overline{s}}_2 z})\), i.e., \(\mathrm{start}(\overleftarrow{xP^{\overline{s}}_1 z}) \neq \mathrm{start}(\overleftarrow{xP^{\overline{s}}_2 z})\): by Union Lemma [Lemma2], \(P^{\overline{s}}_1 \cup P^{\overline{s}}_2 \subseteq D\) contains an \(x\)-tadpole (contradicting Proposition [prop95structure][item6]) or a \(z\)-cycle (which does not contain \(s\), also a contradiction).

 ◻

Proof. First of all, we can assume that \(P_c\) consists of a single edge \(e\). Indeed, suppose that is not the case, and define \(e = \mathrm{end}(\overrightarrow{c\mathbf{P}_{V(D)}(c,P_c)})\) and \(c'\) as the unique vertex in \((e \cap \mathrm{inn}(P_c)) \setminus V(D)\):

• If there is a \(c'x\)-chain \(P\) in \(D \cup e\), then \(\overrightarrow{cP_c}\vert_{\{c'\}} \oplus \overrightarrow{c'Px}\) represents a \(cx\)-chain in \(D \cup P_c\).

• If there is a \(c'\)-snake \(S\) in \(D \cup e\), then \(\overrightarrow{cP_c}\vert_{\{c'\}} \oplus \overrightarrow{c'S}\) represents a \(c\)-snake in \(D \cup P_c\).

• If there is a \(c'\)-tadpole \(T\) in \(D \cup e\), then \(\overrightarrow{cP_c}\vert_{\{c'\}} \oplus \overrightarrow{c'T}\) represents a \(c\)-tadpole in \(D \cup P_c\).

Therefore, we are working in \(D \cup P_c=D \cup e\). Now suppose for a contradiction that: \[\label{cont1} \text{D \cup e contains no c-tadpoles, no cx-chains, and also no c-snakes in the case of item \ref{item195Lemma5}.}\tag{1}\] Since \(I_{H^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(H)}\right) \neq \varnothing\) by assumption, let \(s \in I_{H^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(H)}\right)\), and let \(P^{\overline{s}}\in \mathcal{P}_{zx}\) be such that \(s \not\in V(P^{\overline{s}})\) as per Proposition [prop95s]. Define \(w = o(z,\overleftarrow{xP^{\overline{s}}z})\). These notations are summed up in Figure 24.

The key to the proof is the fact that every \(z\)-tadpole contains \(s\) (by definition of \(s\)), whereas \(P^{\overline{s}}\) does not. This will eventually lead to a contradiction. Before going into details, let us explain the idea of the proof. We want to show that there exists a \(cz\)-chain \(P_{cz}^{\overline{w}}\) in \(D \cup e\) that does not contain \(w\). Indeed, suppose we manage to exhibit one. On the one hand, following \(P_{cz}^{\overline{w}}\) starting from \(c\) until touching \(P^{\overline{s}}\), we know by (1 ) that we cannot get a \(cx\)-chain. Therefore, we necessarily get a \(z\)-tadpole \(T\), containing \(s\) at a uniquely determined location, as pictured on the left of Figure 25. On the other hand, following \(P_{cz}^{\overline{w}}\) starting from \(z\) until touching \(P^{\overline{s}}\) again, we know by Proposition [prop95structure][item6] that we cannot get an \(x\)-tadpole. Therefore, we necessarily get a \(z\)-cycle, which must also contain \(s\), as pictured on the right of Figure 25. All in all, we get two disjoint parts of \(P_{cz}^{\overline{w}}\) which both contain \(s\), a contradiction. We now proceed with the rigorous proof, in three steps. We prove items [item195Lemma5] and [item295Lemma5] jointly: there are only two times during the proof where we will have to differentiate the two very briefly to make separate arguments.

1. Firstly: we show that there exists a \(cz\)-chain \(P_{cz}\) in \(D \cup e\).
   Since \(e \cap V(D) \neq \varnothing\), there exists \(X \in \mathcal{F}_D = \mathcal{S}_z \cup \mathcal{T}_z \cup \mathcal{P}_{zx}\) such that \(e \cap V(X) \neq \varnothing\). For each of the three cases, we use an adequate union lemma from Section 2:

   • Suppose \(X \in \mathcal{T}_z\), and write \(X=T\). Since there are no \(c\)-tadpoles in \(D \cup e \supseteq T \cup e\) by (1 ), Union Lemma [Lemma3] ensures that there is a \(cz\)-chain in \(T \cup e\).

   • Suppose \(X \in \mathcal{S}_z\), and write \(X=S\). We address items [item195Lemma5] and [item295Lemma5] separately. For [item195Lemma5], there are no \(c\)-snakes in \(D \cup e \supseteq S \cup e\) by (1 ). For [item295Lemma5], let \(m\) be the marked vertex such that \(S\) is a \(zm\)-snake: since \(J(\mathcal{D}_1,H)\) holds, Proposition [prop95markedvertex] tells us there are no \(m\)-tadpoles in \(D \cup e \supseteq S \cup e\). In both cases, Union Lemma [Lemma4] ensures that there is a \(cz\)-chain in \(S \cup e\).

   • Suppose \(X \in \mathcal{P}_{zx}\), and write \(X=P\). Since there are no \(cx\)-chains in \(D \cup e \supseteq P \cup e\) by (1 ), Union Lemma [Lemma1] ensures that there is a \(cz\)-chain in \(P \cup e\).

   In all cases, we get a \(cz\)-chain \(P_{cz}\) in \(D \cup e\).

2. Secondly: we show that there exists a \(cz\)-chain \(P_{cz}^{\overline{w}}\) in \(D \cup e\) that does not contain \(w\).
   We start with a useful observation about \(cz\)-chains:

   Let \(P_0\) be a \(cz\)-chain in \(D \cup e\), and write \(\overrightarrow{c\mathbf{P}_{V(P^{\overline{s}})}(c,P_0)}=(c,e_1,\ldots,e_j)\). Then: \(j>1\), \(e_j \perp \overrightarrow{xP^{\overline{s}}z}\), and \(e_{j-1} \cap e_j = \{s\}\). In particular, the \(cs\)-chain in \(P_0\) is disjoint from \(P^{\overline{s}}\).

   Proof of Claim [claim95Lemma5]. Since there are no \(cx\)-chains in \(D \cup e\) by (1 ), we apply Union Lemma [Lemma1] with \(a=x\), \(b=z\), \(P_{ab}=P^{\overline{s}}\). Note that \(e_j\) is precisely the edge \(e^* = \mathrm{end}(\overrightarrow{c\mathbf{P}_{V(P^{\overline{s}})}(c,P_0)})\) from the statement of Union Lemma [Lemma1]. We get that: \(|e_j \cap V(P^{\overline{s}})|=2\), \(e_j \perp \overrightarrow{xP^{\overline{s}}z}\), and there is a \(z\)-tadpole \(T\) in \(P^{\overline{s}}\cup e_j\).
   Since \(|e_j \cap V(P^{\overline{s}})|=2\), there is exactly one vertex of \(T\) that is not in \(P^{\overline{s}}\). That vertex is necessarily \(s\), as pictured on the left of Figure 25: indeed, we know \(s \in V(T)\) by definition of \(s\), and \(s \not\in V(P^{\overline{s}})\) by definition of \(P^{\overline{s}}\). In particular, since \(c \neq s\) (\(s \in V(D)\) whereas \(c \not\in V(D)\)), we get \(j>1\). We know \((e_1 \cup \ldots \cup e_{j-1}) \cap V(P^{\overline{s}}) = \varnothing\) by definition of a projection, therefore \(e_{j-1} \cap e_j = \{s\}\) and \((e_1,\ldots,e_{j-1})\) represents the unique \(cs\)-chain in \(P_0\), which is disjoint from \(P^{\overline{s}}\). ◻

   Applying Claim [claim95Lemma5] with \(P_0=P_{cz}\), we obtain a \(cs\)-chain \(P_{cs}\) in \(P_{cz}\) such that \(V(P_{cs}) \cap V(P^{\overline{s}})=\varnothing\): in particular, \(w \not\in V(P_{cs})\). Moreover, since \(w\) is non-marked (otherwise \(P^{\overline{s}}\) would contain an \(x\)-snake, contradicting Proposition [prop95structure][item6]), Proposition [prop95structure][item2] ensures that there exists \(X^{\overline{w}} \in \mathcal{F}_D\) such that \(w \not\in V(X^{\overline{w}})\). We thus find \(P_{cz}^{\overline{w}}\) inside \(P_{cs} \cup X^{\overline{w}}\):

   • Suppose \(X^{\overline{w}} \in \mathcal{T}_z\), and write \(X^{\overline{w}} = T\). In particular \(s \in V(T)\), so \(V(P_{cs}) \cap V(T) \neq \varnothing\). Since \(D \cup e \supseteq P_{cs} \cup T\) does not contain a \(c\)-tadpole by (1 ), Union Lemma [Lemma3] ensures that \(P_{cs} \cup T\) contains a \(cz\)-chain.

   • Suppose \(X^{\overline{w}} \in \mathcal{S}_z\), and write \(X^{\overline{w}} = S\). In particular \(s \in V(S)\), so \(V(P_{cs}) \cap V(S) \neq \varnothing\). For the second and last time in this proof, we address items [item195Lemma5] and [item295Lemma5] separately. For [item195Lemma5], there are no \(c\)-snakes in \(D \cup e \supseteq P_{cs} \cup S\) by (1 ). For [item295Lemma5], let \(m\) be the marked vertex such that \(S\) is a \(zm\)-snake: Proposition [prop95markedvertex] tells us there are no \(m\)-tadpoles in \(D \cup e \supseteq P_{cs} \cup S\). In both cases, Union Lemma [Lemma4] ensures that there is a \(cz\)-chain in \(P_{cs} \cup S\).

   • Suppose \(X^{\overline{w}} \in \mathcal{P}_{zx}\), and write \(X^{\overline{w}} = P\). Since \(w \not\in V(P)\), we have \(w \not\in \mathrm{start}(\overleftarrow{xPz})\) hence \(\mathrm{start}(\overleftarrow{xPz}) \neq \mathrm{start}(\overleftarrow{xP^{\overline{s}}z})\). By the final assertion of Proposition [prop95s], this implies \(s \in V(P)\), so \(V(P_{cs}) \cap V(P) \neq \varnothing\). Since \(D \cup e \supseteq P_{cs} \cup P\) does not contain a \(cx\)-chain by (1 ), Union Lemma [Lemma1] ensures that \(P_{cs} \cup P\) contains a \(cz\)-chain.

   In all cases, we get a \(cz\)-chain \(P_{cz}^{\overline{w}}\) in \(P_{cs} \cup X^{\overline{w}} \subseteq D \cup e\), that does not contain \(w\) since neither \(P_{cs}\) nor \(X^{\overline{w}}\) does.

3. Finally: we conclude by getting the desired contradiction illustrated on the right of Figure 25. We now work exclusively inside \(P_{cz}^{\overline{w}} \cup P^{\overline{s}}\).
   We start by defining the chains \(P_1\) and \(P_2\) pictured on the right of Figure 25. First, define the projection \(P_1 = \mathbf{P}_{V(P^{\overline{s}})}(c,P_{cz}^{\overline{w}})\). By (1 ), it is impossible that \(V(P_{cz}^{\overline{w}}) \cap V(P^{\overline{s}})=\{z\}\), because \(P_{cz}^{\overline{w}} \cup P^{\overline{s}}\) would then be a \(cx\)-chain. Therefore, the projection \(P_2 = \mathbf{P}_{V(P^{\overline{s}}) \setminus\{z\}}(z,P_{cz}^{\overline{w}})\) is also well defined. Write \(\overrightarrow{cP_{cz}^{\overline{w}}z}=(c,e_1,\ldots,e_L,z)\), \(\overrightarrow{cP_1}=(c,e_1,\ldots,e_j)\), and \(\overrightarrow{zP_2}=(z,e_L,e_{L-1},\ldots,e_{\ell})\), i.e., \(j=\min\{1 \leq i \leq L \mid e_i \cap V(P^{\overline{s}}) \neq \varnothing\}\) and \(\ell=\max\{1 \leq i \leq L \mid e_i \cap (V(P^{\overline{s}})\setminus\{z\}) \neq \varnothing\}\). Note that necessarily \(e_1=e\), since \(e\) is the only edge incident to \(c\).

   • First of all, we show that \(1<j<\ell\) and that \(s \in e_{j-1}\). By Claim [claim95Lemma5] applied with \(P_0=P_{cz}^{\overline{w}}\), we have: \(j>1\), \(e_j \perp \overrightarrow{xP^{\overline{s}}z}\), and \(e_{j-1} \cap e_j = \{s\}\). Moreover, since \(w \not \in V(P_{cz}^{\overline{w}})\), we have \(w \not\in e_j\): since \(e_j \perp \overrightarrow{xP^{\overline{s}}z}\), this implies \(z \not\in e_j\). Therefore \(j<L\), so we can consider the edge \(e_{j+1}\). Since \(s \in e_{j-1} \cap e_j\), we have \(s \not\in e_{j+1}\), so \(e_j \cap e_{j+1} \subseteq e_j \setminus \{s\} \subseteq V(P^{\overline{s}}) \setminus \{z\}\): in particular \(j<\ell\) by maximality of \(\ell\).

   • Finally, we show that \(s \in e_i\) for some \(\ell \leq i \leq L\), i.e., \(s \in V(P_2)\). Note that \(P_2 \subseteq D\): indeed, we have \(P_2 \subseteq P_{cz}^{\overline{w}} \subseteq D \cup e\), and \(e=e_1\) is not an edge of \(P_2\) because \(\ell \geq 2\). Since \(P_2 \subseteq P_{cz}^{\overline{w}}\) does not contain \(w\), we have \(\mathrm{start}(\overrightarrow{zP_2})\neq \mathrm{start}(\overrightarrow{zP^{\overline{s}}})\), so we can apply Union Lemma [Lemma2]. There are no \(x\)-tadpoles in \(P_2 \cup P^{\overline{s}}\subseteq D\) by Proposition [prop95structure][item6], so we get a \(z\)-cycle \(C\) in \(P_2 \cup P^{\overline{s}}\). Since \(C\) must contain \(s\), we have \(s \in V(P_2) \cup V(P^{\overline{s}})\) hence \(s \in V(P_2)\).

   Since \(j<\ell\), \(e_{j-1}\) is disjoint from \(e_{\ell},\ldots,e_L\) by definition of a chain. However, we have just shown that \(s \in e_{j-1}\) and \(s \in e_i\) for some \(l \leq i \leq L\). This is a contradiction.

 ◻

Proof. Let \(s \in I_{H^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(H)}\right)\), and let \(P^{\overline{s}}\in \mathcal{P}_{zx}\) be such that \(s \not\in V(P^{\overline{s}})\) as per Proposition [prop95s]. We define \(e_x = \mathrm{start}(\overrightarrow{xP^{\overline{s}}z})\). We will show at the end of the proof that \(e_x\) is the unique edge of \(D\) containing \(x\).
For now, let \(P_x\) be an \(x\)-chain in \(H\) such that \(V(P_x) \cap (V(D) \setminus \{x\}) \neq \varnothing\) and \(\mathrm{start}(\overrightarrow{xP_x}) \neq e_x\). Up to replacing \(P_x\) by the projection \(\mathbf{P}_{V(D) \setminus \{x\}}(x,P_x)\), assume that \(\mathrm{end}(\overrightarrow{xP_x})\) is the only edge of \(P_x\) that intersects \(V(D) \setminus \{x\}\). Suppose for a contradiction that: \[\label{cont2} \text{There are no x-snakes and no x-tadpoles in D \cup P_x.}\tag{2}\] Let \(e = \mathrm{start}(\overrightarrow{xP_x})\). We distinguish between two cases, pictured in Figure 26.

1. Case 1: \(P_x\) is of length at least 2, i.e., \(e \cap V(D)=\{x\}\) (since we have just assumed that \(\mathrm{end}(\overrightarrow{xP_x})\) is the only edge of \(P_x\) that intersects \(V(D) \setminus \{x\}\)).
   Write \(e=\{x,a,c\}\) where \(c\) is the only vertex in \(\mathrm{inn}(P_x) \cap e\), and let \(P_c\) be the \(c\)-chain defined as \(P_c= P_x^{-x-a}\) (see Figure 26). Since \(H\) is not a trivial Maker win and \(I_{H^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(H)}\right) \neq \varnothing\), we can apply item [item195Lemma5] of Union Lemma [Lemma5] in \(H\) to \(D\) and \(P_c\), which tells us that \(D \cup P_c\) contains one of the following:

   • a \(cx\)-chain \(P\). Then the walk \((x,e,c)\oplus \overrightarrow{cPx}\) represents an \(x\)-cycle in \(D \cup P_x\).

   • a \(c\)-tadpole \(T\). If \(x \in V(T)\), then \(T\) contains a \(cx\)-chain by Substructure Lemma [lemma95subchain4bis], so we simply go back to that case. If \(x \not\in V(T)\), then the walk \((x,e,c)\oplus \overrightarrow{cT}\) represents an \(x\)-tadpole in \(D \cup P_x\).

   • a \(c\)-snake \(S\). If \(x \in V(S)\), then \(S\) contains a \(cx\)-chain by Substructure Lemma [lemma95subchain1] so we simply go back to that case. If \(x \not\in V(S)\), then the walk \((x,e,c)\oplus \overrightarrow{cS}\) represents an \(x\)-snake in \(D \cup P_x\).

   All three possibilities contradict (2 ). This ends Case 1.

2. Case 2: \(P_x=e\) is of length 1, i.e., \(|e \cap V(D)| \geq 2\).
   Write \(e=\{x,a,b\}\). As a gadget, we create a new non-marked vertex \(c\) and an edge \(\widetilde{e}=\{a,b,c\}\) (see Figure 26).

   Let \(X\) be a subhypergraph of \(D \cup \widetilde{e}\) such that \(\widetilde{e} \in E(X)\) and \(x \not\in V(X)\), and define the subhypergraph \(\varphi(X)\) of \(D \cup e\) obtained from \(X\) by replacing \(c\) by \(x\) and \(\widetilde{e}\) by \(e\). Then we have the isomorphisms of pointed marked hypergraphs: \((X,c) \sim (\varphi(X),x)\) and \((X,v) \sim (\varphi(X),v)\) for all \(v \in V(X) \setminus (M(X) \cup \{c\})\).

   Proof of Claim [claim95Lemma6]. This is straightforward. ◻

   The idea is to apply Union Lemma [Lemma5] in \(D \cup \widetilde{e}\) to \(D\) and \(P_c =\widetilde{e}\), and then contradict (2 ) through replacing \(\widetilde{e}\) by \(e\) in the obtained subhypergraph as per Claim [claim95Lemma6]. To do so, we need to check that \(D \cup \widetilde{e}\) is not a trivial Maker win and that \(I_{(D \cup \widetilde{e})^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(D \cup \widetilde{e})}\right) \neq \varnothing\).
   The former is clear: we know \(D \subseteq H\) is not a trivial Maker win, moreover there are no \(x\)-snakes in \(P_x\) by (2 ) so \(M(e)=\varnothing\) hence \(M(\widetilde{e})=\varnothing\), so \(D \cup \widetilde{e}\) is not a trivial Maker win either.
   The latter is more difficult, because the addition of \(\widetilde{e}\) may create new \(\mathcal{D}_1\)-dangers at \(z\). However, we now show that they all contain \(s\), i.e., \(s \in I_{(D \cup \widetilde{e})^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(D \cup \widetilde{e})}\right)\). Indeed, let \(X\) be a \(\mathcal{D}_1\)-danger at \(z\) in \(D \cup \widetilde{e}\): we want to show that \(s \in V(X)\).

   • Suppose \(\widetilde{e} \not\in E(X)\). Then \(X \in z\mathcal{D}_1(H)\), hence \(s \in V(X)\) by definition of \(s\).

   • Suppose \(\widetilde{e} \in E(X)\) and \(x \not\in V(X)\). By Claim [claim95Lemma6], we have \((X,z) \sim (\varphi(X),z)\), therefore \(\varphi(X)\) is a \(\mathcal{D}_1\)-danger at \(z\) in \(D \cup e\) hence \(s \in V(\varphi(X))\). Since \(s \neq x\) by Proposition [prop95s], this yields \(s \in V(X)\).

   • Finally, suppose \(\widetilde{e} \in E(X)\) and \(x \in V(X)\). In particular, we have \(c,x \in V(X)\).

     • If there exists a \(cx\)-chain \(P\) in \(X\), then necessarily \(\mathrm{start}(\overrightarrow{cPx})=\widetilde{e}\) since \(\widetilde{e}\) is the only edge incident to \(c\) in \(D \cup \widetilde{e}\). Either \(a\) or \(b\), say \(b\), is an inner vertex of \(P\), so that \(P^{-c-a}\) is a \(bx\)-chain in \(D\) that does not contain \(a\). This means that \(P^{-c-a} \cup e\) is an \(x\)-cycle in \(D \cup e\), contradicting (2 ).

     • If there are no \(cx\)-chains in \(X\), then the only possibility according to Substructure Lemmas [lemma95subchain1] and [lemma95subchain4bis] is that \(X\) is a \(z\)-tadpole (we write \(X=T\)) such that \(C_T\) is of length 2 and \(\mathrm{out}(C_T)=\{c,x\}\) as in Figure 27. Therefore, the edges incident respectively to \(c\) and \(x\) in \(T\) intersect on two vertices. Since the edge incident to \(c\) in \(T\) is necessarily \(\widetilde{e}=\{a,b,c\}\), the edge incident to \(x\) in \(T\) is precisely \(\{a,b,x\}=e\). Define the \(zx\)-chain \(P = T^{-c}\), as in Figure 27. Since \(T \subseteq D \cup \widetilde{e}\), we have \(P \subseteq D\), so \(P \in \mathcal{P}_{zx}\) by maximality of the decomposition. Moreover \(\mathrm{start}(\overrightarrow{xPz})=e\neq e_x = \mathrm{start}(\overrightarrow{xP^{\overline{s}}z})\) by assumption, so the final assertion of Proposition [prop95s] ensures that \(s \in V(P) \subseteq V(X)\).

       

   Now that we have shown that \(I_{(D \cup \widetilde{e})^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(D \cup \widetilde{e})}\right) \neq \varnothing\), we can apply Union Lemma [Lemma5] in \(D \cup \widetilde{e}\) to \(D\) and \(P_c = \widetilde{e}\), which tells us that \(D \cup \widetilde{e}\) contains one of the following:

   • a \(cx\)-chain \(P\). In this case, taking \(P\) and replacing \(\widetilde{e}\) by \(e\) yields an \(x\)-cycle. Indeed, write \(\overrightarrow{cPx}=(c,e_1,\ldots,e_L,x)\): since \(\widetilde{e}\) is the only edge incident to \(c\), we have \(e_1=\widetilde{e}\), so the walk \((x,e,e_2,\ldots,e_L,x)\) represents an \(x\)-cycle in \(D \cup e\).

   • a \(c\)-tadpole \(T\). Since \(\widetilde{e}\) is the only edge incident to \(c\), we have \(\widetilde{e} \in E(T)\). If \(x \in V(T)\), then \(T\) contains a \(cx\)-chain so we simply go back to that case. If \(x \not\in V(T)\), then by Claim [claim95Lemma6] we have \((T,c) \sim (\varphi(T),x)\), so \(\varphi(T)\) is an \(x\)-tadpole in \(D \cup e\).

   • a \(c\)-snake \(S\). Since \(\widetilde{e}\) is the only edge incident to \(c\), we have \(\widetilde{e} \in E(S)\). If \(x \in V(S)\), then \(S\) contains a \(cx\)-chain so we simply go back to that case. If \(x \not\in V(S)\), then by Claim [claim95Lemma6] we have \((S,c) \sim (\varphi(S),x)\), so \(\varphi(S)\) is an \(x\)-snake in \(D \cup e\).

   All three possibilities thus contradict (2 ). This ends Case 2 and concludes the proof of the second assertion of the lemma.

Finally, we prove the first assertion of the lemma, namely, that \(e_x\) is the only edge of \(D\) that is incident to \(x\). Suppose for a contradiction that there exists \(e'_x \in E(D)\) such that \(x \in e'_x\) and \(e'_x \neq e_x\). Define \(P_x = e'_x\): we have \(V(P_x) \cap (V(D) \setminus \{x\}) = e'_x \setminus \{x\} \neq \varnothing\) and \(\mathrm{start}(\overrightarrow{xP_x}) = e'_x \neq e_x\). Therefore, we can apply the second assertion of the lemma to the chain \(P_x\): we get an \(x\)-snake or an \(x\)-tadpole in \(D \cup P_x = D\), contradicting Proposition [prop95structure][item6]. ◻

Proof. Suppose for a contradiction that there exists some \(m \in M(D)\). As a gadget, we add two new non-marked vertices \(a\) and \(c\) as well as a new edge \(\widetilde{e}=\{a,c,m\}\). This does not create any new \(\mathcal{D}_1\)-danger at \(z\): indeed, it is obvious that a \(z\)-snake or a \(z\)-tadpole cannot contain an edge with two non-marked vertices of degree 1 other than \(z\). For that reason, the fact that \(J(\mathcal{D}_1,D)\) holds implies that \(J(\mathcal{D}_1,D \cup \widetilde{e})\) holds as well. Moreover, since \(D\) is not a trivial Maker win by Proposition [prop95structure][item5], \(D \cup \widetilde{e}\) is not either. Therefore, item [item295Lemma5] of Union Lemma [Lemma5] applied to \(D\) and \(P_c = \widetilde{e}\) ensures that \(D \cup \widetilde{e}\) contains a \(cx\)-chain or a \(c\)-tadpole. Since \(\widetilde{e}\) is the only edge containing \(c\), it is easy to see by removing \(\widetilde{e}\) that \(D\) contains an \(mx\)-chain or an \(m\)-tadpole respectively (see Figure 28). The former is impossible because an \(mx\)-chain in \(D\) is an \(x\)-snake in \(D\), which cannot exist by Proposition [prop95structure][item6]. The latter is impossible by Proposition [prop95markedvertex]. We can conclude that \(M(D)=\varnothing\), which implies \(\mathcal{S}_z=\varnothing\) hence the final assertion. ◻

Proof. This is the first assertion of Union Lemma [Lemma6] applied in \(H=D\). ◻

Proof. Assume that \(D\) is not of type (2): we show that \(D\) is of type (1).

Of all pairs \((C,P_{xw})\) as in Claim [claim95TwoTypes0], we choose one where \(P_{xw}\) is longest. This choice ensures that:

We will show that \(x \not\in V(C)\), i.e., \(x \neq w\) at the end of the proof. For now, let \(e\) be the only edge of \(C\) containing \(w\), and let us show the existence of \(X \in \mathcal{F}_D\) such that \(V(X) \cap V(P_{xw}) \neq \varnothing\) and \(e \setminus \{w\} \not\subseteq V(X)\).
Let us first address the case \(z \in e\). Since \(z \in \mathrm{inn}(C)\) and \(w \in \mathrm{out}(C)\), we have \(z \neq w\). Let \(v\) be the third vertex of \(e\), so that \(e=\{w,z,v\}\). By Proposition [prop95structure][item2], there exists \(X^{\overline{v}} \in \mathcal{F}_D\) such that \(v \not\in V(X^{\overline{v}})\), which implies \(e \setminus \{w\} \not\subseteq V(X^{\overline{v}})\). Suppose for a contradiction that \(V(X^{\overline{v}}) \cap V(P_{xw}) = \varnothing\). In particular \(X^{\overline{v}}\) is not a \(zx\)-chain. We also know \(X^{\overline{v}}\) is not a \(z\)-snake by Proposition [prop95nomarkedvertex], so \(X^{\overline{v}}\) is a \(z\)-tadpole. We write \(X^{\overline{v}}=T\). Since \(V(T) \cap (V(P_{xw}) \cup e) = \{z\}\), the walk \(\overrightarrow{xP_{xw}w} \oplus (w,e,z) \oplus \overrightarrow{zT}\) represents an \(x\)-tadpole in \(D\), contradicting Proposition [prop95structure][item6]. In conclusion, we have \(V(X^{\overline{v}}) \cap V(P_{xw}) \neq \varnothing\).
We can now assume that \(z \not\in e\). Write \(\overrightarrow{zC}=(z,e_1,\ldots,e_L,z)\): we have \(e=e_i\) for some \(1 \leq i \leq L\). Actually, since \(z \not\in e\), we have \(L \geq 3\) and \(2 \leq i \leq L-1\). We can thus define \(w_1\) (resp. \(w_2\)) as the only vertex in \(e_{i-1} \cap e_i\) (resp. in \(e_i \cap e_{i+1}\)), and we have \(e=\{w,w_1,w_2\}\). Therefore, defining \(P_1 =[(z,e_1,\ldots,e_{i-1},w_1)]\) and \(P_2 = [(z,e_L,e_{L-1},\ldots,e_{i+1},w_2)]\), \(P_1\) is a \(zw_1\)-chain and \(P_2\) is a \(zw_2\)-chain. These notations are summed up in Figure 30.

Since \(z \not\in e\), we have \(w_1, w_2 \neq z\). By Proposition [prop95structure][item2], for all \(j \in \{1,2\}\), there exists \(X^{\overline{w_j}} \in \mathcal{F}_D\) such that \(w_j \not\in V(X^{\overline{w_j}})\), which implies \(e \setminus \{w\} \not\subseteq V(X^{\overline{w_j}})\). We choose \(X^{\overline{w_1}}=X^{\overline{w_2}}\) if possible, i.e., if there exists an element of \(\mathcal{F}_D\) containing neither \(w_1\) nor \(w_2\). Suppose for a contradiction that \(V(X^{\overline{w_1}}) \cap V(P_{xw}) = \varnothing\) and \(V(X^{\overline{w_2}}) \cap V(P_{xw}) = \varnothing\).
In particular, \(X^{\overline{w_1}}\) and \(X^{\overline{w_2}}\) are not \(zx\)-chains, moreover they are not \(z\)-snakes by Proposition [prop95nomarkedvertex] and they are not \(z\)-cycles by Claim [claim95TwoTypes]. Therefore, \(X^{\overline{w_1}}\) and \(X^{\overline{w_2}}\) are \(z\)-tadpoles that are not cycles. We write \(X^{\overline{w_1}} = T^{\,\overline{w_1}}\) and \(X^{\overline{w_2}} = T^{\,\overline{w_2}}\). We distinguish between two cases, obtaining a contradiction for both.

• First case: \(e_L \not\in E(T^{\,\overline{w_1}})\) or \(e_1 \not\in E(T^{\,\overline{w_2}})\). By symmetry, assume that \(e_L \not\in E(T^{\,\overline{w_1}})\).
  It is impossible that \(V(T^{\,\overline{w_1}}) \cap V(P_2)=\{z\}\), otherwise we would have \(V(T^{\,\overline{w_1}}) \cap (V(P_{xw}) \cup e \cup V(P_2))=\{z\}\) so the walk \(\overrightarrow{xP_{xw}w} \oplus (w,e,w_2) \oplus \overrightarrow{w_2P_2z} \oplus \overrightarrow{zT^{\,\overline{w_1}}}\) would represent an \(x\)-tadpole in \(D\), contradicting Proposition [prop95structure][item6]. Therefore, the projection \(P^{\,\overline{w_1}} = \mathbf{P}_{V(P_2) \setminus \{z\}}(z,T^{\,\overline{w_1}})\) is well defined. Since \(P^{\,\overline{w_1}} \subseteq T^{\,\overline{w_1}}\), we have \(V(P^{\,\overline{w_1}}) \cap (V(P_{xw}) \cup \{w_1\})=\varnothing\) and \(e_L \not\in E(P^{\,\overline{w_1}})\). In particular \(\mathrm{start}(\overrightarrow{zP^{\,\overline{w_1}}}) \neq e_L=\mathrm{start}(\overrightarrow{zP_2w_2})\), so we can apply Union Lemma [Lemma2]. Since \(P_2 \cup P^{\,\overline{w_1}}\) cannot contain a \(z\)-cycle by Claim [claim95TwoTypes], it contains a \(w_2\)-tadpole \(T\). We have \(V(T) \subseteq V(P_2) \cup V(P^{\,\overline{w_1}})\) hence \(V(T) \cap (V(P_{xw}) \cup e) = \{w_2\}\), so the walk \(\overrightarrow{xP_{xw}w} \oplus (w,e,w_2) \oplus \overrightarrow{w_2T}\) represents an \(x\)-tadpole in \(D\), contradicting Proposition [prop95structure][item6].

• Second case: \(e_L \in E(T^{\,\overline{w_1}})\) and \(e_1 \in E(T^{\,\overline{w_2}})\).
  Since \(T^{\,\overline{w_1}}\) and \(T^{\,\overline{w_2}}\) are not cycles, \(z\) is of degree 1 in both of them, hence \(e_1 \not\in E(T^{\,\overline{w_1}})\) and \(e_L \not\in E(T^{\,\overline{w_2}})\). Since \(e_1 \in E(T^{\,\overline{w_2}})\) and \(e_1 \not\in E(T^{\,\overline{w_1}})\), we have \(T^{\,\overline{w_1}} \neq T^{\,\overline{w_2}}\), so our initial choice of \(T^{\,\overline{w_1}}\) and \(T^{\,\overline{w_2}}\) ensures that \(w_2 \in V(T^{\,\overline{w_1}})\) and \(w_1 \in V(T^{\,\overline{w_2}})\).

  • Firstly, suppose that \(w_2 \not\in \mathrm{out}(C_{T^{\,\overline{w_1}}})\) or \(w_1 \not\in \mathrm{out}(C_{T^{\,\overline{w_2}}})\). By symmetry, assume that \(w_2 \not\in \mathrm{out}(C_{T^{\,\overline{w_1}}})\). By Substructure Lemma [lemma95subtadpole], \(T^{\,\overline{w_1}}\) contains a \(w_2\)-tadpole \(T\). Since \(V(T) \cap (V(P_{xw}) \cup e)=\{w_2\}\), the walk \(\overrightarrow{xP_{xw}w} \oplus (w,e,w_2) \oplus \overrightarrow{w_2T}\) represents an \(x\)-tadpole in \(D\), which contradicts Proposition [prop95structure][item6].

  • Finally, suppose that \(w_2 \in \mathrm{out}(C_{T^{\,\overline{w_1}}})\) and \(w_1 \in \mathrm{out}(C_{T^{\,\overline{w_2}}})\). Since \(J(\mathcal{D}_1,D)\) holds, there exists \(s \in I_{D^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(D)}\right)\). In particular, \(s \in V(T^{\,\overline{w_1}}) \cap V(C)\). Since \(w \not\in V(T^{\,\overline{w_1}})\), we have \(s \neq w\), hence \(s \in V(P_1)\) or \(s \in V(P_2)\). By symmetry, assume \(s \in V(P_1)\). In particular, \(s \neq w_2\): by Substructure Lemma [lemma95subchain4], the fact that \(w_2 \in \mathrm{out}(C_{T^{\,\overline{w_1}}})\) thus ensures the existence of a \(zs\)-chain \(P_{zs}^{\,\overline{w_2}}\) in \(T^{\,\overline{w_1}}\) that does not contain \(w_2\). Since \(e_1 \not\in E(T^{\,\overline{w_1}})\), we have \(e_1 \not\in E(P_{zs}^{\,\overline{w_2}})\). Therefore \(\mathrm{start}(\overrightarrow{zP_{zs}^{\,\overline{w_2}}}) \neq e_1=\mathrm{start}(\overrightarrow{zP_1w_1})\), moreover \(V(P_{zs}^{\,\overline{w_2}}) \cap (V(P_1) \setminus \{z\}) \supseteq \{s\} \neq \varnothing\) so we can apply Union Lemma [Lemma2]: since \(P_1 \cup P_{zs}^{\,\overline{w_2}}\) cannot contain a \(z\)-cycle by Claim [claim95TwoTypes], it contains a \(w_1\)-tadpole \(T\). We have \(V(T) \subseteq V(P_1) \cup V(P_{zs}^{\,\overline{w_2}})\) hence \(V(T) \cap (V(P_{xw}) \cup e) = \{w_1\}\), so the walk \(\overrightarrow{xP_{xw}w} \oplus (w,e,w_1) \oplus \overrightarrow{w_1T}\) represents an \(x\)-tadpole in \(D\), contradicting Proposition [prop95structure][item6].

In conclusion, we have shown the existence of \(X \in \mathcal{F}_D\) such that \(V(X) \cap V(P_{xw}) \neq \varnothing\) and \(e \setminus \{w\} \not\subseteq V(X)\). To prove that \(D\) is of type (1), it only remains to show that \(x \not\in V(C)\). Suppose for a contradiction that \(x \in V(C)\), i.e., \(x=w\), i.e., \(V(P_{xw})=\{x\}\). Since \(V(X) \cap V(P_{xw}) \neq \varnothing\) by definition of \(X\), we get \(x \in V(X)\), so there exists an edge \(e'\) of \(X\) that is incident to \(x\). Moreover, \(e\) is also incident to \(w=x\). Since \(e \not\in E(X)\) by definition of \(X\), we have \(e' \neq e\). Therefore, \(e\) and \(e'\) are two distinct edges of \(D\) that are incident to \(x\), contradicting Proposition [prop95degree1]. This ends the proof. ◻

Proof. The case where \(H\) contains a nunchaku of length 1 is obvious:

When there exists a nunchaku of length at least 2, Maker can use a "dichotomy strategy" to halve the length of a shortest nunchaku each round, until she gets one of length 1 (which is a trivial Maker win):

Meanwhile, Breaker has a strategy ensuring that, if there exists a nunchaku at the beginning of a round, then the length of a shortest nunchaku has not been more than halved after the round, and if there are no nunchakus before a round, then there are still none after the round:

We now have all the elements to prove the theorem by induction on \(|V(H) \setminus M(H)|\).

• For the base case, let \(H\) be a 3-uniform marked hyperforest with no fully marked edges such that \(|V(H) \setminus M(H)| \leq 1\). If \(H\) contains a nunchaku, then it is necessarily of length 1, so Claim [claim95forest0] concludes. If \(H\) contains no nunchakus, then in particular \(H\) contains no nunchakus of length 1: since \(H\) has no fully marked edges, this means \(H\) is not a trivial Maker win, so \(H\) is a Breaker win.

• For the induction step, let \(H\) be a 3-uniform marked hyperforest with no fully marked edges such that \(|V(H) \setminus M(H)| \geq 2\), and assume that the theorem is true for all 3-uniform marked hyperforests with less than \(|V(H) \setminus M(H)|\) non-marked vertices. Since Claim [claim95forest0] concludes if \(L(H)=1\), also assume \(L(H)>1\): this ensures that \(H\) is not a trivial Maker win and that there cannot be a fully marked edge after one round. Therefore, by the induction hypothesis: \[\tau_M(H) = 1+\underset{x \in V(H) \setminus M(H)}{\min}\,\,\underset{y \in V(H^{+x}) \setminus M(H^{+x})}{\max}\,\,(1+\lceil \log_2(L(H^{+x-y})) \rceil),\] with the convention that \(1+\lceil \log_2(L(H^{+x-y})) \rceil=\infty\) if \(L(H^{+x-y})=\infty\).

  • Firstly, suppose \(H\) contains a nunchaku, i.e., \(2 \leq L(H)<\infty\). By Claims [claim95forest1] and [claim95forest2] respectively, the above equality yields \(\tau_M(H) \leq 1+ \mathopen{}\mathclose{\left( 1+\mathopen{}\mathclose{\left\lceil \log_2\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lceil\frac{L(H)}{2}}\right\rceil}\right) }\right\rceil }\right)\) and \(\tau_M(H) \geq 1+ \mathopen{}\mathclose{\left( 1+\mathopen{}\mathclose{\left\lceil \log_2\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lceil\frac{L(H)}{2}}\right\rceil}\right) }\right\rceil }\right)\). Therefore \(\tau_M(H) = 1+ \mathopen{}\mathclose{\left( 1+\mathopen{}\mathclose{\left\lceil \log_2\mathopen{}\mathclose{\left(\mathopen{}\mathclose{\left\lceil\frac{L(H)}{2}}\right\rceil}\right) }\right\rceil }\right) = 1+\lceil \log_2(L(H)) \rceil < \infty\), so \(H\) is a Maker win.

  • Finally, suppose \(H\) contains no nunchakus, i.e., \(L(H)=\infty\). By Claim [claim95forest2]: for all \(x \in V(H)\setminus M(H)\), there exists \(y \in V(H^{+x})\setminus M(H^{+x})\) such that \(L(H^{+x-y})=\infty\). Therefore \(\tau_M(H)=\infty\), so \(H\) is a Breaker win. This ends the proof.

 ◻

Proof. Recall that the "only if" direction is automatic by Proposition [prop95cn]. Suppose that \(H\) is a Maker win. Since \(H\) is not a trivial Maker win, we know \(H\) has no fully marked edges, so Lemma [lemma95forest] ensures that \(H\) contains a nunchaku \(N\). Again, since \(H\) is not a trivial Maker win, \(N\) is of length at least 2. Let \(x \in \mathrm{inn}(N)\), so that \(N\) is the union of two \(x\)-snakes \(S\) and \(S'\) such that: \(|M(S)|=1\), \(|M(S')|=1\), and \(V(S) \cap V(S')=\{x\}\). Therefore, \(\{S,S'\}\) is a \(\mathcal{D}_0\)-fork at \(x\) in \(N\), so \(J(\mathcal{D}_0,N)\) does not hold and neither does \(J(\mathcal{D}_0,H)\). ◻

Proof of Theorem [theo95main95structure1] assuming Lemma [lemma95main95structure]. Item [item95Maker] is a direct consequence of Proposition [prop95cn]. We now show item [item95Breaker] by induction on \(|V(H) \setminus M(H)|\).

• Let us start with the base case \(|V(H) \setminus M(H)| \in \{2,3\}\). Let \(x_1 \in V(H) \setminus M(H)\) and \(y_1 \in I_{H^{+x_1}}\mathopen{}\mathclose{\left(x_1\mathcal{D}_2(H)}\right)\), which exists since \(J(\mathcal{D}_2,H)\) holds. The trivial danger of size 3 is in \(\mathcal{D}_0 \subseteq \mathcal{D}_2\) (snake of length 1), so any edge of \(H\) that contains both \(x_1\) and some \(m \in M(H)\) must have \(y_1\) as its third vertex. Therefore, as \(H\) is not a trivial Maker win, \(H^{+x_1-y_1}\) is not a trivial Maker win either. Since \(|V(H^{+x_1-y_1}) \setminus M(H^{+x_1-y_1})|\leq 1\), this means \(H^{+x_1-y_1}\) is a Breaker win, so \(H\) is a Breaker win.

• For the induction step, assume \(|V(H) \setminus M(H)| \geq 4\) and item [item95Breaker] to be true for marked hypergraphs with less non-marked vertices than \(H\). Let \(x_1 \in V(H) \setminus M(H)\) and \(y_1 \in I_{H^{+x_1}}\mathopen{}\mathclose{\left(x_1\mathcal{D}_2(H)}\right)\), which exists since \(J(\mathcal{D}_2,H)\) holds: we must show that \(H^{+x_1-y_1}\) is a Breaker win. Let us first list a few important properties of \(H^{+x_1-y_1}\):

  1. \(|V(H^{+x_1-y_1}) \setminus M(H^{+x_1-y_1})| = |V(H) \setminus M(H)| - 2 \geq 2\).

  2. \(H^{+x_1-y_1}\) is not a trivial Maker win. Just like in the base case, this comes from the fact that \(H\) is not a trivial Maker win and the trivial danger of size 3 is in \(\mathcal{D}_2\).

  3. \(J(\mathcal{D}_1,H^{+x_1-y_1})\) holds. Indeed, \(J(\mathcal{D}_1,H)\) holds (because \(J(\mathcal{D}_2,H)\) holds) and \(y_1 \in I_{H^{+x_1}}\mathopen{}\mathclose{\left(x_1\mathcal{D}_2(H)}\right)\), so Proposition [prop95equiv95dangers2] applies and ensures that \(J(\mathcal{D}_1,H^{+x_1-y_1})\) holds.

  Thanks to [property95a] and [property95b], checking that property \(J(\mathcal{D}_2,H^{+x_1-y_1})\) holds is sufficient to prove that \(H^{+x_1-y_1}\) is a Breaker win, according to the induction hypothesis. Let \(x \in V(H^{+x_1-y_1}) \setminus M(H^{+x_1-y_1})\): we want to show that \(I_{(H^{+x_1-y_1})^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H^{+x_1-y_1})}\right) \neq \varnothing\). Assume that there exists some \(D_0 \in x\mathcal{D}_2(H^{+x_1-y_1})\), otherwise \(I_{(H^{+x_1-y_1})^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H^{+x_1-y_1})}\right)=I_{(H^{+x_1-y_1})^{+x}}\mathopen{}\mathclose{\left(\varnothing}\right)=V((H^{+x_1-y_1})^{+x}) \setminus M((H^{+x_1-y_1})^{+x}) \neq \varnothing\) trivially as \(|V(H)\setminus M(H)|\geq 4\).

  1. First case: there are no \(xx_1\)-snakes in \(H^{+x_1-y_1}\).
     What happens here is that any vertex that hits all the \(\mathcal{D}_2\)-dangers at \(x\) in \(H\) still works in \(H^{+x_1-y_1}\), because the marking of \(x_1\) has not created any new \(\mathcal{D}_2\)-danger at \(x\). Indeed, for all \(D \in x\mathcal{D}_2(H^{+x_1-y_1})\):

     • If \((D,x) \in \mathcal{D}_1\) and \(D\) is an \(x\)-snake, then \(x_1 \not\in V(D)\) since we are assuming that there are no \(xx_1\)-snakes in \(H^{+x_1-y_1}\).

     • If \((D,x) \in \mathcal{D}_1\) and \(D\) is an \(x\)-tadpole, then \(x_1 \not\in V(D)\) since \(M(D)=\varnothing\).

     • If \((D,x) \in \widehat{\mathcal{D}_1}\), then \(x_1 \not\in V(D)\) since \(M(D)=\varnothing\) by Proposition [prop95nomarkedvertex] (which [property95c] allows us to use).

     Therefore, \(x\mathcal{D}_2(H^{+x_1-y_1}) \subseteq x\mathcal{D}_2(H^{-x_1-y_1}) \subseteq x\mathcal{D}_2(H)\). Let \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H)}\right)\), which exists since \(J(\mathcal{D}_2,H)\) holds. To show that \(y \in I_{(H^{+x_1-y_1})^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H^{+x_1-y_1})}\right)\), since \(x\mathcal{D}_2(H^{+x_1-y_1}) \subseteq x\mathcal{D}_2(H)\), it suffices to check that \(y \not\in\{x_1,y_1\}\). For this, we use \(D_0\). On the one hand, we have \(D_0 \in x\mathcal{D}_2(H^{+x_1-y_1}) \subseteq x\mathcal{D}_2(H)\) hence \(y \in V(D_0)\). On the other hand, we have \(D_0 \in x\mathcal{D}_2(H^{+x_1-y_1}) \subseteq x\mathcal{D}_2(H^{-x_1-y_1})\) hence \(x_1,y_1 \not\in V(D_0)\). In conclusion, we do have \(y \not\in\{x_1,y_1\}\), so \(y \in I_{(H^{+x_1-y_1})^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H^{+x_1-y_1})}\right)\) hence \(I_{(H^{+x_1-y_1})^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H^{+x_1-y_1})}\right) \neq \varnothing\).

  2. Second case: there is an \(xx_1\)-snake in \(H^{+x_1-y_1}\).
     Here, we have the \(x\)-snake that is necessary to apply Lemma [lemma95main95structure] to \(H^{+x_1-y_1}\). The other assumptions of this lemma are also verified thanks to [property95a], [property95b] and [property95c]. In conclusion, Lemma [lemma95main95structure] applies and yields \(I_{(H^{+x_1-y_1})^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H^{+x_1-y_1})}\right) \neq \varnothing\) as desired.

As for the final assertion of the theorem about the appearance of a nunchaku or a necklace, the "if" direction is clear since nunchakus and necklaces are Maker wins (Proposition [prop95forcing]), while the "only if" direction follows from item [item95Breaker] and Proposition [prop95interpretation]. ◻

Proof of Theorem [theo95main95structure2] assuming Lemma [lemma95main95structure]. If \(H\) is a Breaker win, then \(J(\mathcal{D}_1,H)\) holds by Proposition [prop95cn]. Conversely, assume that \(J(\mathcal{D}_1,H)\) holds. We claim that, actually, \(J(\mathcal{D}_2,H)\) holds: indeed, for all \(x \in V(H) \setminus M(H)\), there exists an \(x\)-snake in \(H\) by assumption hence \(I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_2(H)}\right) \neq \varnothing\) by Lemma [lemma95main95structure]. Therefore, \(H\) is a Breaker win according to Theorem [theo95main95structure1]. As for the final assertion of the theorem about the appearance of a nunchaku or a necklace, the "if" direction is clear since nunchakus and necklaces are Maker wins (Proposition [prop95forcing]), while the "only if" direction follows from Proposition [prop95interpretation]. ◻

Proof of Theorem [theo95main95algo] assuming Lemma [lemma95main95structure]. First of all, let us transform the input (non-marked) hypergraph of rank 3 into a (still non-marked) 3-uniform hypergraph. We can assume that all edges are of size 2 or 3, otherwise we have a trivial Maker win. Using Proposition [prop95duplication], we then transform each edge of size 2 into two edges of size 3. At most, we have added two vertices and doubled the number of edges, so all relevant orders of magnitude are preserved. All in all, up to a preprocessing step in time \(O(m)\), we can assume that \(H\) is a non-marked 3-uniform hypergraph.
Since \(\mathrm{\small MakerBreaker}\) is trivially solved in time \(O(1)\) on hypergraphs with less than 6 vertices, further assume \(|V(H)| \geq 6\). By Theorem [theo95main95structure1], \(H\) is a Maker win if and only if:

Our algorithm checks whether the above assertion is true, as follows. Suppose that we are given \(x_1,y_1,x_2,y_2,x_3,y_3\), and consider the marked hypergraph \(H^{+x_1-y_1+x_2-y_2+x_3-y_3}\), in which \(x_1,x_2,x_3\) are the only marked vertices:

• Clearly, \(H^{+x_1-y_1+x_2-y_2+x_3-y_3}\) contains a fully marked edge or a nunchaku if and only if it contains a chain between two marked vertices. By Theorem [theo95archipelagos], this can be tested in time \(O(m^2)\): for all \(i \in \{1,2\}\), compute \(LCC_{H^{-y_1-y_2-y_3}}(x_i)\) and check whether it contains \(x_j\) for some \(j \in \{2,3\} \setminus \{i\}\). We note that membership to a given linear connected component \(L\) is verifiable in constant time: this can be done by implementing \(L\) as an array of length \(n\), with indices corresponding to the vertices of \(H\), where the element at index \(i\) is a 1 if the corresponding vertex is in \(L\) or a 0 otherwise.

• If \(H^{+x_1-y_1+x_2-y_2+x_3-y_3}\) contains no fully marked edges and no nunchakus, then it contains a necklace if and only if it contains some edge \(e=\{x,a,b\}\) with \(x\) marked such that there exists an \(xb\)-chain \(P\) that does not contain \(a\) (the necklace is then \(P \cup e\)). This can be tested in time \(O(\Delta m^2)\): for all \(i \in \{1,2,3\}\) and for every edge \(\{x_i,a,b\}\), compute \(LCC_{H^{-y_1-y_2-y_3-a}}(x_i)\) and check whether it contains \(b\), then repeat when exchanging the roles of \(a\) and \(b\).

This yields an algorithm in time \(O(n^6(m^2+\Delta m^2))=O(n^6\Delta m^2)\). However, we can easily apply a slight improvement to it. Indeed, since the linear connected components that we need only depend on four out of the six vertices \(x_1,y_1,x_2,y_2,x_3,y_3\), computing them inside of the six nested loops leads to some redundancies. Instead, it is better to compute all of them once and for all at the beginning of the algorithm, store them all (using nested arrays) and then access them when needed. Computing \(LCC_{H^{-y_1-y_2-y_3}}(x)\) and \(LCC_{H^{-y_1-y_2-y_3-a}}(x)\) for all possibilities of \(y_1,y_2,y_3,a,x\) is done in time \(O(n^5m^2)\), so the final running time is \(O(n^5m^2+n^6\Delta)\). ◻

Proof. The statement for nunchakus is a direct corollary of Lemma [lemma95forest]. The statement for necklaces ensues since applying the reduction from Proposition [prop95reduction], which clearly preserves \(\tau_M\), gives the same hypergraph for both (recall Figure 14). ◻

Proof of Theorem [theo95main95duration] assuming Lemma [lemma95main95structure]. Suppose that \(H\) is a Maker win. By Theorem [theo95main95structure1], Maker has a strategy ensuring that, after three rounds of play with successive picks \(x_1,y_1,x_2,y_2,x_3,y_3\), there is a fully marked edge, a nunchaku or a necklace in \(H^{+x_1-y_1+x_2-y_2+x_3-y_3}\). By Proposition [prop95subwin] (Subhypergraph Monotonicity), to conclude the proof, it suffices to show that any nunchaku or necklace \(N\) in \(H^{+x_1-y_1+x_2-y_2+x_3-y_3}\) satisfies \(\tau_M(N) \leq \lceil \log_2(|V(H) \setminus M(H)|-5)\rceil\).

• A nunchaku \(N\) is of length \(\frac{|V(N)|-1}{2}\), so it satisfies \(\tau_M(N)=1+\mathopen{}\mathclose{\left\lceil \log_2 \mathopen{}\mathclose{\left(\frac{|V(N)|-1}{2}}\right) }\right\rceil = \lceil \log_2(|V(N)|-1) \rceil\) by Lemma [lemma95duration]. Moreover, a nunchaku \(N\) in \(H^{+x_1-y_1+x_2-y_2+x_3-y_3}\) has two marked vertices and all its other vertices are in \(V(H) \setminus (M(H) \cup \{x_1,y_1,x_2,y_2,x_3,y_3\})\), so it satisfies \(|V(N)|\leq 2+(|V(H) \setminus M(H)|-6)\) hence \(\tau_M(N) \leq \lceil \log_2(|V(H) \setminus M(H)|-5)\rceil\).

• A necklace \(N\) is of length \(\frac{|V(N)|}{2}\), so it satisfies \(\tau_M(N)= \lceil \log_2(|V(N)|) \rceil\) by Lemma [lemma95duration]. Moreover, a necklace \(N\) in \(H^{+x_1-y_1+x_2-y_2+x_3-y_3}\) has one marked vertex and all its other vertices are in \(V(H) \setminus (M(H) \cup \{x_1,y_1,x_2,y_2,x_3,y_3\})\), so it satisfies \(|V(N)|\leq 1+(|V(H) \setminus M(H)|-6)\) hence \(\tau_M(N) \leq \lceil \log_2(|V(H) \setminus M(H)|-5)\rceil\).

 ◻

Proof. This is given by Propositions [prop95nomarkedvertex] and [prop95degree1]. ◻

Proof. Since \(J(\mathcal{D}_1,H)\) holds and \(m \not\in V(D)\), Union Lemma [Lemma5] with \(c=m\) ensures that \(D \cup P_m\) contains an \(m\)-tadpole or an \(mx\)-chain (i.e., an \(xm\)-snake). There cannot be an \(m\)-tadpole in \(H\) according to Proposition [prop95markedvertex], therefore \(D \cup P_m\) contains an \(xm\)-snake. Since \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_1(H)}\right)\), that \(xm\)-snake must contain \(y\), moreover \(y \not\in V(D)\) by assumption so \(y \in V(P_m)\). ◻

Proof. Since \(J(\mathcal{D}_1,H)\) holds, we have \(I_{H^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(H)}\right) \neq \varnothing\), so Union Lemma [Lemma6] ensures that \(D \cup P_x\) contains an \(x\)-tadpole or an \(x\)-snake. In both cases, it contains \(y\), moreover \(y \not\in V(D)\) by assumption, so \(y \in V(P_x)\). ◻

Proof. The fact that \(\mathrm{dist}_H(v,m)\geq\mathrm{dist}_H(y,m)\) is a direct consequence of Proposition [prop95chemin1]: since \(v \in V(D)\), any \(vm\)-snake in \(H\) contains \(y\).

• Suppose \(\mathrm{dist}_H(v,m)>\mathrm{dist}_H(y,m)\).
  Let \(S_{ym}\) be a shortest \(ym\)-snake in \(H\): note that there does exist one, since there exists an \(xm\)-snake by assumption, which must contain \(y\) and therefore contains a \(ym\)-snake by Substructure Lemma [lemma95subchain1]. Since \(S_{ym}\) is shortest and \(\mathrm{dist}_H(v,m)>\mathrm{dist}_H(y,m)\), we have \(v \not\in V(S_{ym})\).
  We necessarily have \(v \not\in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_1(H)}\right)\), otherwise the fact that \(\mathrm{dist}_H(v,m)>\mathrm{dist}_H(y,m)\) would contradict our choice of \(y\). Since \(v\) is non-marked (recall that \(M(D)=\varnothing\)) and distinct from \(x\), this means there exists some \(X \in x\mathcal{D}_1(H)\) such that \(v \not\in V(X)\). On the other hand, since \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_1(H)}\right)\), we have \(y \in V(X)\) hence \(y \in V(X) \cap V(S_{ym})\). This allows us, thanks to an adequate union lemma in \(X \cup S_{ym}\), to find the desired \(xm\)-snake \(S_{xm}^{\overline{v}}\) (ensuring that \(v \not\in V(S_{xm}^{\overline{v}})\) since \(v \not\in V(X) \cup V(S_{ym})\)):

  • Suppose \(X\) is an \(x\)-snake, and write \(X=S\). If the marked vertex of \(S\) is \(m\), then we define \(S_{xm}^{\overline{v}} = S\) as the desired \(xm\)-snake. Otherwise \(m \not\in V(S)\), so apply Union Lemma [Lemma4] with \(a=x\), \(S_{ab}=S\), \(c=m\) and \(P_c=S_{ym}\). Since \(S \cup S_{ym} \subseteq H\) cannot contain an \(m\)-snake by Proposition [prop95markedvertex], it contains an \(mx\)-chain, i.e., an \(xm\)-snake \(S_{xm}^{\overline{v}}\).

  • Suppose \(X\) is an \(x\)-tadpole, and write \(X=T\). We have \(M(T)=\varnothing\) hence \(m \not\in V(T)\), so apply Union Lemma [Lemma3] with \(a=x\), \(c=m\) and \(P_c=S_{ym}\). Since \(T \cup S_{ym} \subseteq H\) cannot contain an \(m\)-tadpole by Proposition [prop95markedvertex], it contains an \(mx\)-chain, i.e., an \(xm\)-snake \(S_{xm}^{\overline{v}}\).

• Suppose \(\mathrm{dist}_H(v,m)=\mathrm{dist}_H(y,m)\).
  Let \(S_{vm}\) be a shortest \(vm\)-snake in \(H\). Since \(v \in V(D)\), we have \(y \in V(S_{vm})\) by Proposition [prop95chemin1]. If \(y \neq o(v,\overrightarrow{vS_{vm}m})\) (see Figure 32, top), then \(S_{vm}\) contains a \(ym\)-snake that is shorter than \(S_{vm}\): this is impossible since \(\mathrm{dist}_H(v,m)=\mathrm{dist}_H(y,m)\) and \(S_{vm}\) has been chosen shortest. Therefore \(y = o(v,\overrightarrow{vS_{vm}m})\) (see Figure 32, bottom). The \(m\)-chain \(S_{vm}^{-y-v}\) does not contain \(y\) and thus contains no vertices in \(D\) by Proposition [prop95chemin1], hence why \(V(S_{vm}) \cap V(D)=\{v\}\). Finally, there cannot be a \(v\)-tadpole \(T\) in \(D\), because \(S_{vm} \cup T\) would then be an \(m\)-tadpole in \(H\) since \(V(S_{vm}) \cap V(T)=\{v\}\), contradicting Proposition [prop95markedvertex].

  

 ◻

Proof. Suppose for a contradiction that: \[\label{cont3} \text{All dm-snakes in H contain v.}\tag{3}\] We are going to exhibit an \(m\)-tadpole in \(H\), contradicting Proposition [prop95markedvertex]. This \(m\)-tadpole will be obtained inside the union of an \(xy\)-chain and an \(xm\)-snake having specific properties, whose existence is given by the following two claims which we prove independently from each other. Define \(t = o(x,\overrightarrow{xP_{dx}^{\overline{v}}d})\), and note that \(\mathrm{start}(\overrightarrow{xP_{dx}^{\overline{v}}d})=e_x\) since \(e_x\) is the only edge incident to \(x\) in \(D\).

Proof of Claim [claim95exclusion1]. We have \(\mathrm{dist}_H(v,m)>\mathrm{dist}_H(y,m)\) by assumption, so by Lemma [lemma95dist] there exists an \(xm\)-snake \(S_{xm}^{\overline{v}}\) in \(H\) that does not contain \(v\). Since \(P_{dx}^{\overline{v}} \subseteq D\) and \(m \not\in V(D)\), the edge \(e^* = \mathrm{end}(\overrightarrow{m\mathbf{P}_{V(P_{dx}^{\overline{v}})}(m,S_{xm}^{\overline{v}})})\) is well defined. According to (3 ), there are no \(dm\)-snakes in \(P_{dx}^{\overline{v}} \cup S_{xm}^{\overline{v}}\). Therefore, by Union Lemma [Lemma1] applied to \(a=d\), \(b=x\), \(c=m\), \(P_{ab}=P_{dx}^{\overline{v}}\) and \(P_c=S_{xm}^{\overline{v}}\): \(|e^* \cap V(P_{dx}^{\overline{v}})|=2\), \(e^* \perp \overleftarrow{xP_{dx}^{\overline{v}}d}\), moreover there is an \(x\)-tadpole \(T\) in \(P_{dx}^{\overline{v}} \cup e^*\). Since \(|e^* \cap V(P_{dx}^{\overline{v}})|=2\), there is exactly one vertex of \(T\) that is not in \(P_{dx}^{\overline{v}}\). That vertex is necessarily \(y\), as illustrated in Figure 33: indeed, we know \(y \in V(T)\) because \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_1(H)}\right)\), and \(y \not\in V(D) \supseteq V(P_{dx}^{\overline{v}})\). By Substructure Lemma [lemma95subchain4bis], \(T\) contains an \(xy\)-chain \(P_{xy}^{\overline{v}}\), and we have \(V(P_{xy}^{\overline{v}}) \subseteq V(T) \subseteq V(P_{dx}^{\overline{v}}) \cup \{y\}\). See Figure 33.

Finally, let us check that \(o(x,\overrightarrow{xP_{xy}^{\overline{v}}y})=t\). Since \(|e^* \cap V(P_{dx}^{\overline{v}})|=2\) and \(e^* \perp \overleftarrow{xP_{dx}^{\overline{v}}d}\), there are two possibilities:

• First case: \(\{x,t\} \subseteq e^*\). Then \(P_{xy}^{\overline{v}}\) consists of the single edge \(e^*=\{x,t,y\}\), so obviously \(o(x,\overrightarrow{xP_{xy}^{\overline{v}}y})=t\).

• Second case: \(\{x,t\} \cap e^* = \varnothing\). Then \(\mathrm{start}(\overrightarrow{xP_{xy}^{\overline{v}}y}) \neq e^*\), so \(\mathrm{start}(\overrightarrow{xP_{xy}^{\overline{v}}y})=\mathrm{start}(\overrightarrow{xP_{dx}^{\overline{v}}d})=e_x \ni t\). Moreover \(t\) is of degree 1 in \(P_{dx}^{\overline{v}} \cup e^* \supseteq P_{xy}^{\overline{v}}\), so necessarily \(t \not\in \mathrm{inn}(P_{xy}^{\overline{v}})\) hence \(t=o(x,\overrightarrow{xP_{xy}^{\overline{v}}y})\).

 ◻

Proof of Claim [claim95exclusion2]. It is impossible that \(\mathrm{dist}_H(t,m)=\mathrm{dist}_H(y,m)\): indeed, a shortest \(tm\)-snake \(S_{tm}\) in \(H\) would then satisfy \(V(S_{tm}) \cap V(D)=\{t\}\) by Lemma [lemma95dist], hence \(v \not\in V(S_{tm})\), so the walk \(\overrightarrow{dP_{dx}^{\overline{v}}t} \oplus \overrightarrow{tS_{tm}m}\) would represent a \(dm\)-snake in \(H\) that does not contain \(v\), contradicting (3 ). Therefore, Lemma [lemma95dist] ensures that \(\mathrm{dist}_H(t,m)>\mathrm{dist}_H(y,m)\), and that there exists an \(xm\)-snake \(S_{xm}^{\overline{t}}\) in \(H\) such that \(t \not\in V(S_{xm}^{\overline{t}})\). Since \(y \in I_{H^{+x}}\mathopen{}\mathclose{\left(x\mathcal{D}_1(H)}\right)\), we obviously have \(y \in V(S_{xm}^{\overline{t}})\).
Write \(\overrightarrow{xS_{xm}^{\overline{t}}m}=(x,e_1,\ldots,e_L,m)\). Recalling Notation [notation95walk], write \(\overrightarrow{xS_{xm}^{\overline{t}}m}\vert_{\{y\}}=(x,e_1,\ldots,e_i)\) and \(\overleftarrow{xS_{xm}^{\overline{t}}m}\vert_{\{y\}}=(m,e_L,e_{L-1},\ldots,e_j)\). Note that \(j=i+1\) if \(y \in\mathrm{inn}(S_{xm}^{\overline{t}})\) and \(j=i\) otherwise.

• By definition of the walk \(\overleftarrow{xS_{xm}^{\overline{t}}m}\vert_{\{y\}}\), the \(m\)-chain \([(m,e_L,e_{L-1},\ldots,e_{j+1})]\) does not contain \(y\). Therefore, \((e_{j+1} \cup \ldots \cup e_L) \cap V(D)=\varnothing\) by Proposition [prop95chemin1].

• By definition of the walk \(\overrightarrow{xS_{xm}^{\overline{t}}m}\vert_{\{y\}}\), the \(x\)-chain \([(x,e_1,\ldots,e_{i-1})]\) does not contain \(y\). Moreover, \(e_1 \neq e_x\) because \(t \not\in V(S_{xm}^{\overline{t}}) \supseteq e_1\). Therefore, \((e_1 \cup \ldots \cup e_{i-1}) \cap (V(D) \setminus \{x\})=\varnothing\) by Proposition [prop95chemin2].

Suppose that \(y \not\in\mathrm{inn}(S_{xm}^{\overline{t}})\): then, \(i=j\) hence \(V(S_{xm}^{\overline{t}})=e_1 \cup \ldots \cup e_{i-1} \cup \{y\} \cup e_{j+1} \cup \ldots \cup e_L\). By the above, this yields \(V(S_{xm}^{\overline{t}}) \cap V(D)=\{x\}\) and in particular \(v \not\in V(S_{xm}^{\overline{t}})\), therefore the walk \(\overrightarrow{dP_{dx}^{\overline{v}}x} \oplus \overrightarrow{xS_{xm}^{\overline{t}}m}\) represents a \(dm\)-snake that does not contain \(v\). This contradicts (3 ).
Therefore, we have \(y \in \mathrm{inn}(S_{xm}^{\overline{t}})\). Let \(P_{xy}^{\overline{t}}\) (resp. \(S_{ym}^{\overline{t}}\)) be the unique \(xy\)-chain (resp. \(ym\)-snake) in \(S_{xm}^{\overline{t}}\), and define \(u = o(y,\overleftarrow{xP_{xy}^{\overline{t}}y})\) and \(u'= o(y,\overrightarrow{yS_{ym}^{\overline{t}}m})\), as in Figure 34. Since \(y \in \mathrm{inn}(S_{xm}^{\overline{t}})\), we have \(j=i+1\) hence \(V(S_{xm}^{\overline{t}})=e_1 \cup \ldots \cup e_{i-1} \cup \{u,y,u'\} \cup e_{j+1} \cup \ldots \cup e_L\). By the above, this yields \((V(S_{xm}^{\overline{t}}) \cap V(D)) \setminus \{x\} \subseteq \{u,u'\}\), hence \((V(S_{xm}^{\overline{t}}) \cap V(P_{dx}^{\overline{v}})) \setminus \{x\} \subseteq \{u,u'\}\).

Finally, it is impossible that \(u' \in V(P_{dx}^{\overline{v}})\): indeed, this would imply that \(V(S_{ym}^{\overline{t}}) \cap V(P_{dx}^{\overline{v}}) =\{u'\}\) and that \(u' \neq v\) hence \(v \not\in V(S_{ym}^{\overline{t}})\), so the walk \(\overrightarrow{dP_{dx}^{\overline{v}}x}\vert_{\{u'\}} \oplus \overrightarrow{u'S_{ym}^{\overline{t}}m}\) would represent a \(dm\)-snake not containing \(v\), contradicting (3 ). Therefore \((V(S_{xm}^{\overline{t}}) \cap V(P_{dx}^{\overline{v}})) \setminus \{x\} \subseteq \{u\}\), which concludes the proof of the claim. ◻

We can now conclude by exhibiting an \(m\)-tadpole in \(H\), which contradicts Proposition [prop95markedvertex] since \(H\) is not a trivial Maker win and \(J(\mathcal{D}_1,H)\) holds.
Let \(P_{xy}^{\overline{v}}\) be as in Claim [claim95exclusion1], and let \(S_{xm}^{\overline{t}}\), \(P_{xy}^{\overline{t}}\), \(S_{ym}^{\overline{t}}\), \(u\) be as in Claim [claim95exclusion2]. We have \(V(P_{xy}^{\overline{v}}) \subseteq V(P_{dx}^{\overline{v}}) \cup \{y\}\) by Claim [claim95exclusion1], and \((V(S_{xm}^{\overline{t}}) \cap V(P_{dx}^{\overline{v}})) \setminus \{x\} \subseteq \{u\}\) by Claim [claim95exclusion2]: therefore, \(V(S_{xm}^{\overline{t}}) \cap V(P_{xy}^{\overline{v}}) = \{x,y\}\) or \(V(S_{xm}^{\overline{t}}) \cap V(P_{xy}^{\overline{v}}) = \{x,y,u\}\).

• Case 1: \(V(S_{xm}^{\overline{t}}) \cap V(P_{xy}^{\overline{v}}) = \{x,y\}\). The walk \(\overleftarrow{yS_{ym}^{\overline{t}}m} \oplus \overleftarrow{xP_{xy}^{\overline{t}}y} \oplus \overrightarrow{xP_{xy}^{\overline{v}}y}\) clearly represents an \(m\)-tadpole (see Figure 35, top).

  

• Case 2: \(V(S_{xm}^{\overline{t}}) \cap V(P_{xy}^{\overline{v}}) = \{x,y,u\}\). Let \(e_u\) be the edge of \(S_{xm}^{\overline{t}}\) containing \(u\), and let \(P_{uy}\) be the unique \(uy\)-chain in \(P_{xy}^{\overline{v}}\). Since \(u \neq t\), we have \(x \not\in V(P_{uy})\), therefore the walk \(\overleftarrow{yS_{ym}^{\overline{t}}m} \oplus (y,e_u,u) \oplus \overrightarrow{uP_{uy}y}\) represents an \(m\)-tadpole (see Figure 35, bottom).

 ◻

Proof. Since all \(z\)-snakes in \(H\) contain \(s\), we can apply the contrapositive of Lemma [lemma95exclusion] with \(d=z\) and \(v=s\) (recall that \(s \not\in\{x,z\}\), so that Lemma [lemma95exclusion] indeed applies). We get that \(\mathrm{dist}_H(s,m) \leq \mathrm{dist}_H(y,m)\) or all \(zx\)-chains in \(D\) contain \(s\). We know the latter is false: a counterexample chain \(P^{\overline{s}}\) is given by Proposition [prop95s]. Therefore, we conclude that \(\mathrm{dist}_H(s,m) \leq \mathrm{dist}_H(y,m)\), hence \(\mathrm{dist}_H(s,m) = \mathrm{dist}_H(y,m)\) by Lemma [lemma95dist]. ◻

Proof. We have \(\mathrm{dist}_H(s,m) = \mathrm{dist}_H(y,m)\) by Corollary [coro95s], so there are no \(s\)-tadpoles in \(D\) according to Lemma [lemma95dist]. Let \(T\) be a \(z\)-tadpole in \(D\): we know \(s \in V(T)\) by definition of \(s\). If we had \(s \not\in \mathrm{out}(C_T)\), then there would be an \(s\)-tadpole in \(T \subseteq D\) by Substructure Lemma [lemma95subtadpole], therefore \(s \in \mathrm{out}(C_T)\). ◻

Proof. Suppose for a contradiction that there exists a \(z\)-cycle \(C\) of length 2 in \(D\). We have \(s \in \mathrm{out}(C)\) by Proposition [prop95s95bis]: write \(V(C)=\{z,s,a,b\}\) and \(E(C)=\{e_1,e_2\}\) where \(e_1=\{z,a,s\}\) and \(e_2=\{z,a,b\}\). By Proposition [prop95structure][item2], we know there exists some \(X^{\overline{a}} \in \mathcal{F}_D\) such that \(a \not\in V(X^{\overline{a}})\).

• First suppose \(s \in V(X^{\overline{a}})\). By Substructure Lemma [lemma95subchain1] (if \(X^{\overline{a}} \in \mathcal{P}_{zx}\)) or Substructure Lemma [lemma95subchain4bis] (if \(X^{\overline{a}} \in \mathcal{T}_z\)), there exists a \(zs\)-chain \(P_{zs}\) in \(X^{\overline{a}}\). Since \(a \not\in V(P_{zs})\), we get an \(s\)-cycle \(P_{zs} \cup e_1\) in \(D\), contradicting Proposition [prop95s95bis].

• Now suppose \(s \not\in V(X^{\overline{a}})\). Since \(s \in I_{H^{+z}}\mathopen{}\mathclose{\left(z\mathcal{D}_1(H)}\right)\), this implies that \(X^{\overline{a}} \in \mathcal{P}_{zx}\). Write \(X^{\overline{a}} = P\). If \(b \not\in V(P)\), then \(V(C) \cap V(P)=\{z\}\), therefore \(P \cup C\) is an \(x\)-tadpole in \(D\), contradicting Proposition [prop95structure][item6]. If \(b \in V(P)\), then there exists a \(zb\)-chain \(P_{zb}\) in \(P\) by Substructure Lemma [lemma95subchain1], and we get a \(z\)-cycle \(P_{zb} \cup e_2\) in \(D\) that does not contain \(s\), also a contradiction.

 ◻

Proof of Proposition [prop95roadmap]. Let \(w \in V(D)\setminus \{x\}\) be such that \(D\) contains the following three subhypergraphs:

1. a \(z\)-cycle \(C\) containing \(w\);

2. an \(xw\)-chain \(P_{xw}\) such that \(V(P_{xw}) \cap \mathrm{inn}(C) \subseteq \{w\}\);

3. a \(w\)-tadpole \(T\) that does not contain \(s\).

We are going to consider \(C\), \(P_{xw}\) and \(T\) successively. Each of these three objects will imply the existence of some \(\mathcal{D}_1\)-dangers at \(w\), which will improve our upper bound on \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right)\) (with respect to set inclusion) until we get the desired conclusion that \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right)=\varnothing\).

1. Step 1: we show that \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) \subseteq \mathrm{inn}(C) \cup \{s\} \cup (V(H) \setminus V(D))\).
   In this step, we use \(C\). Recall that \(s \in \mathrm{out}(C)\) by Proposition [prop95s95bis] and that \(C\) is of length at least 3 by Proposition [prop95nodiamond].

   For all \(ws\)-chains \(P_{ws}\) in \(C\): \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) \subseteq (V(P_{ws}) \setminus \{w\}) \cup (V(H) \setminus V(D))\).

   Proof of Claim [claim95roadmap]. We know \(\mathrm{dist}_H(s,m)=\mathrm{dist}_H(y,m)\) by Corollary [coro95s]. Let \(S_{sm}\) be a shortest \(sm\)-snake in \(H\): Lemma [lemma95dist] thus ensures that \(V(S_{sm}) \cap V(D)=\{s\}\) hence \(V(S_{sm}) \cap V(C)=\{s\}\). Therefore, any \(ws\)-chain \(P_{ws}\) in \(C\) yields a \(wm\)-snake \(S_{wm} = P_{ws} \cup S_{sm}\) in \(H\) and: \[\begin{align} I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) & \subseteq V(S_{wm}) \setminus \{w\} \\ & \subseteq (V(P_{ws}) \setminus \{w\}) \cup (V(S_{sm}) \setminus \{s\}) \\ & \subseteq (V(P_{ws}) \setminus \{w\}) \cup (V(H) \setminus V(D)). \qedhere \end{align}\] ◻

   We know there exists a \(ws\)-chain in \(C\) by Substructure Lemma [lemma95subchain3bis], so Claim [claim95roadmap] ensures that \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) \subseteq (V(C) \setminus \{w\}) \cup (V(H) \setminus V(D))\). Moreover, for all \(v \in \mathrm{out}(C) \setminus \{w,s\}\), there exists a \(ws\)-chain in \(C\) that does not contain \(v\) by Substructure Lemma [lemma95subchain3], so \(v \not\in I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right)\) by Claim [claim95roadmap]. All in all, we get \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) \subseteq \mathrm{inn}(C) \cup \{s\} \cup (V(H) \setminus V(D))\), which concludes Step 1.

2. Step 2: we show that \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) \subseteq \{s\} \cup (V(H) \setminus V(D))\).
   In this step, we use \(P_{xw}\). Comparing with Step 1, we need to show that \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right)\) is disjoint from \(\mathrm{inn}(C)\). Let \(v \in \mathrm{inn}(C)\). If \(v=w\), then obviously \(v \not\in I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right)\), so assume \(v \neq w\). By definition of \(P_{xw}\), we have \(V(P_{xw}) \cap \mathrm{inn}(C) \subseteq \{w\}\), so \(v \not\in V(P_{xw})\). Lemma [lemma95exclusion] thus applies with: \(d=w\), our vertex \(v\), and \(P_{dx}=P_{xw}\). We get a \(wm\)-snake in \(H\) that does not contain \(v\), hence \(v \not\in I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right)\), which concludes Step 2.

3. Step 3: we show that \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) = \varnothing\).
   In this step, we use \(T\). We already know that \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) \subseteq \{s\} \cup (V(H) \setminus V(D))\). Moreover, \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) \subseteq V(T)\) because \(T\) is a \(w\)-tadpole, where \(V(T)\) is disjoint from \(\{s\} \cup (V(H) \setminus V(D))\) by definition. In conclusion, \(I_{H^{+w}}\mathopen{}\mathclose{\left(w\mathcal{D}_1(H)}\right) = \varnothing\).

 ◻

Proof of Claim [claim95Type2]. Suppose for a contradiction that \(w,w' \in \mathrm{inn}(C)\). Write \(\overrightarrow{zC}=(z,e_1,\ldots,e_L,z)\). Since \(L \geq 3\) and \(w,w' \in \mathrm{inn}(C) \setminus \{z\}\), there exist \(1 \leq i \neq i' \leq L-1\) such that \(e_i \cap e_{i+1}=\{w\}\) and \(e_{i'} \cap e_{i'+1}=\{w'\}\). Since \(w\) and \(w'\) have symmetrical roles, assume \(i<i'\). Let \(1 \leq j \leq L\) be the unique index such that \(s \in e_j\).
Since \(e_1\) and \(e_L\) are the only edges of \(C\) containing \(z\), the \(ww'\)-chain represented by the walk \((w, e_{i+1}, ..., e_{i'}, w')\) does not contain \(z\), so it is necessarily \(P_{ww'}\) according to the uniqueness statement of Substructure Lemma [lemma95subchain3]. Since \(s \not\in V(P_{ww'})\), this yields \(1 \leq j \leq i\) or \(i'+1 \leq j \leq L\): by symmetry, assume \(i'+1 \leq j \leq L\). Then \((z,e_1,\ldots,e_i,w) \oplus \overrightarrow{wP_{ww'}w'} \oplus (w',e^*,w)\) represents a \(z\)-tadpole not containing \(e_j\), i.e., not containing \(s\), a contradiction which concludes the proof of the claim. ◻

Proof of Claim [claim95Type1]. Since \(V(X) \cap V(P_{xw}) \neq \varnothing\), the projection \(\mathbf{P}_{V(P_{xw})}(z,X)\) is well defined. There are no \(x\)-tadpoles in \(D \supseteq P_{xw} \cup \mathbf{P}_{V(P_{xw})}(z,X)\) by Proposition [prop95structure][item6], so Union Lemma [Lemma1] with \(a=w\), \(b=x\) and \(c=z\) ensures that \(P_{xw} \cup \mathbf{P}_{V(P_{xw})}(z,X)\) contains a \(wz\)-chain \(P_{wz}\). Now, since \(V(P_{wz}) \cap (V(C) \setminus \{w\}) \supseteq \{z\} \neq \varnothing\), the projection \(P_w = \mathbf{P}_{V(C) \setminus \{w\}}(w,P_{wz})\) is well defined.
Define \(e^* =\mathrm{end}(\overrightarrow{wP_w})\): by definition of a projection, the edge \(e^*\) is the only edge of \(P_w\) that intersects \(V(C) \setminus \{w\}\), and \(|e^* \cap (V(C) \setminus \{w\})| \in \{1,2\}\), hence item [item95a].
Since \(P_w \subseteq P_{wz} \subseteq X \cup P_{xw}\), where \(\{w_1,w_2\} \not\subseteq V(X)\) by definition of \(X\) and \(\{w_1,w_2\}\cap V(P_{xw})=\varnothing\), we have \(\{w_1,w_2\} \not\subseteq V(P_w)\), i.e., item [item95b].
Finally, suppose for a contradiction that \(s \in V(P_w)\):

• First suppose \(s=w\). By Substructure Lemma [lemma95subchain2], \(C^{-s}\) is a \(w_1w_2\)-chain. By Union Lemma [Lemma1] with \(a=w_1\), \(b=w_2\) and \(c=w=s\), \(C^{-s} \cup P_w\) contains an \(sw_1\)-chain or an \(sw_2\)-chain. Take a shortest \(sw_1\)-chain or \(sw_2\)-chain in \(C^{-s} \cup P_w\): by symmetry, assume it is an \(sw_1\)-chain \(P_{sw_1}\). The minimality of the length ensures that either \(w_2 \not\in V(P_{sw_1})\) or \(w_2 = o(w_1,\overleftarrow{sP_{sw_1}w_1})\).

  • If \(w_2 \not\in V(P_{sw_1})\), then \(P_{sw_1} \cup e\) is an \(s\)-cycle in \(D\), contradicting Proposition [prop95s95bis].

  • If \(w_2 = o(w_1,\overleftarrow{sP_{sw_1}w_1})\), then \(\mathrm{end}(\overrightarrow{sP_{sw_1}w_1})\) is an edge of \(C^{-s} \cup P_w\) containing both \(w_1\) and \(w_2\). However, there are no such edges in \(C^{-s}\) because \(C^{-s}\) is a \(w_1w_2\)-chain of length at least 2 (indeed, recall that \(C\) is of length at least 3), and there are no such edges in \(P_w\) because \(\{w_1,w_2\} \not\subseteq V(P_w)\) by item [item95b]. We have a contradiction.

• Now suppose \(s \neq w\). By item [item95a], \(e^* = \mathrm{end}(\overrightarrow{wP_w})\) is the only edge of \(P_w\) that intersects \(V(C) \setminus \{w\}\), so \(P_w\) is a \(ws\)-chain and either \(V(P_w) \cap V(C)=\{w,s\}\) or \(V(P_w) \cap V(C) = \{w,s,o(s,\overrightarrow{sP_ww})\}\).

  • If \(V(P_w) \cap V(C)=\{w,s\}\), then let \(P_{ws}\) be a \(ws\)-chain in \(C\) (which exists by Substructure Lemma [lemma95subchain3bis]): since \(P_w\) and \(P_{ws}\) are both \(ws\)-chains and \(V(P_w) \cap V(P_{ws})=\{w,s\}\), we get an \(s\)-cycle \(P_w \cup P_{ws}\), contradicting Proposition [prop95s95bis].

  • If \(V(P_w) \cap V(C) = \{w,s,t\}\), where we have defined \(t =o(s,\overrightarrow{sP_ww}) \in e^*\), then let \(P_{st}\) be an \(st\)-chain in \(C\) that does not contain \(w\) (which exists by Substructure Lemma [lemma95subchain3] because \(w \in \mathrm{out}(C)\)): since \(V(P_{st}) \cap e^* = \{s,t\}\), we get an \(s\)-cycle \(P_{st} \cup e^*\), contradicting Proposition [prop95s95bis].

We have a contradiction in all cases, hence item [item95c]. ◻