Proof. The claim holds for \(i=0\) because \(G_0 = G\), \(G'_0 = G'\). Let \(i\geq 0\) and suppose that \(\varphi \in \mathrm{Hom}(G_{i-1}, G'_{i-1})\). Let \(e\in E(G_i)\setminus E(G_{i-1})\). Therefore there exists a copy \(H_i \subseteq G_i\) of \(H\) in \(G_i\) such that \(H_i - e \subseteq G_{i-1}\). We have \(\varphi(H_i) - \varphi(e) = \varphi(H_i-e)\) because \(\varphi\) is injective, and \(\varphi(H_i-e) \subseteq G'_{i-1}\) since \(\varphi \in \mathrm{Hom}(G_{i-1}, G'_{i-1})\). Thus, \(\varphi(e) \in E(G'_i)\) by definition of the \(H\)-process on \(G'\). ◻

Proof. Suppose that at some step in the process the number of components decreases. Take the smallest \(i\) for which there exists an edge \(e\in E(G_i)\) whose endpoints lie in distinct components of \(G\). At time \(i-1\) there must be path of length \(k-1\) between the endpoints of \(e\), a contradiction. ◻

Proof. Let \((G_i)_{i\geq 0}\) be the \(C_k\)-process on \(G\), and suppose for a contradiction that the final graph was not bipartite. Pick the smallest \(i\) for which \(G_i\) contains an edge \(e\) whose endpoints lie in the same part. Then there exists a path of length \(k-1\) between the endpoints of \(e\) at time \(i-1\), a contradiction as \(k-1\) is odd. ◻

Proof. Let \(( G_i)_{i\geq 0}\) be the \(C_k\)-process on \(G\). Since \(\tau_{C_k}( G) \neq 0\), there exists a \(k\)-cycle \(C\) in \(G_1\). Let \(x \in V( G)\setminus V(C)\), and let \(Q\) be a shortest path from \(x\) to \(V(C)\) in \(G_1\). If \(Q\) has length at least \(k-1\) the first \(k\) vertices of \(Q\) starting from \(x\) form a path of length \(k-1\) with endpoint \(x\). If the length of \(Q\) is smaller than \(k-1\) we can extend \(Q\) to a path of length \(k-1\) using vertices along \(C\). In either case, the vertices of this path of length \(k-1\), one of which is \(x\), form a \(k\)-cycle in \(G_2\). ◻

Proof. Let \(G := K_{\floor{k/2},\ceil{k/2}} + \{ zz' \}\) and denote the partite sets of \(K_{\floor{k/2},\ceil{k/2}}\) by \(X\) and \(Y\) such that \(|X| = \ceil{k/2}\) and \(|Y| = \floor{k/2}\). If \(k\) is odd, then for any two distinct \(x,x'\in X\) we can find a Hamilton path, which has length \(k-1\), from \(x\) to \(x'\) in \(K_{\floor{k/2},\ceil{k/2}}\). Thus \(X\) is a clique after one step in the \(C_k\)-process on \(G\). At time \(1\), \(X \setminus \{ x \}\) and \(Y\cup \{ x \}\) are partite sets of a complete bipartite graph of size \(\floor{k/2}\) and \(\ceil{k/2}\), respectively. Therefore \(Y \cup \{ x \}\) is a clique at time \(2\). This shows the claim for odd \(k\). Now assume that \(k\) is even, in particular, \(k \geq 4\) so both \(|X|\geq 2\) and \(|Y|\geq 2\). Since \(|X| = |Y|\) we may further assume that \(z,z'\in X\). For any distinct \(y,y'\in Y\) we can pick a Hamilton path from \(y\) to \(z\) in the complete bipartite graph \(G-y'-z'\) and extend that path to a \(yy'\)-path of length \(k-1\) in \(G\) by \(zz'\) and \(z'y'\). Then \(Y\) must be a clique at time \(1\). Analogous arguments show that \(X\) is a clique after one more step and hence the claim follows. ◻

Proof. In \(\final{ G}_{C_k}\) the endpoints of any path of length \(k-1\) are adjacent. Therefore the shortest path between any two vertices has length less than \(k-1\). Choose vertices \(v_j\), \(j\in [0,k-1]\), in \(G\) that form a \(k\)-cycle \(C\) with edges \(v_jv_{j+1}\). Here and for the rest of this proof addition and subtraction in the subscript are always performed modulo \(k-1\). Every \(x\in V( G)\setminus\{ v_0,\ldots,v_{k-1} \}\) has a neighbour on \(C\) in \(\final{ G}_{C_k}\) because a shortest path from \(x\) to \(C\) in \(G\) can always be extended to a path of length \(k-1\) by vertices of \(C\). If \(xv_j \in E(\final{ G}_{C_k})\) then \(xv_jv_{j-1}\ldots v_{j+2}\) is a path of length \(k-1\) so \(xv_{j+2} \in E(\final{ G}_{C_k})\). In the case that \(k\) is odd the above implies that every vertex of \(C\) is adjacent to every other vertex of \(G\) in \(\final{ G}_{C_k}\). Thus for any two distinct vertices \(x,y\in V(G)\) we can find a \(k\)-cycle containing \(x\) but not \(y\). Indeed if both \(x\) and \(y\) lie on \(C\) we can replace \(y\) by a vertex not on \(C\) to obtain the desired cycle. In the case that neither \(x\) nor \(y\) is a vertex of \(C\) we can replace an arbitrary vertex of \(C\) by \(x\). Repeating the above argument for such a cycle gives \(xy \in E(\final{ G}_{C_k})\).

Now assume that \(k\) is even. Let \[X := \{ v_j : j\equiv 0 \mod 2 \} \qquad,\qquad Y := \{ v_j : j\equiv 1 \mod 2 \}.\] Then every vertex outside \(C\) is adjacent in \(\final{{G}}_{C_k}\) to all vertices in \(X\) or all vertices in \(Y\). Define \[X' := \left\lbrace z \in V( G)\setminus V(C) : Y \subseteq N_{\final{ G}_{C_k}}(z) \right\rbrace \qquad,\qquad Y' := \left\lbrace z \in V( G)\setminus V(C) : X \subseteq N_{\final{ G}_{C_k}}(z) \right\rbrace .\] One of these two sets, say \(X'\), must be non-empty. For any \(x\in X'\), \(y\in Y'\), \(yv_0v_1\ldots v_{k-3} x\) is an \(xy\)-path of length \(k-1\) in \(\final{ G}_{C_k}\). Furthermore for any \(j, j' \in [0,k-1]\), with \(v_j\in X\), \(v_{j'}\in Y\setminus\{v_{j-1},v_{j+1}\}\) and any \(x\in X'\) \[v_{j'}v_{j'+1}\ldots v_{j-1} x v_{j'-2}\ldots v_{j+1}v_j\] is an \(v_jv_{j'}\)-path of length \(k-1\). Therefore \(\final{ G}_{C_k}\) contains a complete bipartite graph whose partite sets are \(X\cup X'\) and \(Y\cup Y'\). If \(G\) is bipartite we are done by Lemma 7. Otherwise the claim follows from Lemma 9. ◻

Proof. Observe that for any edge \(e\in E(G_i)\setminus E(G_{i-1})\) one can find a path of length \(k-1\) between its endpoints in \(G_{i-1}\). Given a shortest \(xy\)-path in \(G_i\), replacing every edge on the path which is not present at time \(i-1\) by a suitable path of length \(k-1\) yields an \(xy\)-walk of length at most \((k-1)\cdot\mathop{\mathrm{dist}}_{G_i}(x,y)\) in \(G_{i-1}\). From this we deduce that \(\mathop{\mathrm{dist}}_{G_{i-1}}(x,y) \leq (k-1) \mathop{\mathrm{dist}}_{G_i}(x,y)\) and thus \(\mathop{\mathrm{dist}}_{G_0}(x,y) \leq (k-1)^i \mathop{\mathrm{dist}}_{G_i}(x,y)\), which gives the lower bound in ?? . To obtain the upper bound on \(\mathop{\mathrm{dist}}_{G_i}(x,y)\), write \(\mathop{\mathrm{dist}}_{G_{i-1}}(x,y) = q\cdot (k-1) +r\) for suitable \(q,r\in\mathbb{N}_0\), \(0\leq r \leq k-2\), and choose a path \(u_0\ldots u_{q(k-1)+r}\) from \(x\) to \(y\) in \(G_{i-1}\). In \(G_i\), \(u_0u_{k-1}\ldots u_{q(k-1)}u_{q(k-1)+1}\ldots u_{q(k-1)+r}\) is a path of length \(q+r\) from \(x\) to \(y\). Since \(r\leq k-2\), we obtain

We can bound the left hand side by just \(q\) whenever \(\mathop{\mathrm{dist}}_{G_i}(x,y)\) is divisible by \(k-1\). An inductive application of 4 yields the claim. ◻

Proof of Theorem 2. We begin by proving the upper bound. We assume that \(n\) is sufficiently large so that Theorem 12 holds and so that \(r(n,k)\geq \binom{k}{2}\). Therefore we have that any \(k\)-vertex graph \(G\) stabilises in at most \(r\) steps and so 3 tells us that we can restrict ourselves to connected starting graphs on at most \(n\) and at least \(k+1\) vertices. When \(k\) is odd or the starting graph is non-bipartite, then the desired upper bound follows from parts [upperpart1] and [upperpart3] of Theorem 12, which state that by round \(r\) our process reaches the complete graph, which is \(C_k\)-stable. If \(k\) is even and the starting graph is bipartite with parts \(X\) and \(Y\), then part [upperpart2] tells us that at time \(r\) there is a complete bipartite graph between \(X\) and \(Y\), which by Lemma 7 must be the final graph of the process. To obtain the lower bounds observe that \(\ell \leq n-3\) for even \(k\) by definition of \(\ell\) and \(r\) and that the edges specified in parts [lowerpart1] and [lowerpart2] of Theorem 13 are not present at time \(r-1\), but will be added eventually by Theorem 12 (in fact in the next step). So the process is not finished after \(r-1\) steps. ◻

Proof. We prove the claim by induction on \(i\geq 0\).

\(i=0\): By definition all edges in \(P^0\) are of the form \(\{ x, x+1 \}\).

\(i\geq 1\): Let \(xy\in E(P^i)\). If \(xy\) was already present at time \(i-1\), the induction hypothesis and the inclusion \(A_{i-1} \subseteq A_i\) give \(y-x \in A_i\). Suppose \(xy\notin E(P^{i-1})\). Let \(v_0,\ldots,v_{k-1}\) be a path from \(v_0 := x\) to \(v_{k-1} := y\) in \(P^{i-1}\). By the induction hypothesis there exist \(\alpha_1,\ldots,\alpha_{k-1},\beta_1,\ldots,\beta_{k-1}\) such that \(v_j-v_{j-1} = (k-1)^{i-1}-\alpha_j\cdot(k-2) - \beta_j\cdot k\) for \(j\in[k-1]\). Then \[y-x = \sum_{j=1}^{k-1} v_j-v_{j-1} = \sum_{j=1}^{k-1} \left( (k-1)^{i-1}-\alpha_j\cdot(k-2) - \beta_j\cdot k\right) = (k-1)^i - \sum_{j=1}^{k-1} \alpha_j\cdot (k-2) - \sum_{j=1}^{k-1} \beta_j\cdot k,\] completing the inductive step. ◻

Proof. The only even edge in \(P^{\Delta,0}\) is \(v_0w_0\) so the claim holds for \(i=0\). Let \(i\geq 1\) and suppose the claim holds for \(i-1\). Since \((k-1)^i-1 > (k-1)^{i-1} -1\) it suffices to show that whenever \(v_j\) or \(w_j\) is the endpoint of an even edge in \(E(P^{\Delta,i})\setminus E(P^{\Delta,i-1})\) one has \(j \leq (k-1)^i-1\). Let \(u_{j_0}u_{j_{k-1}}\) be an even edge in \(E(P^{\Delta,i})\setminus E(P^{\Delta,i-1})\) and let \(u_{j_0}\ldots u_{j_{k-1}}\) be a path in \(P^{\Delta,i-1}\) such that \(u_{j_t} \in \{ v_{j_t},w_{j_t} \}\) for \(0 \leq t \leq k-1\). For parity reasons there exists at least one even edge on that path. Let \(s\in [k-1]\) such that \(j_s-j_{s-1} \equiv 0 \mod 2\). The first part of Lemma 11 gives \[\mathop{\mathrm{dist}}_{P^{\Delta}}(u_{j_t}, u_{j_{t-1}}) \leq (k-1)^{i-1} \mathop{\mathrm{dist}}_{P^{\Delta,i-1}}(u_{j_t}, u_{j_{t-1}}) = (k-1)^{i-1}\] for \(s+1 \leq t \leq k-1\). In \(P^\Delta\) we have \(\mathop{\mathrm{dist}}_{P^{\Delta}}(u_{j_t}, u_{j_{t-1}}) = |j_t - j_{t-1}|\). Now the inductive hypothesis implies \[j_{k-1} = j_s + \sum_{t=s+1}^{k-1} j_t - j_{t-1} \leq (k-1)^{i-1} - 1 + (k-1-s) \cdot (k-1)^{i-1} \leq (k-1)^i - 1.\] ◻

Proof. We induct on \(i\) with \(i\in\{ 1,2 \}\) being our base cases.

\(i=1\): Any path of length \(k-1\) in \(P^{\Delta, 0}\) whose endpoints form an odd edge in \(P^{\Delta,1}\) must not use \(v_0w_0\) because of parity, and thus misses at least one of \(v_0\),\(w_0\). This implies \(j-j' \in \{ -(k-1),-1,1,(k-1) \} \subseteq A_1\) (cf. base case of Lemma 14).

\(i=2\): If \(u_ju_{j'}\) is present at time \(1\) we are done because \(A_1 \subseteq A_2\) and \(j-j'\in A_1\) by the induction hypothesis. Suppose that the edge does not lie in \(E(P^{\Delta,1})\). Let \(Q = u_{j_0}\ldots u_{j_{k-1}}\) be a path in \(P^{\Delta,1}\) with \(j_0 = j'\), \(j_{k-1} = j\) and \(u_{j_t} \in \{ v_{j_t},w_{j_t} \}\) for \(1 \leq t \leq k-2\). There has to be an even number of even edges in \(Q\) because \(j-j'\) is odd and \(Q\) has odd length, and there cannot be more than two because the only even edges of \(P^{\Delta,1}\) are \(v_0w_0\), \(v_0v_{k-2}\) and \(w_0v_{k-2}\). If all edges of \(Q\) are odd we proceed as in the inductive step of Lemma 14. Otherwise there are precisely two even edges on \(Q\). These two edges must share a common endpoint considering that the even edges in \(P^{\Delta,1}\) form a triangle. Let \(s\in [k-2]\) such that \(u_{j_{s-1}}u_{j_s}\) and \(u_{j_s}u_{j_{s+1 }}\) are the even edges. We have either \(j_{s-1} = j_{s+1} = 0\) or \(\{ j_{s-1},j_{s+1} \} = \{ 0,k-2 \}\). For \(t \in [k-1]\setminus\{ s,s+1 \}\), by induction choose \(\alpha_t, \beta_t\in \mathbb{N}_0\) such that \(j_t - j_{t-1} = (k-1)- \alpha_t (k-2) - \beta_t k\). This allows us to express \(j_{k-1}-j_0\) as follows:

Therefore \(j_{k-1}-j_{0}=j-j'\in A_2\), as required.

\(i\geq 3\): We handle the case \(u_ju_{j'}\in E(P^{\Delta,i-1})\) as before and so assume that \(u_ju_{j'}\) is an odd edge not in \(P^{\Delta,i-1}\). Let \(u_{j_0}\ldots u_{j_{k-1}}\) be a \(u_ju_{j'}\)-path in \(P^{\Delta,i-1}\) where \(u_{j_t} \in \{ v_{j_t},w_{j_t} \}\) for \(1 \leq t \leq k-2\), and let \(J := \{ t \in [0,k-2] : j_t \equiv j_{t+1} \mod 2 \}\). Since \(j-j'\) and \(k-1\) are odd, \(|J|\) must be even. If \(J\) is empty, that is, if \(Q\) consists of odd edges we can again proceed as in Lemma 14. Suppose that \(|J|\geq 2\) and let \(s:=\min J\). Lemma 15 yields \(j_s \leq (k-1)^{i-1}-1\) while Lemma 11 guarantees \(j_t - j_{t+1} \leq (k-1)^{i-1}\) for \(t\in [0,k-2]\). Therefore,

The last inequality uses 2 and \(i\geq 3\). We now have \(j-j'\in A_i\) by the definition of Frobenius numbers and 2 and because \((k-1)^i\) and \(j-j'\) are odd. ◻

Proof. We induct on \(i\geq 1\).

Base case \(i=1\): The only even edges in \(E(P^{\Delta,1})\setminus E(P^{\Delta,0})\) are \(v_0v_{k-2}\) and \(w_0v_{k-2}\). Both of them satisfy the hypothesis \(j+j' \geq (k-1)^1-(k-1)-2\cdot F'(k-2,k)-2\). The claim now holds with either \(\alpha=-1\) and \(\beta,\gamma,\delta,\lambda,\mu\) equal to zero or \(\gamma=-1\) and \(\alpha,\beta,\delta,\lambda,\mu\) equal to zero.

Inductive step: Let \(Q = u_{j_0}\ldots u_{j_{k-1}}\) be a path in \(P^{\Delta, i-1}\) such that \(j_0 = j\), \(j_{k-1} = j'\), and \(u_{j_t}\in\{ v_{j_t},w_{j_t} \}\) for \(1\leq t \leq k-2\). We first show that \(Q\) has exactly one even edge. The number of even edges in \(Q\) is odd for otherwise we have \(j \not \equiv j' \mod 2\). If \(i=2\) the only three even edges in \(P^{\Delta,i-1}\) are \(v_0v_{k-2}\), \(v_{k-2}w_0\) and \(v_0w_0\). A path cannot contain all three of them so \(Q\) has precisely one even edge. If \(i\geq 3\), suppose there are at least three even edges in \(Q\) and let \(s,s'\in [k-1]\) such that \(u_{j_s}u_{j_{s+1}}\) is the first and \(u_{j_{s'-1}}u_{j_{s'}}\) is the last even edge in \(Q\). Then \(s+ (k-1-s') \leq k-4\). By Lemma 15 \[j_s \leq (k-1)^{i-1}-1 \qquad,\qquad j_{s'} \leq (k-1)^{i-1}-1.\] Combining this with Lemma 16 and \(\max A_{i-1} = (k-1)^{i-1}\) gives us

which contradicts the assumption \(j+j' \geq (k-1)^i-(k-1)-2\cdot F'(k-2,k)-2\). Here we used that \(i\geq 3\) and so \((k-1)^{i-1} > 2\cdot F'(k-2,k) + (k-1)\) by 2 . We have thus shown that \(Q\) has precisely one even edge.

Take the unique \(s^*\in [k-1]\) for which \(u_{j_{s^*-1}}u_{j_{s^*}}\) is an even edge. We claim that there exist \(\alpha^*,\gamma^*\in\mathbb{Z}_{\geq -1}\), \(\beta^*,\delta^*,\lambda^*,\mu^*\in\mathbb{N}_0\) such that \(\lambda^*+\mu^* = (k-1)^{i-2}-1\) and \[\label{jstar} j_{s^*-1} = \lambda^* (k-1) - \alpha^* (k-2) - \beta^* k \qquad,\qquad j_{s^*} = \mu^* (k-1) - \gamma^* (k-2) - \delta^* k.\tag{8}\] Indeed, this follows if \(i=2\) and \(j_{s^*-1}= j_{s^*}=0\) by setting all parameters to be \(0\). For all other cases, this follows by the induction hypothesis. In order to appeal to the induction hypothesis, we need to establish the required lower bound on \(j_{s^*-1} + j_{s^*}\) and show that the edge \(u_{j_{s^*-1}}u_{j_{s^*}} \in E(P^{\Delta,i-1})\setminus E(P^{\Delta,i-2})\), which we now do. We have

as required. Now suppose for a contradiction that \(u_{j_{s^*-1}}u_{j_{s^*}}\) already appeared at time \(i-2\). If \(i=2\), then the only even edge at time 0 is \(v_0w_0\) and as we are not appealing to the induction hypthesis for this case, we can assume that \(i\geq 3\). Then by Lemma 15 \[j_{s^*-1}, j_{s^*} \leq (k-1)^{i-2} -1\] and \[j_{s^*-1} + j_{s^*} \leq 2(k-1)^{i-2} - 2 < (k-1)^{i-1} - (k-1) - 2F'(k-2,k) - 2,\] contradicting our lower bound above, using that \(i\geq 3\) and 2 here. Therefore \(u_{j_{s^*-1}}u_{j_{s^*}} \in E(P^{\Delta,i-1})\setminus E(P^{\Delta,i-2})\) and the induction hypothesis gives 8 .

Now by Lemma 16 we have that we can find \(\alpha_t,\beta_t \in \mathbb{N}_0\) such that \[j_t-j_{t-1} = (k-1)^{i-1} - \alpha_t (k-2) - \beta_t k\] for \(s^* < t \leq k-1\) and \[j_{t}-j_{t+1} = (k-1)^{i-1} - \alpha_t (k-2) - \beta_t k\] for \(0 \leq t < s^*-1\). Therefore,

where

Moreover, \[\lambda + \mu = (k-2)(k-1)^{i-2} + \lambda^* + \mu^* = (k-1)^{i-1} - 1,\] which completes the induction. ◻

Proof. Let \(\ell\in(k-1)D_i \cap [n'-1]\). Choose \(d_1,\ldots,d_{k-1}\in D_i\) such that \(\ell = d_1+\ldots+d_{k-1}\). For any \(x\in V(P_{n'})\) with \(x+\ell\in V(P_{n'})\), \[x,x+d_1,\ldots,x+ (d_1+\ldots+d_{k-1})\] is a path of length \(k-1\) from \(x\) to \(x+\ell\) in \(P^i\) since \(d_1,\ldots,d_{k-1}\in D_i\). Thus \(x\) and \(x+\ell\) are adjacent in \(P^{i+1}\) and the claim follows by the definition of \(D_{i+1}\). ◻

Proof. We have \(D_0 = \{ 1 \}\) and \(D_1 = \{ 1,k-1 \}\). For every odd \(3\leq\ell\leq k\) and \(x\in V(P_{n'})\) with \(x+(x+\ell) \leq n'-1\), \[x,\ldots,x+\frac{\ell-1}{2}, x+(k-1)+\frac{\ell-1}{2}, x+(k-1)+\frac{\ell-1}{2}-1,\ldots,x+\ell\] is a path of length \(k-1\) from \(x\) to \(x+\ell\) in \(P^1\) due to the hypothesis \(3(k-1) \leq n'\). Indeed, a quick analysis of two cases \(x\leq (k-1)\) and \(x>(k-1)\) gives that \(x+(k-1) +(\ell-1)/2\leq n'-1\). Therefore 13 gives \(\{ \ell\in [k] : \ell \text{ odd } \} \subseteq D_2\). ◻

Proof. Let \(i\geq 3\) and \(\ell \in [(k-1)^{i-2}+2(k-1), (k-1)^i] \cap A_i\). Then there exist \(\alpha,\beta\in\mathbb{N}_0\) satisfying \(\ell = (k-1)^{i}-\alpha(k-2)-\beta k\). We may assume that \(\alpha\leq k-1\) because \((\alpha-k)\cdot(k-2) + (\beta+k-2)k = \alpha (k-2) + \beta k\). From \[(\alpha+\beta)k - 2\alpha = (k-1)^{i}-\ell \leq (k-1)^i-(k-1)^{i-2}-2(k-1) = (k-1)^{i-2}\cdot (k-2)k -2(k-1)\] we infer \[\alpha+\beta \leq (k-1)^{i-2}\cdot (k-2) + \frac{2\alpha}{k} - \frac{2(k-1)}{k} \leq (k-1)^{i-2}\cdot (k-2),\] hence \(\ell \in A'_{i}\). ◻

Proof. We induct on \(i\geq 0\). We have that \(A'_0 = \{ 1 \} = D_0\) and \(A'_1 = \{ k-1 \} \subseteq D_1\). Let \(i=2\), and let \(x,y\in V(P_{n'})\) with \(y-x = (k-1)^2-\alpha(k-2)-\beta k\) for some \(\alpha+\beta \leq (k-2)\). Write \(s:=k-1-\alpha-\beta\) and note that \(s\geq 1\). If \(x \geq \beta\) then \[x, x-1,\ldots, x-\beta, x-\beta+(k-1),\ldots, x-\beta+s(k-1),x-\beta+s(k-1)+1,\ldots,y\] is a path of length \(k-1\) from \(x\) to \(y = x-\beta+s(k-1)+\alpha\) in \(P^1\). If \(x \leq \beta\) consider the \(xy\)-path \[x,\ldots, x+\alpha, x+\alpha+(k-1),x+\alpha+(k-1)-1,\ldots, x+\alpha+(k-1)-\beta, x+\alpha+2(k-1)-\beta,\ldots, y.\] This path is well-defined because all vertices lie in \([n'-1]\). Indeed, for \(s\geq 2\) the largest term in the sequence is \(y\), which lies in \(V(P_{n'})\) by assumption, whereas if \(s=1\), then \(x+\alpha+(k-1)-\beta = y\) and the maximum is \(x+\alpha+(k-1)\) which can be bounded from above by \(\beta +\alpha + (k-1) \leq 2k-3 \leq n'-1\). Thus, \(xy \in E(P^2)\). Since \(x\) and \(y\) were arbitrary, \(A'_2 \cap [n'-1] \subseteq D_2\). For every \(i\geq 3\), the induction hypothesis and Lemma 18 imply \[A'_i \cap [n'-1] \subseteq (k-1)A'_{i-1}\cap [n'-1] \subseteq (k-1)D_{i-1} \cap [n'-1] \subseteq D_i ,\] where the inclusion \(A'_i \subseteq (k-1)A'_{i-1}\) follows from the fact that for any \(\alpha,\beta\in\mathbb{N}_0\) with \(\alpha+\beta\leq (k-1)^{i-2}\cdot(k-2)\) we can find \[\alpha_1,\ldots,\alpha_{k-1} \in \left\lbrace \floor*{\frac{\alpha}{k-1}}, \ceil*{\frac{\alpha}{k-1}}\right\rbrace \quad,\quad \beta_1,\ldots,\beta_{k-1} \in \left\lbrace \floor*{\frac{\beta}{k-1}}, \ceil*{\frac{\beta}{k-1}}\right\rbrace\] such that \(\alpha = \alpha_1+\ldots+\alpha_{k-1}\), \(\beta = \beta_1+\ldots+\beta_{k-1}\) and \(\alpha_s+\beta_s \leq (k-1)^{i-3}\cdot (k-2)\), \(1\leq s\leq k-1\). ◻

Proof. Our goal is to show \(D_\rho = [n'-1]\). To do so we write \([n'-1]\) as the union \[[n'-1] = [3(k-1)-1] \;\cup\; [3(k-1),n'-1]\] and show \([3(k-1)-1] \subseteq D_4\) and \([3(k-1),n'-1]\subseteq D_\rho\). Lemma 19 yields \(k-2\in D_2\) because \(k-2\) is odd. Then for each even \(2\leq\ell \leq k-1\) and each vertex \(x\) with \(x+(x+\ell) \leq n'-1\), \[x,\ldots,x+\frac{\ell}{2}, x+(k-2)+\frac{\ell}{2}, x+(k-2)+\frac{\ell}{2}-1,\ldots,x+\ell\] is a path of length \(k-1\) from \(x\) to \(x+\ell\) in \(P_{n'}^2\). Here we used that \(x+(k-2)+\ell/2\leq n'-1\), which follows from a quick case analysis of \(x\leq k-2\) and \(x\geq k-1\), so all vertices of the path indeed belong to \(P_{n'}\). Now 13 implies \([k] \subseteq D_3\). Applying Lemma 18 gives \[D_4 \supseteq [(k-1)\cdot k]\cap [n'-1] \supseteq [3(k-1)-1].\] The inclusion \([3(k-1), n'-1] \subseteq D_\rho\) follows from Lemmas 20 and 21. Indeed, by the definition of the Frobenius number \(F(k-2,k)\) 1 , and as \(k\) is odd we have \(A_i \supseteq (-\infty, (k-1)^i-F(k-2,k)-1]\) for all \(i\geq 0\). This allows us to write

The second equality holds since \((k-1)^{3-2}+2(k-1) = 3(k-1)\) and \((k-1)^i-F(k-2,k) \geq (k-1)^{i+1-2}+2(k-1)\) for \(i\geq 3\) by 1 . We also used Lemma 20 followed by Lemma 21 in the fourth line. We have shown that \(D_\rho = [n'-1]\), so \(P_{n'}^\rho\) is a complete graph. ◻

Proof. Since \(n' \geq 3(k-1)\) we may invoke Lemma 19 to obtain \[\{ \ell \in [k] : \ell \text{ odd} \} \subseteq D_2.\] Lemma 18 then gives \[\{ \ell \in [3(k-1)-1] : \ell \text{ odd} \} \;\subseteq\; \{ \ell \in [(k-1)^2] : \ell \text{ odd} \} \cap [n'-1] \subseteq D_3 \subseteq D_\rho.\] This takes care of the case \(|x-y| < 3(k-1)\). Suppose that \(|x-y| \geq 3(k-1)\).

The intervals \([(k-1)^{i-2}+2(k-1), (k-1)^i-F'(k-2,k)]\) and \([(k-1)^{i-1}+2(k-1), (k-1)^{i+1}-F'(k-2,k)]\) intersect whenever \(i\geq 3\). Therefore by 2 \[[3(k-1),(k-1)^\rho] = [(k-1)^\rho - F'(k-2,k), (k-1)^\rho] \cup \bigcup_{i=3}^{\rho} [(k-1)^{i-2}+2(k-1), (k-1)^i-F'(k-2,k)-1].\] If \((k-1)^\rho - F'(k-2,k) < |x-y|\) we can use Lemma 20 because \(|x-y|\in A_\rho\) and thereby obtain \(|x-y|\in A'_\rho\). Lemma 21 then tells us that \(|x-y| \in D_\rho\). If not, there exists \(3\leq i\leq \rho\) such that \(|x-y| \in [(k-1)^{i-2}+2(k-1), (k-1)^i-F'(k-2,k)-1]\) so we have \(|x-y| \in A_i\) by definition of \(F'(k-2,k)\) and we can apply Lemmas 20 and 21 to conclude \(|x-y|\in D_i \subseteq D_\rho\). In the case that \(n' \leq (k-1)^\rho - F'(k-2,k)\) a copy of \(K_{\floor{n'/2},\ceil{n'/2}}\) is present at time \(\rho\). Since \(P_{n'}\) is bipartite, so is \(\final{P_{n'}}_{C_k}\) due to Lemma 7. Thus the process has stabilised. ◻

Proof. Take a shortest odd walk \(u_0\ldots u_m\) between the endpoints of \(e\) in \(G\). The claim is clearly satisfied with \(\ell'=0\) and \(\ell=m-1\) when the shortest odd walk is already a path. We therefore assume that the walk has at least one repeated vertex. Observe that for any \(0 \leq j < j'\leq m\) with \(u_j = u_{j'}\), \(j-j'\) must be odd for otherwise \(u_0\ldots u_j u_{j'+1}\ldots u_m\) would be a shorter odd walk. This implies that no vertex occurs more than twice on \(u_0\ldots u_m\). Set

and let \(j'_0,j'_1\in [m]\) be the unique integers satisfying \(j'_0 > j_0, u_{j_0} = u_{j'_0}\) and \(j'_1 < j_1, u_{j_1} = u_{j'_1}\). Then \(j_0 < j_1\) since otherwise \(u_0\ldots u_{j'_1-1}u_{j_1}\ldots u_{j_0}u_{j'_0+1}\ldots u_m\) would be an odd walk of length less than \(m\). By the extremality of \(j_0\) and \(j_1\) we have \(j'_1 \leq j_0\) and \(j_1 \leq j'_0\). In fact, we have that equality is attained in both of the last two inequalities. Indeed, if one of them was strict the walk \(u_0\ldots u_{j'_1-1}u_{j_1}\ldots u_{j_0}u_{j'_0+1}\ldots u_m\) would have length \[j'_1 + (j_1-j_0) + m-j'_0 < j'_1 + (j'_0-j'_1) + m - j'_0 = m\] so \[0 \equiv j'_1 + (j_1-j_0) + m-j'_0 \equiv (j_1-j'_1) + (j'_0-j_0) +m \mod 2\] by the minimality of \(m\). But this would contradict the fact that \(j_1-j'_1\), \(j'_0-j_0\) and \(m\) are all odd. Therefore \(j'_1 = j_0\) and \(j'_0 = j_1\), which implies \(u_{j_0} = u_{j_1}\). We conclude \(j_1-j_0 \geq 3\) and \(j_1+j_0=j_1-j_0+2j_0\) is odd because \(j_1-j_0\) must be odd. By definition of \(j_0\) and \(j_1\), both \(u_0\ldots u_{j_1-1}\) and \(u_{j_0+1}\ldots u_m\) are paths and each of the vertices \(u_{j_0+1},\ldots,u_{j_1-1}\) occurs precisely once on \(u_0\ldots u_m\). Define \(v_j\), \(0\leq j \leq \ell:=\floor{(j_0+j_1)/2}\), and \(w_{j'}\), \(0\leq j' \leq \ell' := m - \ceil{(j_0+j_1)/2}\) by \[v_j := u_{\floor*{\frac{j_0+j_1}{2}}-j} \quad,\quad w_{j'} := u_{\ceil*{\frac{j_0+j_1}{2}}+j'}.\] Then both \(v_\ell \ldots v_0w_0\) and \(v_0w_0\ldots w_{\ell'}\) are paths. Therefore \(\ell,\ell' \leq n-2\). Now we check that \(\ell' \leq \ell\) and \(v_j\neq w_{j'}\) whenever \(j\neq j'\). Suppose there were \(j\neq j'\) with \(v_j = w_{j'}\). Due to the definition of \(v_j, w_{j'}\) and the minimality of \(m\) we have \[\left(\floor*{\frac{j_0+j_1}{2}}-j\right) - \left(\ceil*{\frac{j_0+j_1}{2}}+j'\right) \equiv 1 \mod 2,\] and thus, as \(j_0 - j_1 \equiv 1 \!\mod 2\), \[j_0 - \floor*{\frac{j_0+j_1}{2}}+j \equiv \ceil*{\frac{j_0+j_1}{2}}+j'-j_1 \mod 2.\] But then replacing the longer of the two walks \(u_{j_0}\ldots u_{\floor*{\frac{j_0+j_1}{2}}-j}\) and \(u_{j_1}\ldots u_{\ceil*{\frac{j_0+j_1}{2}}+j'}\) by the shorter one creates an odd walk between the endpoints of \(e\) whose length is less than \(m\). Here we used these walks are not the same size due to the fact that \(j\neq j'\). If \(\ell' \leq \ell\) we are done. Otherwise we simply relabel the path by interchanging the roles of \(\ell\) and \(\ell'\) and turning \(v_i\) into \(w_i\) and vice versa. Finally, we cannot have \(\ell' = \ell = n-2\) as in that case \(w_{\ell'}\notin \{ v_0,\ldots,v_\ell \}\) gives \(|\{ v_0,\ldots,v_\ell,w_0,w_{\ell'} \}| = n+1\). ◻

Proof. Write \(\ell'=q'(k-1)+s'\) and \(\ell = q(k-1)+s\) and where \(q,q',s,s'\in\mathbb{N}_0\), \(0 \leq s, s' \leq k-2\). Recall that \(\ell \geq \ell'\) and \(\ell+\ell' \geq 4(k-1)^2-1\), hence \(q \geq q'\) and \(q > 1\). At time \(1\), \[P := w_0\ldots w_{s'}w_{s'+(k-1)}\ldots w_{s'+q'(k-1)}\] is a path of length \(q'+s'\) from \(w_0\) to \(w_{\ell'}\). It contains neither \(v_0\) nor \(v_\ell\) as \(\ell'\leq\ell\), \(w_{\ell'}\neq v_{\ell}\), and \(w_j\notin \{v_0, v_\ell\}\) for \(j<\ell\) by Claim 24. If \(s'=0\), \[Q_0 := v_0v_{1}v_{1+(k-1)}\ldots v_{1+q(k-1)}v_{1+q(k-1)+1}\ldots v_{1+q(k-1)+s-1}\] is a path of length \(q+s\) from \(v_0\) to \(v_\ell\) which is vertex-disjoint from \(P\) as the indices of the vertices on \(P\) are multiples of \(k-1\) whereas the indices of vertices on \(Q_0-v_0-v_\ell\) are not. The union of \(P\), \(Q_0\) and \(v_0w_0\) is an \(xy\)-path in \(G_1\) of length \(q'+(q+s)+1\). Note that \[q'+(q+s)+1 \equiv q'(k-1)+ q(k-1)+s+1 \equiv (\ell - \ell'+1) \equiv 1 \mod 2\] and \[q' + q+s + 1 \leq \frac{\ell'+\ell}{k-1} + k - 1 \leq (k-1)^{r-1} - F'(k-2,k) - 2(k-1) < (k-1)^{r-1} - F'(k-2,k).\]

If \(s' >0\), recall that \(q>1\) and consider the path \[Q_{s'} := \begin{cases} v_0v_{k-1}\ldots v_{q(k-1)}v_{q(k-1)-1}\ldots v_{(q-1)(k-1)+s}v_\ell &, \; \text{if } s > s' ; \\ v_0v_{k-1}\ldots v_{q(k-1)}v_{q(k-1)+1}\ldots v_\ell &, \; \text{if } s\leq s'. \end{cases}\] This path has length \(q+(k-1)-s+1\) or \(q+s\). It is vertex-disjoint from \(P\) since \(w_j \equiv s'\mod k-1\) for all \(j\geq s'\) with \(w_j \in V(P)\), whereas all \(j\in [0,\ell']\) with \(v_j \in V(Q_{s'})\setminus\{v_0,v_\ell\}\) satisfy \(j > s'\) and \(j\not \equiv s'\mod k-1\). Moreover, recall that \(v_0\) and \(v_\ell\) do not lie on \(P\).

As \(v_0w_0 \in E(G_1)\), the union of the paths \(P\),\(Q_{s'}\) and the edge \(v_0w_0\) is an \(xy\)-path of length \(q'+s'+q+k-s+1\) or \(q'+s' + q + s+1\), where \[q'+s' + q+k- s + 1\;\equiv\; q'+s'+q+s + 1\;\equiv\; \ell+\ell'+1 \mod 2.\] The length of \(P\cup Q_{s'} \cup \{v_0w_0\}\) is bounded from above by \[\frac{\ell+\ell'}{k-1} + 2(k-2) + 1 < (k-1)^{r-1} - F'(k-2,k).\] In all cases we have an odd \(xy\)-path of length at least \(q+q'\) and less than \((k-1)^{r-1}- F'(k-2,k)\). Using \[q + q' = \floor*{\frac{\ell}{k-1}} + \floor*{\frac{\ell'}{k-1}} \geq \floor*{\frac{\ell+\ell'}{k-1}} - 1 \geq 3(k-1)\] we can apply Proposition 23 with \(\rho=r-1\) and Observation 5 to either \(P \cup Q_0 \cup \{ v_0w_0\}\) or \(P\cup Q_{s'}\cup \{v_0w_0\}\) to deduce \(xy\in E(G_{1+r-1}) = E(G_r)\). ◻

Proof. The size constraints are only necessary to guarantee that the vertices occurring in the statement actually exist. We induct on \(i\geq 1\). When \(i=1\) the claim reads \(v_0w_{k-2},v_{k-1}w_{-1} \in E(G_1)\), which holds since \(v_0\) and \(w_{k-2}\), and similarly \(v_{k-1}\) and \(v_0\), are endpoints of paths of length \(k-1\) in \(G\). Suppose that \(i\geq 2\) and the above size constraints are satisfied. Set \[j_s := \frac{(k-1)^{i-1}-(k-1)}{2} + s\cdot (k-1)^{i-1} \quad,\quad 0\leq s \leq (k-2)/2.\] The induction hypothesis gives \[v_{j_0}w_{j_0+k-2},v_{j_0+k-1}w_{j_0-1} \in E(G_{i-1})\] and Lemma 11 assures that any two vertices of distance \((k-1)^{i-1}\) in \(G\) are adjacent at time \(i-1\). We have \[j_s+k-2 \equiv k-2 \not\equiv 0 \equiv j_{s'} \mod k-1\] for any \(0\leq s,s'\leq (k-2)/2\) and hence \(w_{j_s+k-2} \neq v_{j_{s'}}\). Similarly, \(w_{j_s-1} \neq v_{j_{s'}+k-1}\). Therefore \[v_{j_{(k-2)/2}}\ldots v_{j_1}v_{j_0}w_{j_0+k-2}w_{j_1+k-2}\ldots w_{j_{(k-2)/2}+k-2}\] and \[v_{j_{(k-2)/2}+k-1}\ldots v_{j_1+k-1}v_{j_0+k-1}w_{j_0-1}w_{j_1-1}\ldots w_{j_{(k-2)/2}-1}\] are paths of length \(k-1\) in \(G_{i-1}\). The claim now follows from the observation that \[j_{(k-2)/2} = \frac{(k-1)^i-(k-1)}{2}.\] ◻

Proof. Recall that \(\ell \equiv \ell' \mod 2\) since \(v_\ell\ldots v_0w_0\ldots w_{\ell'}\) is an odd walk. Our plan is to find an \(xy\)-path of length \(k-1\) in \(G_{r-1}\). By the conditions on \(\ell,\ell'\) in Claim 24 and the upper bound in 6 , we have

Now choose \[j_0 \in \left\lbrace \frac{(k-1)^{r-1}-(k-1)}{2}, \frac{(k-1)^{r-1}-(k-1)}{2}+k-1 \right\rbrace\] and \[j'_0 \in \left\lbrace \frac{(k-1)^{r-1}-(k-1)}{2}-1, \frac{(k-1)^{r-1}-(k-1)}{2}+k-2 \right\rbrace\] such that \(\ell-j_0 \equiv \ell'-j'_0 \equiv (k-2)/2 \mod 2\). The congruences \(\ell-j_0 \equiv \ell'-j'_0 \mod 2\) and \(\ell \equiv \ell' \mod 2\) together imply \(j_0 \equiv j'_0 \mod 2\). Thus \(v_{j_0}w_{j'_0}\) is one of the edges whose presence at time \(r-1\) is guaranteed by Claim 27 with \(i=r-1\). We note here that \(v_{j_0}, w_{j_0'}\) indeed exist as \(\ell, \ell'\geq j_0,j_0'\) due to 14 and the fact that \(r\) is sufficiently large.

We will now construct a \(v_{j_0}v_\ell\)-path \(Q\subseteq G_{r-1}\) and a \(w_{j'_0}w_{\ell'}\)-path \(P \subseteq G_{r-1}\) , both of length \((k-2)/2\) and such that \(V(P)\cap V(Q)=\emptyset\). Then the union of these paths along with the edge \(w_{j'_0}v_{j_0}\) gives an \(xy\)-path of length \(k-1\) in \(G_{r-1}\), and hence \(xy\in E(G_r)\) as required. To this end we define \[j'_s := j'_0 + s\cdot (k-1)^{r-1} \qquadand\qquad j_s := j_0 + s\cdot (k-1)^{r-1},\] for \(1\leq s\leq t:= \frac{k-2}{2}-1=\frac{k-4}{2}\), and claim that \(Q:=v_{j_0}v_{j_1}\ldots v_{j_t}v_{\ell}\) and \(P:= w_{j'_0}w_{j'_1}\ldots w_{j'_{t}}w_{\ell'}\) are the required paths.

First let us check that the vertices used in the path actually exist. That is, we need to check that \(\ell>j_t\) and \(\ell'>j'_t\). This follows because

where we used 14 in the second last inequality and the fact that \(r\) is sufficiently large in the final inequality. This shows that \(\ell>j_t\) and \(\ell'>j'_t\) as \(\ell\geq \ell'\) and \(j'_t\leq j_t+(k-2)\).

Next we show that the paths \(P,Q\) indeed exist in \(G_{r-1}\). The existence of the edges \(v_{j_{s-1}}v_{j_{s}}\in E(G_{r-1})\) for \(s\in[t]\) is guaranteed by Lemma 11 and likewise for the edges \(w_{j'_{s-1}}w_{j'_{s}}\) with \(s\in [t]\). It remains to establish that \(v_{j_t}v_\ell,w_{j'_t}w_{\ell'}\in E(G_r)\). For this we note that \[\label{eq:ell32parity} \ell-j_t\equiv (\ell-j_0)-(j_t-j_0) \equiv \left(\frac{k-2}{2}\right) - \left(\frac{k-4}{2}\right)\equiv 1 \mod 2,\tag{16}\] from our choice of \(j_0\). Similarly, we have that \(\ell'-j'_t\equiv 1 \mod 2\). Moreover, \(\ell,\ell'+1\leq n-2\) (Claim 24) and \(j_t, j'_t+1\geq \frac{k-3}{2}(k-1)^{r-1}-\frac{k-1}{2}\). Therefore, appealing to the upper bound of 6 , we get \[\ell-j_t,\ell'-j'_{t}< \frac{(k-1)^r-(k-1)}{2}-F'(k-2,k)-\left(\frac{k-3}{2}(k-1)^{r-1}-\frac{k-1}{2}\right)=(k-1)^{r-1}-F'(k-2,k).\] Hence Proposition 23 gives that both \(v_{j_t}v_\ell\) and \(w_{j'_t}w_{\ell'}\) are present in \(G_{r-1}\).

Finally then, we need to establish that \(P\) and \(Q\) are disjoint. Recall that we chose \(j_0, j'_0\) such that \(j_0 \equiv j'_0 \mod 2\) and hence we obtain either \(j_0 = j'_0 - (k-2)\) or \(j_0 = j'_0 + k\). Therefore \[j_s \equiv j_0 \not\equiv j'_0 \equiv j'_{s'} \mod k-1\] for \(0 \leq s,s' \leq t\) and so \(Q\setminus \{v_\ell\}\) and \(P\setminus \{w_{\ell'}\}\) do not intersect by Remark 25. Moreover \(v_\ell\neq w_{\ell'}\) as \(\{v_\ell,w_{\ell'}\}=\{x,y\}\) and \(\ell\geq \ell'>j_t\) using 15 gives that \(v_\ell\notin V(P)\) and \(w_{\ell'}\notin V(Q)\). This shows that \(P\cup Q\cup\{w_{j'_0}v_{j_0}\}\) is indeed a path of length \(k-1\) in \(G_{r-1}\) and \(xy \in E(G_r)\) as required. ◻

Proof. Let \(Q\) be a shortest \(xy\)-path in \(G_i\). Any edge \(uv\) of \(Q\) that is not present at time \(i-1\) yields a \(uv\)-path \(Q_{uv}\) of length \(k_j-1\) in \(G_{i-1}\) for some \(j\in [s]\). We can build an \(xy\)-walk in \(G_{i-1}\) by replacing every \(uv \in E(Q)\cap E(G_i) \setminus E(G_{i-1})\) by \(Q_{uv}\). That walk has length at most \((k_1-1)\cdot \mathop{\mathrm{dist}}_{G_i}(x,y)\) because \(k_1 \geq k_j\) for \(j\in [s]\). Therefore, \[\mathop{\mathrm{dist}}_{G_{i-1}}(x,y) \leq (k_1-1) \mathop{\mathrm{dist}}_{G_i}(x,y)\] and iterating gives the desired claim. ◻

Proof. For each \(j\in[s]\), every copy \(P'\) of \(P_{k_j}\) at time \(i\) with vertices in \(Z\) can be extended to \(C'_1\cup\ldots\cup C'_{k_j-1}\cup P'\cup C'_{k_j+1}\cup\ldots\cup C'_s\) so the endpoints of \(P'\) are adjacent at time \(i+1\). This implies that if no edge is added inside \(Z\) at time \(i\) then \(\langle G\rangle_H[Z]=G_i[Z]\). If \(G_1[Z]\) is already \(C_{k_j}\)-stable for every \(j\in [s]\) or has at most \(k_1\) vertices, it will be \(C_{k_j}\)-stable for every \(j\) at time \(k_1^2+1\). Otherwise we have \(|Z| \geq k_1+1\) and one can find a \(k_j\)-cycle in \(G_2[Z]\) for some \(j\in [s]\).

Consider the case that \(G_2[Z]\) has diameter at most \(k_1-2\). Since \(k_s = \min_{j\in [s]} k_j\) there must be a \(k_s\)-cycle \(C\) in \(G_3[Z]\). Pick a vertex \(z_0\in V(C)\) and define

As \(G_3[Z]\) is connected, \(Z = X \cup Y\) with \(X\cap Y = \varnothing\) when \(G_3[Z]\) is bipartite and \(X=Y=Z\) otherwise. Let \(x\in X\), \(y\in Y\) be distinct vertices and choose \(Z'\subseteq Z\) of size at least \(k_1+1\) and at most \(3k_1\) such that \(x,y\in Z'\), \(G_3[Z']\) is connected, and \(C \subseteq G_3[Z']\). Let \(i_0 := 3 + M_{C_{k_s}}(3k_1)\). By Lemma 10 with respect to the \(C_{k_s}\)-process on \(G_3[Z']\), \(xy \in E(G_{i_0}[Z'])\). Since \(x\) and \(y\) were chosen arbitrarily, \(G_{i_0}[Z]\) is complete or contains a complete bipartite graph with partite sets \(X\) and \(Y\). If \(G_{i_0}[Z]\) is a complete bipartite graph it will be \(C_{k_j}\)-stable for all \(j\) after two more steps¹. If not, Lemma 9 tells us that \(Z\) will be a clique at time \(i_0+2 < 5k_1^2\).

Finally, we suppose that \(G_2[Z]\) contains a copy of \(P_{k_1}\). Let \(i_1 := 2 + M_{C_{k_1}}(n)\). Lemma 10 applied to the \(C_{k_1}\)-process on \(G_2[Z]\) guarantees that \(G_{i_1}[Z]\) is either complete or contains a complete bipartite graph with at least \(\floor{k_1/2}\) vertices in either part. Again, after two more steps we arrive at a graph that is \(C_{k_j}\)-stable for all \(j\in[s]\). ◻

Proof. If \(u\in U_j'\) then there is a path \(P_u\) in \(G_1\) from \(u\) to \(C_j'\) avoiding the \(C'_{\ell}\) with \(\ell\neq j\). If \(P_u\) has length at least \(k_1+1\) (and hence \(k_1+1\) vertices disjoint from \(C_j'\)), Theorem 12 applied with \(k=k_1\) to \(P_u-v\), where \(v\) is the endpoint of \(P_u\) on \(C'_j\), gives that \(u\) has distance at most 3 from \(C_j'\) in \(G_{\tau_0'}\) with \(\tau_0':=M_{C_{k_1}}(n)+1\). Therefore at time \(\tau_0'\) we can assume that every vertex in \(U_j'\) is of distance at most \(k_1+1\) from \(C_j'\). By Lemma 10 with \(k=k_j\) on \(G_{\tau'_0}[U'_j\cup V(C'_j)]\), we have that indeed \(U_j'\subseteq N_{\tau_0}(C_j')\), using that \(\tau_0'+M_{C_{k_j}}(k_j+k_1)\leq \tau_0'+(k_j+k_1)^2/2 \leq \tau_0\). ◻

Proof. Let \(j\in [s]\) be fixed.

[item:32mult321] Every \(u\in N_i(C'_j)\) has a neighbour on \(C'_j\), so by going around \(C'_j\) we can pick \(x_j(u) \in V(C'_j)\) such that \(u\) and \(x_j(u)\) are the endpoints of a path of length \(k_j-2\) in \(V(C'_j)\cup \{ u \}\). Therefore, if \(uv\in E(G_i)\) for some \(v \in V(G)\setminus (N_{i}(C'_j)\cup V')\), we have \(x_j(u)v\in E(G_{i+1})\) and thus \(v\in N_{i+1}(C'_j)\). Here it is important that \(v\notin V'\) so we may extend the path of length \(k_j-2\) to a copy of \(H\) minus an edge.

[item:32mult322] Recall that any \(k_j\)-cycle with vertices in \(N_{i}(C'_j)\cup V(C'_j)\) can be extended to a copy of \(H\) using \(C'_1,\ldots,C'_s\). If \(j\) is odd, then for any non-empty \(U\subseteq N_i(C'_j)\) of size at most two, \(G_{i+k_j^2}[U\cup V(C'_j)]\) is complete, due to Lemma 10 and the fact that \(M_{C_{k_j}}(k_j+|U|) < \binom{k_j+2}2 \leq k_j^2+1\). Hence \(G_{i+k_j^2}[N_i(C'_j)\cup V(C'_j)]\) is complete. Similarly, if \(j\) is even and \(C'_j\) is bipartite with parts \(X\subseteq V(C'_j)\) and \(Y\subseteq V(C'_j)\), then let \(X'\subseteq N_i(C'_j)\) be all vertices with a neighbour in \(Y\) and \(Y':=N_i(C'_j)\setminus X'\), noting that each vertex in \(Y'\) must have a neighbour in \(X\). Similarly to the odd case, for any non-empty \(U\subseteq N_i(C'_j)\) with \(|U\cap X'|,|U\cap Y'|\leq 1\), we have that \(G_{i+k_j^2}[U\cup V(C'_j)]\) contains a complete bipartite graph with parts \(X\cup (X'\cap U)\) and \(Y\cup (Y'\cap U)\), by Lemma 10. Hence \(G_{i+k_j^2}[N_i(C'_j)\cup V(C'_j)]\) contains a spanning complete bipartite graph with parts \(X\cup X'\) and \(Y\cup Y'\) (which each have size at least \(|X|=|Y|=k_j/2\)).

[item:32mult323] Let \(x \in N_{i}(C'_\ell)\setminus N_{i}(C'_j)\). If \(x\) has a \(G_{i+k_1^2}\)-neighbour in \(N_{i+k_1^2}(C'_j)\), then \(x\in N_{i+k_1^2+1}(C'_j)\) by part [item:32mult321]. Now suppose that \(x\) does not have such a neighbour. In particular, it is not adjacent to any vertex in \(N_{i}(C'_j)\). Since \(|N_{i}(C'_j)\cap N_{i}(C'_\ell)|\geq 3\), we have that \(G_{i+k_1^2}[N_{i}(C'_\ell)\cup V(C'_\ell)]\) contains both \(x\) and a vertex from \(N_{i}(C'_j)\) and thus cannot be complete. Then part [item:32mult322] forces \(k_\ell\) to be even (in particular \(k_\ell \geq 4\)) and \(G_{i+k_1^2}[N_{i}(C'_\ell)\cup V(C'_\ell)]\) to contain a spanning complete bipartite graph. Label the vertices of \(C'_\ell\) by \(v_0,\ldots,v_{k_\ell-1}\) such that \(E(C'_\ell) = \{ v_0v_1,\ldots,v_{k_\ell-1}v_0 \}\) and \(xv_1 \in E(G_{\tau_0})\) (see Figure 3). Let \(y,y',y''\) be three distinct vertices in \(N_{i}(C'_j)\cap N_{i}(C'_\ell)\). As \(N_{G_{i+k_1^2}}(x) \cap \{ y,y',y'' \} = \emptyset\) we have \(yv_t,y'v_t,y''v_t \in E(G_{i+k_1^2})\) for all odd \(t\in[0,k_\ell-1]\). Label the vertices of \(C'_j\) by \(w_0,\ldots,w_{k_j-1}\) (and relabel the vertices \(y,y',y''\) if necessary) such that \(yw_3 \in E(G_{i+k_1^2})\), and \(r\in\{ 1,2 \}\) such that \(y'w_r,y''w_r \in E(G_{i+k_1^2})\) (in Figure 3 we have the case \(r=2\)). Now \[xv_1yw_3\ldots w_{k_j-1}\] is a path of length \(k_j-1\) that is vertex-disjoint from the \(k_\ell\)-cycle \[v_3\ldots v_{k_\ell-1}y'w_ry''v_3.\] Together with the cycles \(C'_t\), \(t\in [s]\setminus\{ j,\ell \}\) they form a copy of \(H\) minus the edge \(xw_{k_j-1}\). Therefore, \(x \in N_{i+k_1^2+1}(C'_j)\). ◻

Proof. Suppose to the contrary that \(\tau_H(G)>i+\tau_1\) and \(W_j:=N_i(C'_j)\) is such that \(N_{i+\tau_1}(C'_j)=W_j\) for all \(j\in [s]\). By part [item:32mult322] of Claim 32, for each \(j\in [s]\) we have that \(G_{i+k_1^2}[W_j\cup V(C'_j)]\) is either complete or contains a spanning complete bipartite graph with partite sets of size at least \(k_j/2\). Unless \(G_{i+k_1^2}[W_j\cup V(C'_j)]\) is a complete bipartite graph, Lemma 9 then gives that \(G_{i+k_1^2+2}[W_j\cup V(C'_j)]\) is complete. Now consider the steps \[\label{eq:I39} I':=\{i':i+k_1^2+2<i'\leq i+\tau_1-1\}.\tag{18}\] For each such step \(i'\in I'\), there is an edge \(e_{i'}\in E(G_{i'})\setminus E({G_{i'-1}})\) (as \(\tau_H(G)>i+\tau_1\)). If \(e_{i'}\) has one vertex in \(V'\) and the other in \(V\setminus V'\) then there will be some \(j\in [s]\) with \(N_{i'}(C'_j)\neq N_{i'-1}(C'_j)\), a contradiction. Therefore either \(e_{i'}\subseteq V'\) or \(e_{i'}\cap V'=\emptyset\). There are at most \(\binom{|V'|}{2}\leq \binom{sk_1}{2}\leq s^2k_1^2\) steps \(i'\in I'\) for which the former can happen. If the latter occurs, as the sets \(W_j\) cover \(V\setminus V'\) (indeed the smaller sets \(N_{\tau_0}(C'_j)\) cover \(V\setminus V'\) by Claim 31) we have that there is some \(j\) such that \(e_{i'}\cap W_j\neq \emptyset\) and we claim that \(e_{i'}\subseteq W_j\). If this was not the case then the other endpoint of \(e_{i'}\) would lie outside of \(W_j\cup V'\) and part [item:32mult321] of Claim 32 gives that \(N_{i'+1}(C'_j)\neq N_{i'}(C'_j)\), a contradiction. There can therefore be at most \(3s\) steps \(i'\in I'\) such that \(e'\) has both endpoints in \(V\setminus V'\). Indeed, as we noted above, for each \(j\in [s]\), we have that \(G_{i+k_1^2+2}[W_j\cup V(C'_j)]\) is either complete or complete bipartite. In the first case, there are no time steps \(i'\in I'\) with \(e_{i'}\subseteq W_j\) and in the second case there are at most 3, as if \(i'_0\) is the first such time step then \(G_{i'_0+2}[W_j\cup V(C'_j)]\) is complete by Lemma 9. Putting this all together and counting the steps \(i'\) according to each possibility, we get that \(|I'|\leq s^2k_1^2+3s<\tau_1-k_1^2-3\), contradicting the definition of \(I'\). ◻

Proof. Suppose that \(\tau_H(G)>i+\tau_2\). By Claim 33, for each \(r\in [2s^2]\), there is some \(j(r)\in [s]\) such that \(|N_{i+r\tau_1}(C'_{j(r)})|>|N_{i+(r-1)\tau_1}(C'_{j(r)})|\). By averaging, there is some \(j\in [s]\) such that \(|Z_j|\geq 2s\) where \(Z_j:=N_{i+2s^2\tau_1}(C_j')\setminus N_{i}(C'_j)\). Now for each \(z\in Z_j\), by Claim 31, we have that there is some \(\ell\in [s]\setminus \{j\}\) such that \(z\in N_{\tau_0}(C_\ell')\). By the pigeonhole principle, as \(|Z_j|\geq 2(s-1)+1\), there is in fact some \(\ell\in [s]\setminus \{j\}\) such that \(|Z_j\cap N_{\tau_0}(C'_\ell)|\geq 3\). In particular, as \(Z_j\cap N_{\tau_0}(C'_j)=\emptyset\), we have that \(N_{\tau_0}(C'_\ell)\nsubseteq N_i(C'_j)\). Finally then by part [item:32mult323] of Claim 32, we have that \(N_{\tau_0}(C_\ell')\subseteq N_{i+2s^2\tau_1}(C'_\ell)\subseteq N_{i+2s^2\tau_1+k_1^2+1}(C'_j)\) as required. ◻