Proof. Let $V_1, \dotsc, V_k$ be the parts of $G$ . Without loss of generality we can assume that $v,v^{\prime} \in V_1$ . We can construct $(v_2, \dotsc, v_k)$ a $(v,v^{\prime})$ -linking sequence by first selecting $v_2 \in N(\{v, v^{\prime}\}, V_2)$ and then $v_k \in N(\{v, v^{\prime}\}, V_k)$ each in at least $2 \delta ^*(G) - n \ge \varepsilon n$ ways. Iteratively, for $i$ from $3$ to $k-2$ we can select $v_i \in N(v_{i-1}, V_i)$ in at least $\delta ^*(G) \ge n/2$ ways. Finally, we can select $v_{k-1} \in N(\{v_{k-2}, v_k\}, V_{k-1})$ in at least $2 \delta ^*(G) - n \ge \varepsilon n$ ways.

Proof. There are at least $n \cdot \delta _3 \cdot (\delta _1 + \delta _2 - n) \ge n^3/6$ triangles in $G$ , because we can pick any $w_3 \in V_3$ , then any $w_1 \in N(w_3, V_1)$ and then any $w_2 \in N(w_1) \cap N(w_3) \cap V_2$ to form a triangle. We will also need the following fact:

(5) \begin{equation} \text{$\forall u_1,u^{\prime}_1 \in V_1$ there are at least $6 \varepsilon ^2 n^2$ edges $u_2u_3$ s.t.} \setminus \text{$u_1u_2u_3$ and $u^{\prime}_1u_2u_3$ are triangles}. \end{equation}

To see (5), note that there are at least $2 \delta _3 - n \ge 2 \varepsilon n$ ways to pick a vertex $u_3 \in V_3$ adjacent to both $u_1$ and $u^{\prime}_1$ and that then there are at least $2\delta _1 + \delta _2 - 2n \ge 3 (\delta _1 + \delta _2)/2 - 2n \ge 3 \varepsilon n$ ways to select a vertex $u_2 \in V_2$ that is adjacent to $u_1$ , $u^{\prime}_1$ and $u_3$ .

The fact that there are at least $n^3/6$ triangles and (5) immediately implies that, for every $v,v^{\prime} \in V_1$ , the number of $(v,v^{\prime},5)$ -linking sequences is at least $\frac{\varepsilon ^3 n^5}{100}$ , because the sequence $(u_2,u_3,w_1,w_2,w_3)$ is a $(v,v^{\prime},5)$ -linking sequence whenever $vu_2u_3$ and $v^{\prime}u_2u_3$ are both triangles and $w_1w_2w_3$ is a triangle disjoint from $\{v,v^{\prime},u_2,u_3\}$ .

So we are left to consider the case when $v,v^{\prime} \in V_i$ for $i \in \{2, 3\}$ . Let $j \in \{2, 3\}$ so $i \neq j$ . We can pick $u_j \in N(v) \cap N(v^{\prime}) \cap V_j$ in at least $2\delta _2 - n \ge 2 \varepsilon n$ ways. Then we can pick $u_1 \in N(v) \cap N(u_j) \cap V_1$ in at least $\delta _1 + \delta _3 - n \ge n/6$ ways. Similarly, we can now pick $u^{\prime}_1 \in N(v^{\prime}) \cap N(u_j) \cap V_1$ distinct from $u_1$ in at least $\delta _1 + \delta _3 - n - 1 \ge n/6$ ways. Observe that $vu_ju_1$ and $v^{\prime}u_ju^{\prime}_1$ are both triangles. By (5), there are at least $\frac 12 \cdot 6 \varepsilon ^2 n^2$ ways to now pick $u_2$ and $u_3$ such that $u_1u_2u_3$ and $u^{\prime}_1u_2u_3$ are both triangles and such that $u_2$ and $u_3$ are disjoint from $\left\{v, v^{\prime}, u_j\right\}$ . All together there are at least

\begin{equation*} 2 \varepsilon \cdot \frac 16 \cdot \frac 16 \cdot 3 \varepsilon ^2 \cdot n^5 \ge \frac {\varepsilon ^3 n^5}{100} \end{equation*}

ways to make these selection. To complete the proof, we observe that every such selection $\left(u_j, u_1, u_2, u_3, u^{\prime}_1\right)$ is a $(v,v^{\prime},5)$ -linking sequence, because $vu_ju_1$ and $u^{\prime}_1u_2u_3$ are both triangles and $v^{\prime}u_ju^{\prime}_1$ and $u_1u_2u_3$ are both triangles.

Proof. We can assume $\sigma$ is small enough and $n$ is large enough so that the following holds:

• $\sigma ^{1/2} \lt \varepsilon$ and, because Observation 8 implies that if Conjecture 11 holds for $k$ , then Conjecture 11 holds for every $\ell$ less than $k$ , we can assume that for every $n^{\prime} \ge \left(1-\sigma ^{1/2}\right)n$ and for every $3 \le \ell \le k$ , we can apply Conjecture 11 with $\ell$ , $\sigma$ , $n^{\prime}$ and $\varepsilon - \sigma ^{1/2}$ playing the roles of $k$ , $\sigma$ , $n$ and $\varepsilon$ , respectively;

• for every $4 \le \ell \le k$ , we can apply Lemma 13 with $\ell$ , $\ell -1$ , $\varepsilon ^3/2^\ell$ and $\sigma ^{1/2}$ playing the roles of $k$ , $t$ , $\eta$ and $\sigma$ , respectively; and

• we can apply Lemma 13 with $3$ , $5$ , $\varepsilon ^3/100$ and $\sigma ^{1/2}$ playing the roles of $k$ , $t$ , $\eta$ and $\sigma$ , respectively.

Let $G$ and $\delta _1, \dotsc, \delta _k$ be as in the statement of Conjecture 5. Let $I \,:\!=\, \left\{i \in [k] \,:\, \delta _i \lt (1 + \varepsilon ) \frac n2\right\}$ , let $\ell = k - |I|$ and let $i_1 \lt \dotsm \lt i_{|I|}$ be an ordering of the elements of $I$ . In the manner described after the statement of Theorem 6, iteratively, for $j$ from $1$ to $|I|$ , we can match every $v \in V_{i_j}$ to a unique $f_v \in V_{i_j+1}$ and then collapse the edge $vf_v$ into $f_v$ . Let $G^{\prime}$ be the resulting graph, so $G^{\prime}$ will be a subgraph of the $n$ -blow-up of $C_\ell$ such that a transversal $C_\ell$ factor of $G^{\prime}$ corresponds to a transversal $C_k$ factor of $G$ . For convenience, we relabel the parts of $G^{\prime}$ as $V^{\prime}_1,\dotsc,V^{\prime}_\ell$ so that, for $i \in [\ell ]$ , we have $G^{\prime}[V^{\prime}_i, V^{\prime}_{i+1}] \ge \delta ^{\prime}_i$ . Note that $\delta ^{\prime}_i \ge (1 + \varepsilon ) \frac n2$ for $i \in [\ell ]$ and

(6) \begin{equation} \sum _{i=1}^{\ell } \delta ^{\prime}_i = \sum _{i=1}^{k} \delta _i - \sum _{j=1}^{k-\ell }\delta _{i_j} \gt k\!\left (1 + \frac 1k + \varepsilon \right )\frac n2 - (k - \ell )(1 + \varepsilon ) \frac n2 = \ell \left (1 + \frac 1\ell + \varepsilon \right ) \frac n2. \end{equation}

Clearly (6) implies $\ell \ge 2$ and that we can assume $\ell \ge 3$ by Remark 10. If $\ell =3$ , then Proposition 15 implies that $G$ is $\left(\varepsilon ^3/100,5\right)$ -linked and if $\ell \ge 4$ , Proposition 14 implies that $G$ is $(\varepsilon ^3/2^\ell, \ell - 1)$ -linked. So by the selection of $\sigma$ and $n$ , we can apply Lemma 13 with $G^{\prime}$ and $\sigma ^{1/2}$ playing the roles of $G$ and $\sigma$ to find a set $A \subseteq V(G^{\prime})$ with $z = |V^{\prime}_i \cap A| \le \sigma ^{1/2}$ for $i \in [\ell ]$ guaranteed by Lemma 13. Conjecture 11 then implies that $G^{\prime} - A$ has a transversal $C_\ell$ -tiling of size at least $n - z - \sigma n$ which implies that $G^{\prime}$ has a transversal $C_\ell$ -factor. This in turn implies that $G$ has a transversal $C_k$ -factor.

Proof. For every $i \in [k]$ , independently and uniformly at random select a partition of $U_i$ into parts $U_{i,1}, \dotsc, U_{i,k}$ each of size $m$ . For every $i,j \in [k]$ and every $v \in V_{i-1} \cup V_{i+1}$ , the random variable $d\!\left(v, U_{i,j}\right)$ is hypergeometrically distributed with expected value $d(v, U_i) \frac{|U_{i,j}|}{|U_i|} = \frac{d(v, U_i)}{k}$ . Therefore, by (C1) and the Chernoff and union bounds, there exists an outcome such that for every $i,j \in [k]$ and every $v \in V_{i-1} \cup V_{i+1}$ we have

(7) \begin{equation} d\!\left(v, U_{i,j}\right) \ge m/2. \end{equation}

This implies that for every $i,j\in [k]$ , the bipartite graph $G[U_{i,j}, U_{i+1,j}]$ is balanced with parts of size $m$ and minimum degree at least $m/2$ , so, by Hall’s Theorem, it contains a perfect matching $M_{i,j}$ . For $j \in [k]$ , let $H_j$ be the graph with vertex set $U_{1,j} \cup \dotsm \cup U_{k,j}$ such that

\begin{equation*} E(H_j)\,:\!=\,\bigcup _{i=1}^{k} M_{i,j} \setminus \left (M_{j-1,j} \cup M_{j,j}\right). \end{equation*}

Note that $H_j$ consists of a collection $\mathcal{P}_{j}$ of $m$ vertex disjoint paths each on $k-1$ vertices such that

• $V(\mathcal{P}_j) = V(H_j) \setminus U_{j,j}$ ;

• every $P \in \mathcal{P}_j$ has exactly one vertex in each of the sets $U_{1,j}, \dotsc, U_{k,j}$ except $U_{j,j}$ ; and

• every $P \in \mathcal{P}_j$ has one end-vertex in $U_{j-1,j}$ and the other end-vertex in $U_{j+1,j}$ .

By (C2), the number of common neighbours in $W_j$ of the endpoints of every path in $\mathcal{P}_j$ is at least

\begin{equation*} 2\!\left (1 + 1/k + \sigma \right )\!mk/2 - mk \gt m = |\mathcal {P}_j|. \end{equation*}

Therefore, we can greedily select such a common neighbour for every path in $\mathcal{P}_j$ to form $\mathcal{T}_j$ , a transversal $C_k$ -tiling of size $m$ . The union $\mathcal{T} \,:\!=\, \mathcal{T}_1 \cup \dotsm \cup \mathcal{T}_k$ is a transversal $C_k$ -tiling of $G$ of size $mk$ . For every $i \in [k]$ , let $U^{\prime}_i \,:\!=\, \left (U_i \cup W_i\right ) \setminus V(\mathcal{T}) = U_{i,i} \cup \left (W_i \setminus V(\mathcal{T})\right )$ , so

\begin{equation*} |U^{\prime}_i| = |U_{i,i}| + |W_i| - m = mk. \end{equation*}

With (C2) and (7), for every $v \in V_{i-1} \cup V_{i+1}$ , we have that

\begin{equation*} d\!\left(v, U^{\prime}_i\right) \ge m/2 + \left (1 + 1/k + \sigma \right )\!mk/2 - m = \left (1 + \sigma \right )\!mk/2. \end{equation*}

Proof of Theorem 3. Define $\eta \,:\!=\, k^{-3} \cdot 2^{-k}$ and $\sigma \,:\!=\, \min \{\varepsilon/4, 0.1 \eta ^{k+1}/(k^4 + 1)\}$ . By Proposition 14, $G$ is $(\eta, k-1)$ -linked. Let $A$ be the set guaranteed by Lemma 13, so there exists $z \le \sigma n$ such that $|A \cap V_i| = z$ for every $i \in [k]$ . Let $m \,:\!=\, \left \lfloor \frac{\sigma ^2 n}{2k} \right \rfloor$ and let $T \,:\!=\, \left \lfloor \frac{n - z}{mk} \right \rfloor -1$ and note that $(T+1)\!mk \le n - z \le (T+2)\!mk$ and that $T$ is bounded above by a constant that depends only on $k$ and $\varepsilon$ . For every $i \in [k]$ , let $V^{\prime}_i \subseteq V_i \setminus A$ where $|V^{\prime}_i| = (T+1)\!mk$ . We will construct $T$ disjoint transversal $C_k$ -tilings each of size $mk$ that each avoid $A$ . Because

\begin{equation*} mkT = (T+2)\!mk - 2mk \ge n - z - \sigma ^2 n, \end{equation*}

this will imply the theorem by the properties of $A$ from Lemma 13.

Note that, by (2), for every $i \in [k]$ and $v \in V_{i-1} \cup V_{i+1}$ , we have

(8) \begin{equation} d\!\left(v, V^{\prime}_i\right) \ge \delta ^*(G) - (n - |V^{\prime}_i|) \ge \left (1 + 1/k + 2\sigma \right )n/2 \ge \left (1 + 1/k + 2\sigma \right )|V^{\prime}_i|/2. \end{equation}

For every $i \in [k]$ , independently and uniformly at random select a partition of $V^{\prime}_i$ into $T+1$ parts $W_{i,0}, \dotsc, W_{i,T}$ each of size $mk$ . For every $i \in [k]$ , every $0 \le t \le T$ and every $v \in V_{i-1} \cup V_{i+1}$ , the random variable $d(v, W_{i, t})$ is hypergeometrically distributed with expected value $d\!\left(v, V^{\prime}_i\right) \frac{|W_{i,t}|}{|V^{\prime}_i|}$ . Therefore, by (8) and the Chernoff and union bounds, there exists an outcome such that for every $i \in [k]$ , $0 \le t \le T$ and $v \in V_{i-1} \cup V_{i+1}$ we have

(9) \begin{equation} d(v, W_{i, t}) \ge \left (1 + 1/k + \sigma \right )\!mk/2. \end{equation}

We will now show by induction on $t$ from $1$ to $T+1$ that there exist $t-1$ disjoint transversal $C_k$ -tilings $\mathcal{T}_1, \dotsc, \mathcal{T}_{t-1}$ each of size $mk$ that are contained in $\bigcup _{i \in k} \bigcup _{s = 0}^{t-1} W_{i,s}$ , and that, for every $i \in [k]$ , if we let $U_{i, t} \,:\!=\, \left (\bigcup _{s=0}^{t-1} W_{i,s}\right ) \setminus \left (\bigcup _{s = 1}^{t-1} V(\mathcal{T}_s)\right )$ , then the following holds:

(10) \begin{equation} d(v, U_{i, t}) \ge (1 + \sigma )\!mk/2 \qquad \text{ for every $v \in V_{i-1} \cup V_{i+1}$.} \end{equation}

This will prove the theorem.

For the base case, note that when $t = 1$ we have that $U_{i,t} = U_{i,1} = W_{i,0}$ for every $i \in [k]$ so (10) holds by (9). Now assume the induction hypothesis holds for some $1 \le t \le T$ . With (9) and (10) we can apply Lemma 17 to find a tiling $\mathcal{T}_t$ of size $mk$ contained in $\bigcup _{i \in [k]} U_{i, t} \cup W_{i, t}$ such that, for every $i \in [k]$ , we have that

\begin{equation*} U_{i,t+1} = \left (\bigcup _{s=0}^{t} W_{i,s}\right ) \setminus \left (\bigcup _{s = 1}^{t} V(\mathcal {T}_s)\right ) = \left (U_{i, t} \cup W_{i, t}\right )\setminus V(\mathcal {T}_t) \end{equation*}

satisfies (10) with $t$ set to $t+1$ . Therefore, the induction hypothesis holds for $t+1$ .

Proof. For brevity, in this proof we call a transversal $C_3$ -tiling a tiling. Let the size of a maximum tiling of $G$ be $m$ and let us assume for a contradiction that $m \le n-2$ . Call a pair of edges $e$ and $f$ dissimilar if $e \in E(G[V_i, V_{i+1}])$ and $f \in E\big(G\big[V_j, V_{j+1}\big]\big)$ for distinct $i,j \in [3]$ . Call a set $F \subseteq E(G)$ a dissimilar matching if the edges in $F$ are disjoint and the edges in $F$ are pairwise dissimilar. For every maximum tiling $\mathcal{T}$ , let $h(\mathcal{T})$ be the maximum size of a dissimilar matching $F \subseteq E(G[U(\mathcal{T})])$ such that every edge in $F$ is uncovered by $\mathcal{T}$ . Recall that an edge $e$ is uncovered by $\mathcal{T}$ if both endpoints of $e$ are disjoint from $V(\mathcal{T})$ . Let $\{\alpha, \beta, \gamma \} = \{\delta _1/n, \delta _2/n, \delta _3/n\}$ and $\{A, B, C\} = \{V_1, V_2, V_3\}$ be labellings such that $\alpha \le \beta \le \gamma$ and

(11) \begin{equation} \delta (G[B,C]) \ge \alpha n, \quad \delta (G[A,C]) \ge \beta n, \quad \text{and}\quad \delta (G[A,B]) \ge \gamma n. \end{equation}

Proof. If $e$ is an edge uncovered by $\mathcal{T}$ and $x \in U(\mathcal{T})$ is such that $d(e, \{x\}) = 1$ , then $ex$ is triangle, and adding $ex$ to $\mathcal{T}$ creates a tiling of size $m+1$ , a contradiction. Similarly, if $e$ and $f$ are disjoint and dissimilar edges that are uncovered by $\mathcal{T}$ and $d(e, T) + d(f, T) \ge 2$ for some $T \in \mathcal{T}$ , then, because $e$ and $f$ are dissimilar, there exist distinct $x,y \in T$ such that $ex$ and $fy$ are both triangles, so if we replace $T$ with $ex$ and $fy$ in $\mathcal{T}$ , then we have a tiling of size $m+1$ , a contradiction.

Proof. Let $\{a_1, \dotsc, a_n\}$ , $\{b_1, \dotsc, b_n\}$ and $\{c_1, \dotsc, c_n\}$ be orderings of $A$ , $B$ and $C$ , respectively, such that $a_ib_ic_i \in \mathcal{T}$ for every $i \in [m]$ (so, when $m + 1 \le i \le n$ , $a_ib_ic_i$ is not a triangle). By (11), we have

\begin{equation*} \sum _{i=1}^{n} \sum _{e \in F} d(e, a_ib_ic_i)= \sum _{e \in F} d(e, V(G)) \ge (\alpha + \beta - 1)n + (\alpha + \gamma - 1)n + (\beta + \gamma - 1)n \ge n. \end{equation*}

Therefore, if $0=\sum _{e \in F} d(e, U(\mathcal{T})) = \sum _{i=m+1}^{n}\sum _{e \in F} d(e, a_ib_ic_i)$ , then there exists $1 \le i \le m$ such that $\sum _{e \in F} d(e, a_ib_ic_i) = 2$ . This proves the first statement.

To see the second statement, assume for a contradiction that there exists a maximum tiling $\mathcal{T}$ such that $h(\mathcal{T}) = 3$ . This means that there exists a dissimilar matching $F$ such that $|F| = 3$ and such that every edge in $F$ is uncovered by $\mathcal{T}$ . By the first part of the statement, there either exists $e \in F$ such $d(e, U(\mathcal{T})) \ge 1$ , or there exist two edges $e,f \in F$ and $T \in \mathcal{T}$ such that $d(e, T) + d(f, T) \ge 1$ . Because every edge in $F$ is uncovered by $\mathcal{T}$ , this contradicts Claim 18.1.

Proof. Suppose for a contradiction that the statement is false and assume $\mathcal{T}$ and a dissimilar matching $F$ in $G[U(\mathcal{T})]$ have both been selected so that

1. (A) there exists $e \in F$ such that $e \in E(G[B,C])$ if possible, and,

2. (B) subject to (A), $|F|$ is as large as possible.

Note that Claim 18.2, implies that $|F| \le h(\mathcal{T}) \le 2$ , so if there exists $e \in F$ such that $e \in E(G[B,C])$ , then $F$ has at most one edge that is contained in $E(G[A,B]) \cup E(G[A,C])$ . If there is no $e \in F$ that is in $E(G[B,C])$ , then by the selection of $\mathcal{T}$ and $F$ (c.f. (A)), for every maximum tiling $\mathcal{T}$ there does not exist $e \in E(G[B,C])$ , so our contrary assumption implies $|F| \le h(\mathcal{T}) \le 1$ . Therefore, in all cases, $F$ has at most one edge that is contained in $E(G[A,B]) \cup E(G[A,C])$ . Let $\{X, Y\} = \{B, C\}$ be a labelling such that $F$ does not contain an edge in $E(G[A,X])$ .

Let $W \subseteq U$ be the set of vertices that are incident to an edge in $F$ . The fact that $|\mathcal{T}| \le n -2$ , implies that there exist nonadjacent vertices $a \in A \setminus W$ and $x \in X \setminus W$ that are uncovered by $\mathcal{T}$ . Let $\{a_1, \dotsc, a_n\}$ , $\{x_1, \dotsc, x_n\}$ and $\{y_1, \dotsc, y_n\}$ be orderings of $A$ , $X$ and $Y$ , respectively such that $a_n = a$ , $x_n = x$ and $a_ix_iy_i \in \mathcal{T}$ for every $i \in [m]$ . We can assume that the orderings are such that $W$ is contained in the set $\left\{a_{n-1}, x_{n-1}, y_{n-1}, y_n\right\}$ with $x_{n-1}y_{n-1} \in F$ if $F \cap E(G[X,Y]) = F \cap E(G[B,C]) \neq \emptyset$ .

Since $a$ and $x$ are nonadjacent, $d(x, a_n) + d(a, x_n) + d(a, y_n) = d(x, a) + d(a, x) + d(a, y_n) \le 1$ , and, by (11) and the fact that $\alpha \le \beta \le \gamma$ , we have

\begin{equation*} \sum _{i=1}^{n} d(x, a_i) + d(a, x_i) + d(a, y_i) = d(x, A) + d(a, X) + d(a, Y) \ge \beta n + \beta n + \gamma n \ge 2n, \end{equation*}

so there must exist $i \in [n-1]$ such that $d(x, a_i) + d(a, x_i) + d(a, y_i) = 3$ . Note that $i \neq n-1$ , because if $ax_{n-1}$ is an edge, then the fact that $F \cap E(G[A,X]) = \emptyset$ and the maximality of $F$ imply that $x_{n-1}y_{n-1} \in F$ , but, because $\mathcal{T}$ is a maximum tiling, $ax_{n-1}y_{n-1}$ is not a triangle. Since $F \cap E(G[A,X]) = \emptyset$ , the maximality of $F$ also implies that that $d(x, a_j) = 0$ for every $m+1 \le j \le n-2$ , so it must be that $i \in [m]$ , that is, that $T = a_ix_iy_i$ is a triangle in $\mathcal{T}$ . Therefore, we can swap $T$ for the triangle $ax_iy_i$ in $\mathcal{T}$ to form the maximum tiling $\mathcal{T}^{\prime}$ . Because the edge $a_ix$ is uncovered by $\mathcal{T}^{\prime}$ and $W \subseteq U(\mathcal{T}^{\prime})$ , we have a contradiction to the selection of $\mathcal{T}$ and $F$ (c.f. (B)).

Proof. Since $y + z \le x + y + z \lt 1$ , one of $y$ or $z$ is less than $1/2$ , so there exists an edge $bc \in E(G[B^{\prime},C^{\prime}])$ . Because $G[A^{\prime}, B^{\prime}, C^{\prime}]$ is triangle-free,

\begin{equation*} 0 = |N(b, A^{\prime}) \cap N(c, A^{\prime})| \ge d(b, A) + d(c, A) - |A| - xn \ge \gamma n + \beta n - n - x n = n/3 - x n, \end{equation*}

so $x \ge 1/3$ . By considering an edge in $E(G[A^{\prime},B^{\prime}])$ and an edge in $E(G[A^{\prime},C^{\prime}])$ the same argument yields $z \ge \beta - 1/2$ and $y \ge \gamma - 1/2$ , respectively.

Proof. We first show that both $x \lt \gamma$ and $y \lt \gamma$ . To this end, note that if $x \ge \gamma$ , then $x + y \ge \gamma + \gamma - 1/2 = 2\gamma - 1/2$ . If $y \ge \gamma$ , then, because $\gamma - 1/2 \le 5/6 - 1/2 = 1/3$ , we also have $x + y \ge 1/3 + \gamma \ge 2\gamma - 1/2$ . So, in either case, we have the following contradiction

\begin{equation*} 1 \gt x + y + z \ge 2\gamma - 1/2 + \beta - 1/2 = 1/3 + \gamma \ge 1. \end{equation*}

Similarly, it is clear that $z \lt 1/2$ , since otherwise $x + y + z \ge 1/3 + (\gamma - 1/2) + 1/2 \ge 1$ , a contradiction.

Assume $y \ge 1/2$ and let $b \in B^{\prime}$ . Note that there are at most $(1-\gamma )n$ vertices $a \in N_{\overline{G}}(b, A^{\prime})$ . For every such $a$ we can find a $4$ -vertex path $ab^{\prime}a^{\prime}b$ in $G[A^{\prime},B^{\prime}]$ . Indeed, since $y \lt \gamma$ , there exists $b^{\prime} \in N(a, B^{\prime})$ . Then, because $2 \gamma + \beta \ge 2$ and $1 \gt x + y + z$ ,

\begin{equation*} x \lt 1 - y - z \le 1/2 - z \le 1/2 - (\beta - 1/2) = 1 - \beta \le 2\gamma - 1. \end{equation*}

Since $|N(b, A) \cap N(b^{\prime}, A)| \ge 2\gamma n - n\gt xn$ , there exists $a^{\prime} \in |N(b, A^{\prime}) \cap N(b^{\prime}, A^{\prime})|$ , giving us the $4$ -path $ab^{\prime}a^{\prime}b$ . Note that $N(a^{\prime}, C^{\prime})$ and $N(b^{\prime}, C^{\prime})$ are disjoint and that every $c \in C^{\prime}$ that is adjacent to both $a$ and $b$ is not adjacent to $a^{\prime}$ and not adjacent to $b^{\prime}$ . Therefore, $|P_3( b, C^{\prime}, a)|$ is at most

\begin{equation*} |C^{\prime} \setminus \left (N(a^{\prime}, C^{\prime}) \cup N(b^{\prime}, C^{\prime})\right )| \le (1 - z)n - (\beta - z)n - (1/2 - z)n = (z - \beta + 1/2)n, \end{equation*}

and $|P_3(b, C^{\prime}, A^{\prime})|/n^2 \le (1 - \gamma )(z - \beta + 1/2)$ . On the other hand,

\begin{equation*} |P_3(b, C^{\prime}, A^{\prime})| \ge \sum _{c \in N(b, C^{\prime})}d(c, A^{\prime})\ge (1/2 - z)n \cdot (\beta - x)n. \end{equation*}

The claim then follows because there are no solutions to

\begin{equation*} (1 - \gamma )(z - \beta + 1/2) \ge (1/2 - z)(\beta - x), \end{equation*}

when $x \ge 1/3$ , $y \ge 1/2$ and $z \ge \beta - 1/2$ . (See Appendix B in [Reference Ergemlidze and Molla2] for a proof of this fact.)

Proof. Assume the contrary and let $a \in A^{\prime}$ and $b \in B^{\prime}$ be such that there is no $(a,b)$ -path in $G[A^{\prime}, B^{\prime}]$ with at most $4$ vertices. Let $b^{\prime} \in N(a, B^{\prime})$ and $a^{\prime} \in N(b, A^{\prime})$ . By our contrary assumption, we have that $N(a, B^{\prime}) \cap N(a^{\prime}, B^{\prime}) = \emptyset$ so $y \ge |N(a, B) \cap N(a^{\prime}, B)|/n \ge 2\gamma - 1$ , By the same argument, $N(b, A^{\prime}) \cap N(b^{\prime}, A^{\prime}) = \emptyset$ and $x \ge 2\gamma - 1$ . Since $\beta \le 2/3$ , we have $2 \gamma - 1 = 2(4/3 - \beta ) - 1 = 5/3 - 2\beta \ge 1 - \beta$ , so

\begin{equation*} z \lt 1 - x - y \le 1 - 2(2 \gamma - 1) \le 1 - 2(1 - \beta ) = 2 \beta - 1 \le |N(a, C) \cap N(a^{\prime}, C)|/n, \end{equation*}

therefore there exists $c \in N(a, C^{\prime}) \cap N(a^{\prime}, C^{\prime})$ . But then $N(c, B^{\prime})$ cannot intersect $N(a, B^{\prime}) \cup N(a^{\prime}, B^{\prime})$ , so

\begin{equation*} (1/2 - y) + 2(\gamma - y) \le |N(c, B^{\prime}) \cup N(a, B^{\prime}) \cup N(a^{\prime}, B^{\prime})|/n \le 1 - y \end{equation*}

which implies that $y \ge \gamma - 1/4$ , therefore $y\ge 5/12$ . But (14) has no solutions when $y \ge 5/12$ , $x \ge 1/3$ and $z \ge \beta -1/2$ . (See Appendix B in [Reference Ergemlidze and Molla2] for a proof of this fact.) This is a contradiction.

Proof. Let $a \in A^{\prime}$ . We first get an upper bound on $|P_3(a, C^{\prime}, B^{\prime})|$ . Note that there are at most $(1 - \gamma )n$ ways to select $b \in B^{\prime}$ that is not adjacent to $a$ . By Claim 20.3, there exists $a^{\prime} \in A^{\prime}$ and $b^{\prime} \in B^{\prime}$ such that $ab^{\prime}a^{\prime}b$ is a path. Note that every vertex $c \in C^{\prime}$ that is adjacent to both $a$ and $b$ cannot be in $N(a^{\prime}, C^{\prime}) \cup N(b^{\prime}, C^{\prime})$ . Since $N(a^{\prime}, C^{\prime})$ and $N\!\left(b^{\prime}, C\right)$ are disjoint, we have the cardinality of $P_3(a, C^{\prime}, b)$ is at most

\begin{equation*} |C^{\prime}| - d(a^{\prime}, C^{\prime}) - d(b^{\prime}, C^{\prime}) \le (1-z)n - (\beta - z)n - (1/2 - z)n = (z - \beta + 1/2)n \end{equation*}

Therefore, $|P_3(a,C^{\prime}, B^{\prime})|/n^2 \le (1 - \gamma )(z - \beta + 1/2)$ . We also have that $|P_3(a, C^{\prime}, B^{\prime})| \ge \sum _{c \in N(a, C^{\prime})}d(c, B^{\prime})\ge (\beta - z)n(1/2 - y)n$ , so

(15) \begin{equation} (1 - \gamma )(z - \beta + 1/2) \ge |P_{3}(a,C^{\prime}, B^{\prime})|/n^2 \ge (\beta - z)(1/2 - y). \end{equation}

By considering $b \in B^{\prime}$ and estimating $P_{3}(A^{\prime},C^{\prime}, b$ ), the same arguments yield that

(16) \begin{equation} (1 - \gamma )(z - \beta + 1/2) \ge |P_{3}(A^{\prime},C^{\prime}, b)|/n^2 \ge \sum _{c \in N(b, C^{\prime})}d(c,A^{\prime})/n^2 \ge (\beta - x)(1/2 - z). \end{equation}

But (15), (16) and (14) cannot hold simultaneously when $x \ge 1/3$ , $y \ge 1/3$ and $z \ge \beta - 1/2$ . (See Appendix B in [Reference Ergemlidze and Molla2] for a proof of this fact.) Therefore $y \lt 1/3$ .

Now we will show that $x\lt \beta$ . Indeed, if $\beta \le x$ , we have

\begin{equation*} y\ge \gamma -1/2= 5/6-\beta \ge 5/6-x \gt y+z-1/6, \end{equation*}

so $z \lt 1/6$ . With (15) we get $(\beta -1/3)(1/6 - \beta + 1/2) \ge (\beta - 1/6)(1/2 - y)$ . Plugging $y\lt 1/3$ we get that $-\beta ^2+(5/6)\beta -1/4\gt 0$ which does not have a solution, a contradiction.

Proof. Assume the contrary and let $a_1 \in A^{\prime}$ . Then, for every $c_1 \in C^{\prime}\setminus N(a^{\prime},C^{\prime})$ , there exists $a_2 \in A^{\prime}$ and $c_2 \in C^{\prime}$ such that $a_1c_2a_2c_1$ is a path, so, since $G[A^{\prime},B^{\prime},C^{\prime}]$ is triangle-free, $|P_3(a_1, B^{\prime}, c_1)|$ is at most

\begin{equation*} |B^{\prime} \setminus (N(a_2, B^{\prime}) \cup N(c_2, B^{\prime})| \le |B^{\prime}| - (d(a_2, B) - yn + d(c_2, B) - yn) \le \left (y - \gamma + 1/2\right )\!n. \end{equation*}

Since $a_1$ has at most $(1 - \beta )n$ non-neighbours in $C^{\prime}$ , we have that

\begin{equation*} (1 - \beta )\left (y - \gamma + 1/2\right ) \ge |P_3(a_1, B^{\prime}, C^{\prime})|/n^2 = \sum _{b \in N(a_1, B^{\prime})}d(b, C^{\prime})/n^2 \ge (\gamma - y) \left (1/2 - z\right ) \end{equation*}

which is impossible when $x \ge 1/3$ , $1/3 \gt y \ge \gamma - 1/2$ and $z \ge \beta - 1/2$ . (See Appendix B in [Reference Ergemlidze and Molla2] for a proof of this fact.)

Proof. Since $|N(a_1, B) \cap N(a_2, B)|/n \ge 2 \gamma - 1 \ge 1/3 \gt y$ , there exists $b \in B^{\prime}$ that is adjacent to both $a_1$ and $a_2$ . Since $G[A^{\prime},B^{\prime},C^{\prime}]$ is triangle-free (17) implies that

\begin{equation*} 1/2 - z \le d(b, C^{\prime})/n \le |C^{\prime} \setminus (N(a_1, C^{\prime}) \cup N(a_2, C^{\prime}))|/n \le 1 - z - 2(\beta - z) = 1 - 2\beta + z, \end{equation*}

so $z \ge \beta - 1/4$ .

Proof. Assume the contrary, so there exists $a_3 \in A^{\prime}$ such that $N(a_1,C^{\prime})$ , $N(a_2, C^{\prime})$ and $N(a_3, C^{\prime})$ are pairwise disjoint and that there exists $c_3 \in C^{\prime}$ such that $N(c_1,A^{\prime})$ , $N(c_2, A^{\prime})$ and $N(c_3, A^{\prime})$ are pairwise disjoint. This implies that

\begin{equation*} (1-x)n = |A^{\prime}| \ge d(c_1, A^{\prime}) + d(c_2, A^{\prime}) + d(c_3, A^{\prime}) \ge 3(\beta - x)n, \end{equation*}

so $x \ge (3 \beta - 1)/2$ , and, by considering the sets $N(a_1, C^{\prime})$ , $N(a_2, C^{\prime})$ and $N(a_3, C^{\prime})$ , we similarly have that $z \ge (3\beta - 1)/2$ . This implies that

\begin{equation*} y \lt 1 - x - z \le 1 - (3\beta - 1) = 2 - 3\!\left (4/3 - \gamma \right ) = 3\gamma - 2. \end{equation*}

Note that $|N(a_1, B) \cap N(a_2, B) \cap N(a_3, B)| \ge 3 \gamma n - 2|B| = (3 \gamma - 2)n \gt y n$ , so there exists $b \in N(a_1, B^{\prime}) \cap N(a_2, B^{\prime}) \cap N(a_3, B^{\prime})$ . Note that $N(b, C^{\prime})$ must be disjoint from $N(a_1, C^{\prime}) \cup N(a_2, C^{\prime}) \cup N(a_3, C^{\prime})$ so, since $N(a_1, C^{\prime})$ , $N(a_2, C^{\prime})$ and $N(a_3, C^{\prime})$ are pairwise disjoint,

\begin{equation*} (1 - z)n = |C^{\prime}| \ge d(b, C^{\prime}) + d(a_1, C^{\prime}) + d(a_2, C^{\prime}) + d(a_3, C^{\prime}) \ge (1/2 - z + 3(\beta - z))n, \end{equation*}

so $z \ge \beta - 1/6$ . But then $1 \gt x + y + z \ge 1/3 + \gamma - 1/2 + \beta - 1/6 = 1$ , a contradiction.

Proof. Since $c_1a_2$ and $c_2a_1$ are edges, we have the desired path if $N(a, C^{\prime})$ intersects either $N(a_1, C^{\prime})$ or $N(a_2, C^{\prime})$ . So assume otherwise, that is, assume that the sets $N(a, C^{\prime})$ , $N(a_1, C^{\prime})$ and $N(a_2, C^{\prime})$ are pairwise disjoint. By Claim 20.2, there exists $c \in N(a, C^{\prime})$ . Because $N(c_1, A^{\prime})$ and $N(c_2, A^{\prime})$ are disjoint, Claim 20.7 implies that $N(c, A^{\prime})$ must intersect one of $N(c_1, A^{\prime})$ or $N(c_2, A^{\prime})$ and this gives us the desired path.

Proof. Let $a \in A^{\prime}$ . First suppose $a \in A_i = N(c_i, A^{\prime})$ for some $i \in \{1, 2\}$ , then $a$ has no neighbours in $B_i$ , so