# Partitioning a 2-edge-coloured graph of minimum degree $2n/3+o(n)$ into
three monochromatic cycles

Peter Allen  ,  Julia Böttcher  ,  Richard Lang  ,  Jozef Skokan  and  Maya
Stein  London School of Economics, London, WC2A 2AE, UK.
<EMAIL_ADDRESS>Institut für Informatik, 69120
Heidelberg, Germany<EMAIL_ADDRESS>Department of
Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801,
USA.  Departamento de Ingeniería Matemática y Centro de Modelamiento
Matemático, Universidad de Chile, Santiago, Chile<EMAIL_ADDRESS>
###### Abstract.

Lehel conjectured in the 1970s that every red and blue edge-coloured complete
graph can be partitioned into two monochromatic cycles. This was confirmed in
2010 by Bessy and Thomassé. However, the host graph $G$ does not have to be
complete. It it suffices to require that $G$ has minimum degree at least
$3n/4$, where $n$ is the order of $G$, as was shown recently by Letzter,
confirming a conjecture of Balogh, Barát, Gerbner, Gyárfás and Sárközy. This
degree condition is asymptotically tight.

Here we continue this line of research, by proving that for every red and blue
edge-colouring of an $n$-vertex graph of minimum degree at least $2n/3+o(n)$,
there is a partition of the vertex set into three monochromatic cycles. This
approximately verifies a conjecture of Pokrovskiy and is essentially tight.

The research leading to these results was partly supported by the DFG grant
450397222 (R. Lang) and also by Fondecyt Regular Grant 1183080, CONICYT +
PIA/Apoyo Basal, Código AFB170001 (M. Stein).

##  1\. Introduction

Influentially, Lehel conjectured that every colouring of the edges of the
complete graph $K_{n}$ with two colours admits two monochromatic cycles of
distinct colours whose vertex sets partition $V(K_{n})$. Here, an edge, a
single vertex, and the empty set each count as a cycle. Łuczak, Rödl and
Szemerédi [31] confirmed this conjecture for sufficiently large $n$ after
preliminary work of Gyárfás [13]. Their result was improved by the first
author [1], and finally, Bessy and Thomassé [6] resolved the conjecture for
all $n$.

Since the early 1990s the field of cycle partitioning has evolved in many
directions. One natural question extensively studied is to what extend Lehel’s
conjecture generalizes to more than two colours. Here, a landmark result is
due to Erdős, Gyárfás and Pyber [11], who showed that any $r$-edge-coloured
complete graph $K_{n}$ admits a partition into ${25r^{2}\log r}$ monochromatic
cycles and conjectured that $r$ cycles suffice. The upper bound was later
improved to $100r\log r$ by Gyárfás, Ruszinkó, Sárközy and Szemerédi [15] for
large $n$. Pokrovskiy [33] disproved the conjecture of Erdős, Gyárfás and
Pyber by providing an $r$-edge-colouring of $K_{n}$ that needs $r+1$ cycles
for every $r\geq 3$ and infinitely many $n$. So far, it is far from clear what
is the best possible number of cycles, even for small $r$, showing that this
problem is difficult.

Other variants of the problem that received much attention in the past decade
include the appearance of subgraphs other than cycles, the use of colourings
with an unbounded number of colours (but local restrictions on the
colourings), and analogues for hypergraphs, to highlight just a few. We refer
the reader to the recent survey of Gyárfás [14] and the references therein for
more detail. Another important direction, which is the variant we are most
interested in here, concerns the replacement the complete graph $K_{n}$ by a
non-complete host graph. This has been investigated for almost complete graphs
[29], complete bipartite graphs [16, 26, 27], graphs with fixed independence
number [36], infinite graphs [10, 35] and random graphs [22, 24] among others.
We are interested in the problem for graphs of large minimum degree.

The study of minimum degree conditions for spanning substructures has a long
tradition in extremal graph theory (see for example the survey [23] for an
overview), and so it is natural to seek a variant of Lehel’s conjecture for
host graphs of large minimum degree. Balogh, Barát, Gerbner, Gyárfás and
Sárközy [4] conjectured the following: For any $2$-edge-colouring of the edges
of any $n$-vertex graph $G$ of minimum degree $3n/4$, there are two distinctly
coloured monochromatic cycles which together partition the vertices of $G$.
Examples show that this would be tight. In support of their conjecture, they
proved an approximate version in which $G$ has minimum degree $3n/4+o(n)$ and
the cycles are allowed to miss $o(n)$ vertices. DeBiasio and Nelsen [9] showed
that under this (stronger) degree condition a complete partition is possible.
Finally, Letzter [28] resolved the full conjecture for all sufficiently large
$n$.

Motivated by these advances, Pokrovskiy [34] conjectured that analogous
results are true for graphs of lower minimum degree. In particular, he
conjectured that any 2-edge-coloured graph of minimum degree $2n/3$ can be
partitioned into 3 monochromatic cycles. The construction in Figure 1 shows
that this bound is essentially tight. Our main result confirms Pokrovskiy’s
conjecture approximately.

$m$$m+2$$m+2$$a$$b$$K$$K^{\prime}$$K^{\prime\prime}$ Figure 1. A graph on
$3m+6$ vertices, consisting of three vertex disjoint cliques $K$, $K^{\prime}$
and $K^{\prime\prime}$ and two additional vertices $a$ and $b$. Here, $K$ and
$K^{\prime}$ have $m+2$ vertices each, all edges of $K$ are coloured red and
all edges of $K^{\prime}$ are coloured blue. The third clique
$K^{\prime\prime}$ is of size $m$ and its edges can be coloured either red or
blue. Further, all edges between $K$ and $K^{\prime\prime}$ are present and
coloured blue and all edges between $K^{\prime}$ and $K^{\prime\prime}$ are
present and coloured red. The vertex $a$ has blue edges to $K\cup
K^{\prime\prime}$ and the vertex $b$ has red edges to $K^{\prime}\cup
K^{\prime\prime}$.

######  Theorem 1.1.

For any $\beta>0$, there is $n_{0}$ such that for any colouring with two
colours of the edges of any graph $G$ on $n\geq n_{0}$ vertices and minimum
degree at least $(2/3+\beta)n$, there is a partition of $V(G)$ into three
monochromatic cycles.

The proof of this theorem is partly based on tried and tested techniques such
as graph regularity, the use of matchings, and absorption, but also draws from
several new ideas which could prove useful for future research in this area.
For an outline of our approach, see Section 2.

#### Organization.

The remainder of this paper is organized as follows. In the next section we
outline our proof method. In Section 3 we then introduce some notation and
concepts related to the regularity method. In Section 4 we present the proof
of Theorem 1.1 alongside the main lemmas needed for this proof. Sections 5, 6,
7 and 8 are dedicated to the Lemmas concerning finding the components,
distributing the exceptional vertices and solving the cases of extremal
colourings, respectively. Finally, we offer some open problems and conjectures
in Section 9.

##  2\. Proof outline

In this section we shall briefly outline our proof, which was inspired by a
method developed by Garbe, Lang, Lo, Mycroft and Sanhueza-Matamala [12] to
solve cycle partitioning problems in hypergraphs.

Suppose that $G$ is an $n$-vertex graph of minimum degree at least $2n/3+o(n)$
and that each of its edges is coloured red or blue. We start by applying the
regularity lemma (Lemma 3.8) to obtain a regular partition and the
corresponding reduced graph $\mathcal{G}$. Roughly speaking, our strategy is
to distinguish the case that $\mathcal{G}$ is close to an extremal
configuration, which can be solved with arguments tailored to this particular
structure (see Lemma 4.4), or we can find three monochromatic components
$C_{1}$, $C_{2}$, $C_{3}$ in $\mathcal{G}$ whose union $C$ has the following
property (see Lemma 4.2). Every stable set $S$ in $C$ has linearly many more
neighbours in $\mathcal{G}$ than $|S|$ (see Definition 3.3). From the LP
duality of maximum fractional matchings and minimum vertex covers we obtain
that $C$ admits a _perfect $2$-matching_ in a robust way, where a perfect
$2$-matching is a spanning union of vertex disjoint edges and cycles (see
Theorem 3.2 and the discussion preceding it).

As is canonical, we then connect the clusters of the components in the perfect
$2$-matching by short monochromatic paths (see Lemma 3.9), which we can
further require to contain certain _exceptional vertices_ (see Lemma 4.6).
Creating these paths will create some imbalances between the clusters of the
matching edges, which we correct by solving a weighted matching problem in an
auxiliary graph and using the robustness of the perfect $2$-matching (see
Lemma 4.7). To finish the proof, we apply the blow-up lemma (Lemma 3.10) to
find monochromatic spanning paths in each of the components of the perfect
$2$-matching. Together with the short paths constructed earlier this yields
the desired cycle partition.

We remark that our approach has the advantage that it avoids a number of
technicalities from earlier approaches, and allows us to isolate the main
steps (finding the components, distributing exceptional vertices and solving
extremal configurations) cleanly in separate lemmas.

##  3\. Preliminaries

In this section we introduce some notation and tools, which we will need for
the proof of Theorem 1.1.

###  3.1. Notation

We let $[n]$ denote the set $\\{1,2,\dots,n\\}$. Let $G=(V,E)$ be a graph. The
_order_ of $G$ is $|V(G)|$ and the _size_ of $G$ is $|E(G)|$. We denote the
_neighbourhood_ of a vertex $v$ by $N_{G}(v)$ and write
$N_{G}(v,W)=N_{G}(v)\cap W$ for a set of vertices $W\subseteq V(G)$. We denote
the _degree_ of $v$ by $\deg_{G}(v)=|N_{G}(v)|$ and set
$\deg_{G}(v,W)=|N_{G}(v)\cap W|$. For a set of vertices $S\subseteq G$ we
write $N_{G}(S)=\bigcup_{s\in S}N(s)$. If it is clear from the context, we
often drop the index $G$. We write $G[W]$ for the subgraph of $G$ induced by
the vertices in $W$ and for a set $U$ disjoint from $W$ we write $G[W,U]$ for
the bipartite subgraph of $G$ containing all edges in $E(G)$ with one end in
$U$ and one in $W$. For another graph $H$ we denote by $G\cup H$ the graph on
vertex set $V(G)\cup V(H)$ and edge set $E(G)\cup E(H)$. We write $H\subseteq
G$ if $H$ is a subgraph of $G$. A _stable set_ in $G$ is a set of vertices
$S\subseteq V(G)$ such that there are no edges with both endpoints in $S$. For
vertices $v$ and $w$, a $v,w$-_path (walk)_ is a path (walk) that starts in
$v$ and ends in $w$. Similarly, for vertex sets $W$ and $W^{\prime}$, a
$W,W^{\prime}$-path (walk) is a path (walk) that starts in $W$ and ends in
$W^{\prime}$.

Suppose that $G$ is a graph whose edges are coloured with red and blue. We
denote by $G_{\text{red}}$ ($G_{\text{blue}}$) the subgraph on $V(G)$ that
contains the red (blue) edges. For a vertex $v$ of $G$ we also write
$N_{\text{red}}(v)$, $N_{\text{blue}}(v)$, $\deg_{\text{red}}(v)$,
$\deg_{\text{blue}}(v)$ for $N_{G_{\text{red}}}(v)$, $N_{G_{\text{blue}}}(v)$,
$\deg_{G_{\text{red}}}(v)$, $\deg_{G_{\text{blue}}}(v)$ for the
neighbourhood/degree of $v$ in the respective colour. We will say that $w\in
N_{\text{red}}(v)$ is a _red neighbour_ of $v$ and likewise for colour blue. A
_red (blue) component_ of $G$ is a component of $G_{\text{red}}$
($G_{\text{blue}}$). In particular a vertex $v$ with $\deg_{\text{red}}(v)=0$
is in a red component of order 1. For convenience of notation, we also count
the empty graph as a component.

In our coloured graphs we do occasionally allow parallel edges (more
precisely, this is the case for our so-called reduced graphs) – however, there
will always be at most one red edge and at most one blue edge between any pair
of vertices. For such a multi-graph $G$ we denote by $\delta(G)$ the minimum
degree of the underlying simple graph, and by $\deg_{G}(u)$ the degree of $u$
in the underlying simple graph.

###  3.2. Perfect 2-matchings

We make use of the concept of a $2$-matching in a graph $G$.

######  Definition 3.1 (Perfect $2$-matching).

A _perfect $2$-matching_ of a graph $G$ is a spanning subgraph of $G$ which is
the disjoint union of cycles and single edges.

The next theorem is a convenient analogue of Tutte’s classical
characterization of perfect matchings for $2$-matchings. It follows easily
from the fact that maximum fractional matching and minimum vertex cover are LP
dual problems both of which have optimal solutions which are half-integral,
and the LP-duality theorem. For a proof of this result see, e.g., [37,
Corollary 30.1a].

######  Theorem 3.2 (Tutte’s Theorem for $2$-matchings).

A graph $G$ has a perfect $2$-matching if and only if every stable set
$S\subseteq V(G)$ satisfies $|N(S)|\geq|S|$.

In order to apply this in our proof, we will need a more robust version of the
condition $|N(S)|\geq|S|$. This motivates the following definition.

######  Definition 3.3 ($\gamma$-robust Tutte).

We say that a graph $G$ on $n$ vertices is _$\gamma$ -robust Tutte_ if for
every non-empty stable subset $S$ of $V(G)$ we have $|N(S)|\geq|S|+\gamma n$.

###  3.3. Hamiltonicity

A _Hamilton cycle_ (_Hamilton path_) in a graph $G$ is a cycle (path) that
covers all the vertices of $G$. Chvátal’s theorem provides a degree sequence
criterium for the existence of Hamilton cycles.

######  Theorem 3.4 (Chvátal [7]).

Let $G$ be a graph with vertex degree sequence $d_{1}\leq\dots\leq d_{n}$. If
for every $1\leq i<n/2$ we have $d_{i}\geq i+1$ or $d_{n-i}\geq n-i$, then $G$
has a Hamilton cycle.

As a corollary we get the following version for balanced bipartite graphs,
which we shall use in our proof.

######  Corollary 3.5 (Bipartite Chvátal).

Let $H$ be a bipartite graph with bipartition classes $X$ and $Y$, each of
size $n$. Let $X$ have vertex degree sequence $x_{1}\leq\dots\leq x_{n}$ and
$Y$ have vertex degree sequence $y_{1}\leq\dots\leq y_{n}$. If for every
$i\in[n-1]$ we have $x_{i}\geq i+1$ or $y_{n-i}\geq n-i+1$, then $H$ is
Hamiltonian.

###### Proof.

Obtain $H^{\prime}$ from $H$ by adding edges between vertices of $Y$ until
$H^{\prime}[Y]$ is complete. So every vertex in $Y$ gains $n-1$ new
neighbours. Let $d_{1},\ldots,d_{2n}$ be the degree sequence of $H^{\prime}$.
By assumption we have either $x_{n-1}\geq n$ or $y_{1}\geq 2$. In either case,
$y_{i}\geq 2$ for all $i\in[n]$. Hence, for each $i\in[n]$ we have
$d_{i}=x_{i}$ and $d_{2n-i+1}=y_{n-i+1}+n-1$. It follows that $d_{i}\geq i+1$
or $d_{2n-i}\geq 2n-i$ for $i\in[n-1]$. By Theorem 3.4, $H^{\prime}$ has a
Hamilton cycle $C$, which, as $|X|=|Y|$, has no edges within $Y$. Thus $C$ is
a Hamilton cycle of $H$. ∎

This also implies the following result on Hamilton paths.

######  Corollary 3.6.

Let $H$ be a bipartite graph with bipartition classes $X_{1}$, $X_{2}$, each
of size $n$. If for each $i\in\\{1,2\\}$, and for each $u\in X_{i}$ we have
$\deg_{H}(u,X_{3-i})\geq\frac{1}{2}n+1$, then for any $w\in X_{1}$,
$w^{\prime}\in X_{2}$ there is a Hamilton $w,w^{\prime}$-path in $H$.

###### Proof.

Obtain the graph $H^{\prime}$ from $H$ by adding a new vertex $v$ to $X_{1}$,
a new vertex $v^{\prime}$ to $X_{2}$ and the edges
$wv^{\prime},v^{\prime}v,vw^{\prime}$. It is easy to verify that the
conditions of Corollary 3.5 are satisfied, which gives a Hamilton cycle in
$H^{\prime}$. As this cycle clearly uses the edges
$wv^{\prime},v^{\prime}v,vw^{\prime}$ it contains Hamilton $w,w^{\prime}$-path
in $H$. ∎

We use Corollary 3.6 to obtain Hamilton paths in the following somewhat
specialized setting, which appears in the analysis of our extremal cases.

######  Lemma 3.7.

Let $0<\mu\leq 1$, $n\geq 100\mu^{-1}$, and let $H$ be an $n$-vertex graph on
$V(H)=A\dot{\cup}B$ with $A^{\prime}\subseteq A$, $|B|\leq|A|\leq|B|+\mu n$
and $|A^{\prime}|\leq\mu n$, such that

  1. ()

for each $v\in A$ we have $\deg_{H}(v,B)\geq(\frac{1}{4}+3\mu)n$,

  2. ()

for each $v\in B$ we have $\deg_{H}(v,A)\geq(\frac{1}{4}+3\mu)n$, and

  3. ()

for each $v\in A\setminus A^{\prime}$ we have $\deg_{H}(v,A)\geq 3\mu n$.

Let $u,u^{\prime}\in V(H)\setminus A^{\prime}$ be distinct vertices such that
if both $u,u^{\prime}\in A\setminus A^{\prime}$ then $|A|\geq|B|+1$. Then
there exists a Hamilton $u,u^{\prime}$-path in $H$.

###### Proof.

We start paths $P$ in $u$ and $P^{\prime}$ in $u^{\prime}$. If
$u,u^{\prime}\in B$, we extend $P$ by adding an edge from $u$ to an arbitrary
neighbour in $A\setminus A^{\prime}$. Similarly, if $u,u^{\prime}\in
A\setminus A^{\prime}$, we extend $P^{\prime}$ by adding an edge from
$u^{\prime}$ to an arbitrary neighbour in $B$. Finally, if
$|A\cap\\{u,u^{\prime}\\}|=|B\cap\\{u,u^{\prime}\\}|=1$, then we assume
without loss of generality that $u\in A$ and $u^{\prime}\in B$ and do not
perform any extensions.

Observe that after this first step, we have $|A\setminus V(P\cup
P^{\prime})|\geq|B\setminus V(P\cup P^{\prime})|$, because of the assumption
in the last sentence of Lemma 3.7. We then greedily extend the path $P$ inside
the set $A\setminus A^{\prime}$ until we have $|A\setminus V(P\cup
P^{\prime})|=|B\setminus V(P\cup P^{\prime})|$, which is possible because
$|A^{\prime}|\leq\mu n$ and for $v\in A\setminus A^{\prime}$ we have
$\deg_{H}(v,A)\geq 3\mu n$. Since $|A|\leq|B|+\mu n$, we now have $V(P)\leq\mu
n+1$.

Remove from $A$ and $B$ all vertices from the paths $P$ and $P^{\prime}$
except their endvertices $w$ and $w^{\prime}$, thus obtaining sets $A^{*}$ and
$B^{*}$. Note that $n^{*}:=|A^{*}|=|B^{*}|\leq(\frac{1}{2}+\mu)n$. We apply
Corollary 3.6 to the bipartite graph $H^{*}$ between $A^{*}$ and $B^{*}$ (it
is not difficult to see that the degree conditions are satisfied), in order to
find a Hamiltonian path $P^{\prime\prime}$ in $H^{*}$ connecting $w$ and
$w^{\prime}$. We finally connect $P^{\prime},P^{\prime\prime}$ and
$P^{\prime}$ to form the desired Hamilton $u,u^{\prime}$-path in $H$. ∎

###  3.4. Regularity

Given a graph $G$ and disjoint vertex sets $U,W\subseteq V(G)$ we denote the
number of edges between $U$ and $W$ by $e(U,W)$ and the _density_ of $(U,W)$
by $d(U,W)=e(V,W)/(|U||W|)$. The pair $(U,W)$ is called _$\varepsilon$
-regular_ in $G$ if, for all subsets $X\subseteq U$, $Y\subseteq W$ with
$|X|\geq\varepsilon|U|$ and $|Y|\geq\varepsilon|W|$, we have
$|d(U,W)-d(X,Y)|\leq\varepsilon$. We say that $(U,W)$ is _$(\varepsilon,d)$
-regular_ if it is $\varepsilon$-regular and has density at least $d$. We say
that a vertex $u\in U$ has _typical degree_ in a regular pair $(U,W)$ if
$\deg(u,W)\geq(d(U,W)-\varepsilon)|W|$. It follows directly from the
definition of $\varepsilon$-regularity that if $(U,W)$ is
$\varepsilon$-regular, then

(3.1) all but at most $\varepsilon|U|$ vertices in $U$ have typical degree in
$(U,W)$.

Another straightforward consequence of the definition of
$\varepsilon$-regularity concerns large subpairs of regular pairs: If $(U,W)$
is an $(\varepsilon,d)$-regular pair and $U^{\prime}\subseteq U$,
$W^{\prime}\subseteq W$ are of size $|U^{\prime}|\geq\frac{1}{2}|U|$,
$|W^{\prime}|\geq\frac{1}{2}|W|$, then

(3.2) $(U^{\prime},W^{\prime})$ is a $(2\varepsilon,d/2)$-regular pair.

Szemerédi’s regularity lemma allows us to partition the vertex set of a graph
into clusters of vertices such that most pairs of clusters are regular [38].
We will use the regularity lemma in its degree form and with 2 colours (see
[20]). For a coloured graph $G$, a colour $\chi$ and two disjoint vertex sets
$U$, $W$ of $G$ we write $(U,W)_{\chi}$ for the bipartite subgraph of $G[U,W]$
containing all edges of colour $\chi$.

######  Lemma 3.8 (Regularity lemma).

For each $\varepsilon>0$ and $m_{0}\in\mathbb{N}$ there is
$M=M(\varepsilon,m_{0})$ such that for any $2$-edge colouring of any
$n$-vertex graph $G$, and for each $d>0$ there is a partition
$V_{0},V_{1},\ldots,V_{m}$ of $V(G)$ and a subgraph $G^{\prime}$ of $G$ with
vertex set $V(G^{\prime})\setminus V_{0}$ such that:

  1. ()

$m_{0}\leq m\leq M$,

  2. ()

$|V_{0}|\leq\varepsilon n$ and $|V_{1}|=\ldots=|V_{m}|\leq\lceil\varepsilon
n\rceil$,

  3. ()

$\deg_{G^{\prime}}(v)\geq\deg_{G}(v)-(2d+\varepsilon)n$ for each $v\in
V(G)\setminus V_{0}$,

  4. ()

$G^{\prime}[V_{i}]$ has no edges for $i\in[m]$,

  5. ()

for all pairs $(V_{i},V_{j})$ and each colour $\chi$ the pair
$(V_{i},V_{j})_{\chi}$ is $\varepsilon$-regular in $G^{\prime}$ and has
density either 0 or at least $d$.

Let $G$ be a red and blue edge coloured graph with a partition
$V_{0},\ldots,V_{m}$ obtained from Lemma 3.8 with parameters $\varepsilon$,
$m_{0}$ and $d$. We then also call the family
$\mathcal{V}=\\{V_{1},\dots,V_{m}\\}$ an _$(\varepsilon,d)$ -regular
partition_ of $G$ with _exceptional set_ $V_{0}$. We define the (coloured)
$(\varepsilon,d)$-_reduced multi-graph_ $\mathcal{G}$ corresponding to this
partition to be the multi-graph graph with vertex set $V(\mathcal{G})=[m]$ in
which two vertices $i$ and $j$ are connected by a red (or blue) edge, if
$(V_{i},V_{j})$ is an $\varepsilon$-regular pair of density at least $d$ in
red (blue, respectively). Note that it is possible that some $i$ and $j$ are
connected by both a red and a blue edge.

It is easy to show that $\mathcal{G}$ inherits the minimum degree of $G$. More
precisely, if $G$ has minimum degree $cn$, it follows that

(3.3) $\delta(\mathcal{G})\geq(c-2d-\varepsilon)m.$

Further, for a graph $G$, vertex disjoint sets $V_{1},\ldots,V_{\ell}$ of
$V(G)$ and a graph $\mathcal{H}$ on vertex set $[\ell]$, we say that $G$ is
_$(\varepsilon,d)$ -regular on $\mathcal{H}$_ if $(V_{i},V_{j})$ is
$(\varepsilon,d)$-regular whenever $ij\in E(\mathcal{H})$.

The next lemma allows us to connect clusters by short paths provided their
counterparts in the reduced graph lie in the same component. Though the lemma
as stated here does not explicitly appear in previous work, this technique is
standard, and the lemma is straightforward to prove. Given a family of sets
$\mathcal{V}=\\{V_{1},\ldots,V_{t}\\}$, we say that a set $W$ (or a graph $D$
with $V(D)=W$) is $\delta$-_sparse_ in $\mathcal{V}$ if $|W\cap
V_{i}|\leq\delta|V_{i}|$ for each $i\in[t]$.

######  Lemma 3.9 (Connection lemma).

Let $\varepsilon,d>0$ and let $m,\ell,n\in\mathbb{N}$ such that
$10\varepsilon\leq d\leq\frac{1}{10}$ and $\frac{10m\cdot\ell}{d}\leq n$. Let
$G$ be a graph on $n$ vertices, let $V_{0}\subseteq V(G)$ with
$|V_{0}|\leq\varepsilon n$, let $\mathcal{V}=\\{V_{1},\ldots,V_{m}\\}$ be an
equipartition of $V(G)\setminus V_{0}$, and let $\mathcal{G}$ be a graph on
$[m]$ so that $G$ is $(\varepsilon,d)$-regular on $\mathcal{G}$. Let
$W=(w_{1},\ldots,w_{\ell})$ be a walk of order $\ell$ in $\mathcal{G}$. Let
$X\subseteq V_{w_{1}},Y\subseteq V_{w_{\ell}}$ be subsets of size
$d|V_{1}|/2$. Let $S\subseteq V(G)$ be $(d/4)$-sparse in $\mathcal{V}$. Then
there is an $X,Y$-path $P\subseteq G-S$ of order $\ell$.

Finally, the blow-up lemma allows us to find almost spanning cycles or paths
in certain regular partitions. A pair $(U,W)$ is _$(\varepsilon,d)$ -super-
regular_ if it is $(\varepsilon,d)$-regular and, in addition, for all vertices
$u\in U,w\in W$, we have $\deg(u,W)\geq d|U|$ and $\deg(w,U)\geq d|W|$. The
following version of the blow-up lemma can be found in [2, Lemma 7.1]. Note
that we only require the special case $\Delta(\mathcal{G}^{\prime})\leq 2$
here. We remark that one could replace our use of Lemma 3.10 with a use of the
original blow-up lemma of Komlós, Sárközy and Szemerédi [19] and some
additional technical work.

######  Lemma 3.10 (Blow-up lemma).

For all $\Delta\geq 2$, $\alpha,\zeta,d>0$, $\kappa>1$ there exist
$\varepsilon,\rho>0$ such that for all $M$ the following holds for all
sufficiently large $n$.

Let $\mathcal{G}$ be a graph on $[m]$ with $m\leq M$ and let
$\mathcal{G}^{\prime}$ be a spanning subgraph of $\mathcal{G}$ with
$\Delta(\mathcal{G}^{\prime})\leq 2$. Let $H$, $G$ be graphs whose vertex sets
are partitioned into sets $X_{1},\dots,X_{m}$ and $V_{1},\dots,V_{m}$
respectively, such that $|X_{i}|=|V_{i}|\geq\frac{n}{\kappa m}$ and
$|X_{i}|\leq\kappa|X_{j}|$ for each $i,j\in[m]$. Let
$\widetilde{X}_{i}\subseteq X_{i}$ satisfy
$|\widetilde{X}_{i}|\geq\alpha|X_{i}|$ for each $i\in[m]$, and let
$I_{x}\subseteq V_{i}$ for each $i\in[m]$ and $x\in X_{i}$. Suppose that

  1. (B 0 )

$\Delta(H)\leq\Delta$, all edges of $H$ lie on pairs $X_{i}X_{j}$ with
$ij\in\mathcal{G}$, and for each $i\in[m]$, all edges of $H$ incident with
$\widetilde{X}_{i}\cup N(\widetilde{X}_{i})$ lie on pairs
$X_{j}X_{j^{\prime}}$ with $jj^{\prime}\in\mathcal{G}^{\prime}$,

  2. (B 0 )

$G$ is $(\varepsilon,d)$-regular on $\mathcal{G}$, and for each $ij\in
E(\mathcal{G}^{\prime})$ the pair $(V_{i},V_{j})$ is $(\varepsilon,d)$-super-
regular, and

  3. (B 0 )

for each $i\in[m]$ and $x\in X_{i}$ we have $|I_{x}|\geq\zeta|X_{i}|$ and
there are at most $\rho|X_{i}|$ vertices $x\in X_{i}$ such that $I_{x}\neq
V_{i}$.

Then there is an embedding $\psi\colon V(H)\to V(G)$ with $\psi(x)\in I_{x}$
for each $x\in H$.

Figure 2. The extremal colourings: The configuration given in Definition 4.1()
‣ 4.1 is depicted on the left and the one in Definition 4.1() ‣ 4.1 on the
right.

##  4\. Main lemmas and proof of the main theorem

In this section we prove Theorem 1.1. We first sketch the proof and give the
lemmas we need, and then give a formal proof.

For proving Theorem 1.1, we apply the regularity lemma to $G$ to obtain a
regular partition $\mathcal{V}=\\{V_{1},\dots,V_{m}\\}$ with exceptional set
$V_{0}$ and a corresponding coloured reduced multi-graph $\mathcal{G}$ on
vertex set $[m]$. Note that $\mathcal{G}$ approximately inherits the
(relative) minimum degree conditions as $G$. Our task is now to analyse the
structure of monochromatic components in $\mathcal{G}$.

We begin by introducing the following extremal colourings (see also Figure 2),
which require special treatment. Recall that in a coloured multi-graph there
is at most one red edge and at most one blue edge between any pair of
vertices.

######  Definition 4.1 (Extremal colourings).

Let $G$ be an $m$-vertex (multi-)graph whose edges are coloured with red and
blue. We say that the colouring of $G$ is _$\gamma$ -extremal_ if one of the
following holds (modulo swapping colours).

  1. ()

$G$ has a spanning bipartite red component with bipartition classes
$X_{1},X_{2}$ and such that $\big{|}|X_{1}|-|X_{2}|\big{|}\leq\gamma m$. There
are (exactly) two blue components $B_{1},B_{2}$, both bipartite, with
$V(B_{1})=X_{1}$ and $V(B_{2})=X_{2}$.

  2. ()

The subgraph $G$ has two red and two blue monochromatic components
$R_{1},R_{2},B_{1},B_{2}$ such that $V(G)=\bigcup_{i,j\in[2]}V(R_{i})\cap
V(B_{j})$ and $|V(R_{i})\cap V(B_{j})|\leq(1/4+\gamma)m$ for $1\leq i,j\leq
2$. Moreover, all but at most $\gamma m^{2}$ edges of $G[V(R_{i})\cap
V(B_{j})]$ are blue if $i=j$ and red otherwise.

Now we present our main structural lemma, whose proof we defer to Section 5.
It states that if $\mathcal{G}$ is not close to an extremal colouring, then we
can choose three monochromatic components covering all vertices of
$\mathcal{G}$ which have various good properties that allow us to complete the
cycle partition.

######  Lemma 4.2 (Finding components).

Let $1/m\ll\gamma$. Let $\mathcal{G}$ be a multi-graph on $m$ vertices with
$\delta(\mathcal{G})\geq(2/3+8\gamma)m$, whose edges are coloured in two
colours. Suppose that the colouring of $\mathcal{G}$ is not
$(4\gamma)$-extremal. Then there are distinct monochromatic components
$C_{1},C_{2},C_{3}\subseteq\mathcal{G}$ such that $C:=\bigcup C_{i}$ spans
$\mathcal{G}$ and all of the following hold.

  1. ()

$C$ is $\gamma$-robust Tutte.

  2. ()

One of the following holds:

    1. ()

$|\bigcup_{i\neq j}V(C_{i})\cap V(C_{j})|\geq(1/3+\gamma)m$, or

    2. ()

$C_{1}$ is spanning, $C_{1}$ or $C_{2}$ contains an odd cycle, and
$C_{3}=\emptyset$.

  3. ()

If $C_{1},C_{2},C_{3}$ are each bipartite, then $C_{3}=\emptyset$.

  4. ()

$C$ is connected.

Our next task is to make a case distinction, depending on the structure of
$\mathcal{G}$ and of $G$. For this we need the following definition.

######  Definition 4.3 (Bridges).

Suppose $G$ is a graph whose edges are coloured in red and blue and which has
an $(\varepsilon,d)$-regular partition $\mathcal{V}=\\{V_{1},\ldots,V_{m}\\}$
with corresponding coloured $(\varepsilon,d)$-reduced multi-graph
$\mathcal{G}$. Let $H_{1},H_{2}\subseteq\mathcal{G}$ be monochromatic
connected subgraphs of $\mathcal{G}$ of colour $\chi$ and let $G_{\chi}$ be
the subgraph of $G$ formed by all edges in $E(G)$ of colour $\chi$. We say
that $(H_{1},H_{2})$ _admits bridges_ if there are two distinct vertices
$u,u^{\prime}$ in $G$ and clusters $V_{i}$, $V_{j}$, $V_{i^{\prime}}$,
$V_{j^{\prime}}$ in $\mathcal{V}$ with $i,i^{\prime}\in V(H_{1})$ and
$j,j^{\prime}\in V(H_{2})$ such that

$\displaystyle\deg_{G_{\chi}}(u,V_{i})$ $\displaystyle\geq d|V_{i}|\,,$
$\displaystyle\qquad\deg_{G_{\chi}}(u,V_{j})$ $\displaystyle\geq d|V_{j}|,$
$\displaystyle\deg_{G_{\chi}}(u^{\prime},V_{i^{\prime}})$ $\displaystyle\geq
d|V_{i^{\prime}}|\,\qquad\text{and}$
$\displaystyle\qquad\deg_{G_{\chi}}(u^{\prime},V_{j^{\prime}})$
$\displaystyle\geq d|V_{j^{\prime}}|\,.$

If the colour $\chi$ is blue, then we also talk of _blue bridges_ , if $\chi$
is red we talk of _red bridges_.

Note that for any monochromatic connected $H\subseteq\mathcal{G}$ with at
least one edge, the pair $(H,H)$ admits bridges.

Continuing with our proof strategy, we separate three cases. First,
$\mathcal{G}$ is not close to either extremal colouring. Second, $\mathcal{G}$
is close to an extremal colouring but there is a pair of red (blue) components
of $\mathcal{G}$ which admit red (blue) bridges. Third, $\mathcal{G}$ is close
to an extremal colouring and no such bridges exist. In the last case, the
structure of $G$ is so close to the respective extremal graph that we can find
the desired three-cycle partition without the regularity lemma, as the
following lemma states. We prove this lemma in Section 8.

######  Lemma 4.4 (Extremal cases).

Let ${1}/{n}\ll\varepsilon,1/m\ll d\ll\gamma\ll\beta.$ Suppose $G$ is a graph
on $n$ vertices with minimum degree $\delta(G)\geq(2/3+\beta)n$ whose edges
are coloured with red and blue. Suppose $G$ has a coloured
$(\varepsilon,d)$-reduced multi-graph $\mathcal{G}$ on $m$ vertices. Let the
colouring of $\mathcal{G}$ be $\gamma$-extremal and such that one of the
following is true:

  * •

$\mathcal{G}$ has a colouring as in Definition 4.1() ‣ 4.1 with monochromatic
components $R_{1},B_{1},B_{2}$ and $(B_{1},B_{2})$ does not admit bridges.

  * •

$\mathcal{G}$ has a colouring as in Definition 4.1() ‣ 4.1 with monochromatic
components $R_{1},R_{2},B_{1},B_{2}$ and neither $(R_{1},R_{2})$ nor
$(B_{1},B_{2})$ admits bridges.

Then $G$ has a partition into three monochromatic cycles.

When $\mathcal{G}$ is not close to an extremal colouring, or when it is but
some pair of components admits bridges, we work with the regular partition to
find the desired three-cycle partition. We now describe the proof for the case
that $\mathcal{G}$ is not close to either extremal colouring, and explain
briefly at the end the modification required for the case that $\mathcal{G}$
is close to an extremal colouring but some pair of components admit bridges.
We set $H_{i}:=C_{i}$ for $i=1,2,3$, where the $C_{i}$ are the components
provided by Lemma 4.2.

The first step is to fix a perfect $2$-matching $\mathcal{M}$ of
$\mathcal{G}$. We then move a few vertices from each of the clusters
$V_{1},\dots,V_{m}$ to the exceptional set in order to make the regular pairs
of $G$ corresponding to $\mathcal{M}$ super-regular. We denote the resulting
exceptional set by $V^{\text{\text{Exc}}}$.

Our next step is to find three pairwise disjoint cycles in $G$ which form the
basis of our three-cycle partition. In each $H_{i}$ we will find a cycle
$D_{i}$, such that all the $D_{i}$ together cover the vertices
$V^{\text{\text{Exc}}}$. In addition, the cycles $D_{i}$ will be ‘easy to
extend to the pairs in $H_{i}$’, which we make precise in next definition.

######  Definition 4.5 (Support path embeddings).

Let $G$ be a graph whose edges are coloured in red and blue and which has an
$(\varepsilon,d)$-regular partition $\mathcal{V}=\\{V_{1},\dots,V_{t}\\}$ with
corresponding coloured $(\varepsilon,d)$-reduced multi-graph $\mathcal{G}$.
Let $H\subseteq\mathcal{G}_{\chi}$ be a subgraph of colour $\chi$. We say that
$D\subseteq G_{\chi}$ _supports path embeddings in $H$_, if for each edge
$ij\in E(H)$ there is an edge $f_{ij}=\\{u,v\\}\in D$ with $u\in V_{i}$ and
$v\in V_{j}$ such that $u$ and $v$ have typical degree in the regular pair
$(V_{i},V_{j})_{\chi}$. We also say that the edge $f_{ij}$ _witnesses_ that
$D$ supports path embeddings in $H$ for $ij$.

Our next lemma constructs the desired cycles covering the exceptional
vertices. We prove this lemma in Section 6.

######  Lemma 4.6 (Covering exceptional vertices).

Let ${1}/{n}\ll\varepsilon,\frac{1}{m}\ll\delta\ll d\ll{\gamma}\ll\beta$.
Suppose $G$ is a graph on $n$ vertices of minimum degree
$\deg(G)\geq(2/3+\beta)n$ whose edges are coloured with two colours. Let $G$
have an $(\varepsilon,d)$-regular partition
$\mathcal{V}=\\{V_{1},\ldots,V_{m}\\}$ with exceptional set $V_{0}$ and
corresponding coloured $(\varepsilon,d)$-reduced multi-graph $\mathcal{G}$.
Let $W\subseteq V(G)$ be $\delta$-sparse in $\mathcal{V}$. Let
$H_{1},H_{2},H_{3}$ be subgraphs of $\mathcal{G}$ with the following
properties.

  1. ()

One of the following holds:

    1. ()

$|\bigcup_{i\neq j}V(H_{i})\cap V(H_{j})|\geq{(1/3+\gamma)m}$ or

    2. ()

$H_{1}$ is spanning, $H_{1}$ or $H_{2}$ contains an odd cycle, and
$H_{3}=\emptyset$.

  2. ()

If $H_{1},H_{2},H_{3}$ are each bipartite, then $H_{3}=\emptyset$.

  3. ()

$H_{1}$ and $H_{3}$ are monochromatic components and $H_{2}$ is the union of
two monochromatic components which admit bridges.

  4. ()

If $V(H_{i})\cap V(H_{j})\neq\emptyset$, then $H_{i}$ and $H_{j}$ are of
different colours.

Then there are disjoint monochromatic cycles $D_{1}$, $D_{2}$, $D_{3}$ such
that $D_{i}$ supports paths embeddings in $H_{i}$ for each $i\in[3]$.
Moreover, for $D=D_{1}\cup D_{2}\cup D_{3}$, the set $V(D)$ is
$\sqrt{\delta}$-sparse in $\mathcal{V}$, we have $W\subseteq V(D)$, and
$|V(G)\setminus V(D)|$ is even.

To complete the proof, we aim to extend the cycles $D_{1},D_{2},D_{3}$ to
monochromatic cycles partitioning $V(G)$. To do this, we will replace in each
$D_{i}$ some of the edges $f_{e}$ (as in Definition 4.5) with longer paths
$P_{e}$ of the correct colour which are contained in the regular pair
corresponding to $e\in E(\mathcal{G})$ such that, overall, we cover all
vertices of $G$. Any such path uses the same number $t^{\prime}_{e}$ of
vertices in each of the two clusters, which is the reason why we require in
the conclusion of Lemma 4.6 that $|V(G)\setminus V(D)|$ is even.

But how do we choose the numbers $t^{\prime}_{e}$? For explaining this, we
remark first that our strategy is to embed all the paths $P_{e}$ vertex-
disjointly using only one application of the blow-up lemma (Lemma 3.10) with
$\mathcal{G}^{\prime}=\mathcal{M}$. We need $t^{\prime}_{e}$ to be large for
all edges $e\in\mathcal{M}$ (for satisfying condition (B 0 ) of Lemma 3.10).
More precisely, we let $z=\lfloor\tfrac{n}{4m}\rfloor$ and require for all
edges $e$ that $t^{\prime}_{e}\geq\omega(e)z$ where $\omega(f)=2$ if $e$ is on
an edge of $\mathcal{M}$, $\omega(f)=1$ if $e$ is on a cycle of $\mathcal{M}$,
and $\omega(e)=0$ otherwise. Changing variables by setting

(4.1)
$t_{e}=t^{\prime}_{e}-\omega(e)z=t^{\prime}_{e}-\omega(e)\lfloor\tfrac{n}{4m}\rfloor\,,$

this is equivalent to requiring $t_{e}\geq 0$. Moreover, as we need to cover
all vertices in each cluster $V_{i}\in\mathcal{G}$, we require

(4.2) $\big{|}V_{i}\setminus V(D)\big{|}=\sum_{e\in E(\mathcal{G})\colon i\in
e}t^{\prime}_{e}=\sum_{e\in E(\mathcal{G})\colon i\in
e}(t_{e}+\omega(e)z)=2z+\sum_{e\in E(\mathcal{G})\colon i\in e}t_{e}\,.$

The following lemma guarantees that such non-negative values $t_{e}$ exist.
When we apply this lemma, we shall set $t_{i}=\big{|}V_{i}\setminus
V(D)\big{|}-2z$, hence all these $t_{i}$ will be very similar in size.

######  Lemma 4.7 (Balancing lemma).

Given $m$ and $0<\gamma\leq\frac{1}{2}$, if $t\geq 5m/\gamma$ the following
holds. Let $H$ be a connected graph on $m$ vertices that is $\gamma$-robust
Tutte. Let $(t_{i})_{i\in V(H)}$ be integers such that $\sum_{i}t_{i}$ is even
and such that $t_{i}=\big{(}1\pm\tfrac{1}{5}\gamma\big{)}t$ for each $i\in
V(H)$. Then there exist non-negative integers $(t_{e})_{e\in E(H)}$ such that
for each $i\in V(H)$ we have $\sum_{e\in E(H)\colon i\in e}t_{e}=t_{i}$.

We prove Lemma 4.7 in Section 7. This concludes our proof sketch in the case
that $\mathcal{G}$ is not close to an extremal colouring.

The final case to be considered is that $\mathcal{G}$ is close to an extremal
colouring but two components admit bridges. In this case we let $H_{2}$ be the
union of these two components, and let $H_{1}$, $H_{3}$ be the other two
components (it is possible that $H_{3}=\emptyset$). It turns out that the
above proof sketch also works in this setting.

We are now ready to give the details of the proof of Theorem 1.1.

###### Proof of Theorem 1.1.

We will start by fixing some constants. Given $\beta>0$ we may assume that
$\beta\leq 1/3$. We choose $\gamma,d,\delta>0$, and $m_{0}$ such that

(4.3) $\frac{1}{m_{0}}\ll\delta\ll d\ll\gamma\ll\beta$

are small enough so that we can apply Lemma 4.2 with input
$\frac{1}{m_{0}}\ll\gamma$, Lemma 4.4 with input $\frac{1}{m_{0}}\ll d\ll
4\gamma\ll\beta$ and Lemma 4.6 with input $\frac{1}{m_{0}}\ll\delta\ll
d\ll\beta$. The blow-up lemma (Lemma 3.10) with input

$\Delta=2,\quad\alpha=\tfrac{1}{5},\quad\zeta=d/2,\quad
d/2\quad\text{and}\quad\kappa=2$

provides us with constants $\varepsilon^{\prime}>0$ and $\rho>0$. We choose
$\varepsilon$ such that $0<2\varepsilon\leq\varepsilon^{\prime}$, and

(4.4) $\varepsilon\ll\delta.$

Note that our choices guarantee we can use Lemma 4.4 with input
$\varepsilon,\frac{1}{m_{0}}\ll d\ll 4\gamma\ll\beta$ and Lemma 4.6 with input
$\varepsilon,\frac{1}{m_{0}}\ll\delta\ll d\ll\beta$. The regularity lemma
(Lemma 3.8) provides us with a constant $M$ for input $\varepsilon$ and
$m_{0}$. Finally, we choose $n_{0}$ such that

(4.5) $n_{0}^{-1}\ll M^{-1}\leq m_{0}^{-1}$

is sufficiently small for Lemma 3.10, Lemma 4.4, and Lemma 4.6 (with inputs as
set above, but with $M$ instead of $m_{0}$). Assume that $n\geq n_{0}$. We
further assume that our choice of constants in (4.3), (4.4), and (4.5) is such
that these constants are chosen sufficiently small in terms of each other for
various estimates we will use in the proof, for example for the application of
Lemma 4.7 below.

Given an $n$-vertex graph $G$ with minimum degree
$\delta(G)\geq\big{(}\tfrac{2}{3}+\beta\big{)}n$, whose edges are coloured
with red and blue, let $\mathcal{V}=\\{V_{1},\dots,V_{m}\\}$ be a regular
partition of $G$ with exceptional set $V_{0}$, as provided by Lemma 3.8 for
input $\varepsilon,m_{0},d$. We have $m_{0}\leq m\leq M$. Let $\mathcal{G}$ be
the corresponding coloured $(\varepsilon,d)$-reduced multi-graph of $G$. By
(3.3) and by the choice of $\gamma$ we have
$\delta(\mathcal{G})\geq\big{(}\tfrac{2}{3}+8\gamma\big{)}m$. Hence we can
apply Lemma 4.2 with input $m$ and $\gamma$ to the coloured multi-graph
$\mathcal{G}$, which tells us that $\mathcal{G}$ is $(4\gamma)$-extremal or
there are monochromatic components $C_{1},C_{2},C_{3}\subseteq\mathcal{G}$
such that $C:=\bigcup C_{i}$ spans $\mathcal{G}$ and ()–() of Lemma 4.2 hold.
We distinguish three cases and define subgraphs
$H_{1},H_{2},H_{3}\subseteq\mathcal{G}$ as follows:

  1. ()

$\mathcal{G}$ is not $(4\gamma)$-extremal. In this case we set $H_{i}:=C_{i}$
for each $i=1,2,3$.

  2. ()

$\mathcal{G}$ is $(4\gamma)$-extremal and some pair of components admit
bridges.

    1. (0)

If $\mathcal{G}$ is close to the colouring of Definition 4.1() ‣ 4.1, with one
red component $R_{1}$ and two blue components $B_{1},B_{2}$ which admit
bridges, we set $H_{1}:=R_{1}$, $H_{2}:=B_{1}\cup B_{2}$ and
$H_{3}=\emptyset$.

    2. (0)

If $\mathcal{G}$ is close to the colouring of Definition 4.1() ‣ 4.1, with one
blue component $B_{1}$ and two red components $R_{1},R_{2}$ which admit
bridges, we set $H_{1}:=B_{1}$, $H_{2}:=R_{1}\cup R_{2}$ and
$H_{3}=\emptyset$.

    3. (0)

If $\mathcal{G}$ is close to the colouring of Definition 4.1() ‣ 4.1, with two
red components $R_{1},R_{2}$ and two blue components $B_{1},B_{2}$ such that
$(B_{1},B_{2})$ admits bridges, we set $H_{1}:=R_{1}$, $H_{2}:=B_{1}\cup
B_{2}$ and $H_{3}=R_{2}$.

    4. (0)

If $\mathcal{G}$ is close to the colouring of Definition 4.1() ‣ 4.1, with two
red components $R_{1},R_{2}$ and two blue components $B_{1},B_{2}$ such that
$(R_{1},R_{2})$ admits bridges, we set $H_{1}:=B_{1}$, $H_{2}:=R_{1}\cup
R_{2}$ and $H_{3}=B_{2}$.

  3. ()

None of the above cases apply.

In case () ‣ 4, by Lemma 4.4 there exist three monochromatic cycles which
partition the vertices of $G$, as desired. We may therefore assume one of the
other two cases holds. Let $H$ be the uncoloured spanning subgraph of
$\mathcal{G}$ whose edges are all pairs lying in at least one of $H_{1}$,
$H_{2}$ and $H_{3}$. We claim that (in either of the two cases) all of the
following hold.

  1. (H: )

$H$ is $\gamma$-robust Tutte.

  2. (H: )

One of the following holds

    1. ()

$|\bigcup_{i\neq j}V(H_{i})\cap V(H_{j})|\geq(1/3+\gamma)m$ or

    2. ()

$H_{1}$ is spanning, $H_{1}$ or $H_{2}$ contains an odd cycle, and
$H_{3}=\emptyset$.

  3. (H: )

If $H_{1},H_{2},H_{3}$ are each bipartite, then $H_{3}=\emptyset$.

  4. (H: )

$H_{1}$ and $H_{3}$ are monochromatic components of $\mathcal{G}$, while
$H_{2}$ is the union of two monochromatic components of $\mathcal{G}$ of the
same colour which admit bridges.

  5. (H: )

If $V(H_{i})\cap V(H_{j})\neq\emptyset$, then $H_{i}$ and $H_{j}$ are of
different colours.

  6. (H: )

$H$ is connected.

These statements hold in case () ‣ 4 by Lemma 4.2, with each $H_{i}$ being a
distinct monochromatic component of $\mathcal{G}$ (and so $H_{2}=C_{2}\cup
C_{2}$, and as observed after Definition 4.3, $(C_{2},C_{2})$ admits bridges
trivially). In case () ‣ 4, $H_{1}$ and $H_{3}$ are distinct monochromatic
components of $\mathcal{G}$ and $H_{2}$ is by construction the union of two
monochromatic components of $\mathcal{G}$ of the same colour which admit
bridges, hence we get (H: ). Further, there are no other other monochromatic
components in $\mathcal{G}$ by Definition 4.1, hence we get (H: ) and
$H=\mathcal{G}$ has minimum degree $\delta(H)\geq 2m/3$. It follows that no
stable set has more than $m/3$ vertices and every stable set has a
neighbourhood of size at least $2m/3$, giving (H: ). It is easy to verify that
also (H: )(H: )() and (H: ) hold. From this point on, we do not need to
distinguish cases () ‣ 4 and () ‣ 4; the above list of properties is all we
need.

By (H: ) and Theorem 3.2, there is an (uncoloured) perfect $2$-matching
$\mathcal{M}$ in $H$. Let $V^{\text{\text{Exc}}}$ consist of $V_{0}$ together
with, for each $i\in V(\mathcal{G})$, all vertices $v\in V_{i}$ such that $v$
does not have typical degree in any pair $(V_{i},V_{j})$ with $ij\in
E(\mathcal{M})$ in any colour such that $\mathcal{G}$ has an edge $ij$ of this
colour. By (3.1), there are at most $4\varepsilon|V_{i}|$ such vertices in
each $V_{i}$, so that $V^{\text{\text{Exc}}}$ is $\delta$-sparse in
$\mathcal{V}=\\{V_{1},\dots,V_{m}\\}$.

We apply Lemma 4.6 to $G$ with the partition $\mathcal{V}$ with reduced multi-
graph $\mathcal{G}$, and with $W=V^{\text{\text{Exc}}}$. The conditions of the
lemma are satisfied by (H: ), (H: ) and (H: ). We obtain pairwise vertex
disjoint monochromatic cycles $D_{1},D_{2},D_{3}$ in $G$, such that for each
$i$ the colour of $D_{i}$ is the same as the colour of $H_{i}$, and $D_{i}$
supports path embeddings in $H_{i}$. Furthermore, for $D:=D_{1}\cup D_{2}\cup
D_{3}$ the set $V(D)$ is $\sqrt{\delta}$-sparse in $\mathcal{V}$, we have
$V^{\text{\text{Exc}}}\subseteq V(D)$, and

(4.6) $\big{|}V(G)\setminus V(D)\big{|}\quad\text{is even}\,.$

For each $e\in H$, choose some $p(e)\in\\{1,2,3\\}$ such that $e\in
E(H_{p(e)})$, and let $f_{e}$ be the edge of $D_{p(e)}$ witnessing that
$D_{p(e)}$ supports path embeddings for $e$.

It remains to extend the cycles $D_{1}$, $D_{2}$, $D_{3}$ to cycles covering
all of $G$, for which we shall use the blow-up lemma. This lemma requires a
reduced graph without multi-edges, and hence we fix a (coloured) subgraph
$\mathcal{G}^{*}$ of $\mathcal{G}$ by deleting for each multi-edge in
$\mathcal{G}$ one of the two parallel edges, with the constraint that if $e\in
H$ then the edge of the same colour as $f_{e}$ is kept. Observe that this does
not create problems with connectivity: Since $D_{i}$ supports path-embeddings
in $H_{i}$ and we shall use this to extend $D_{i}$ by merely replacing some of
its edges by longer paths, the resulting graph will still be a cycle. Hence it
only remains to check that we can do these extensions so that all vertices of
$G$ get covered. For this we shall use the blow-up lemma with reduced graph
$\mathcal{G}^{*}$ and with $\mathcal{G}^{\prime}=\mathcal{M}$.

Let us next check that the vertices not covered by $D_{1}$, $D_{2}$, and
$D_{3}$ indeed form a regular partition which is super-regular on the pairs
corresponding to $\mathcal{M}$, so that we can apply the blow-up lemma. For
each $i\in[m]$ let $V_{i}^{*}=V_{i}\setminus V(D)$ and let $G^{*}$ be a graph
on vertex set $V(G)\setminus V(D)$ that contains for each
$ij\in\mathcal{G}^{*}$ of some colour $\chi$ the edges of $G$ in the regular
pair $(V_{i},V_{j})$ of colour $\chi$ that have one endpoint in $V^{*}_{i}$
and the other in $V^{*}_{j}$. Consider the partition
$\mathcal{V}^{*}=\\{V^{*}_{1},\dots,V^{*}_{m}\\}$. Observe that since
$V^{\text{\text{Exc}}}\subseteq V(D)$, for each $ij\in\mathcal{M}$ and for any
vertex in $v\in V^{*}_{i}$ we have

$\deg_{G^{*}}(v,V^{*}_{j})\geq(d-\varepsilon)|V_{j}|-\sqrt{\delta}|V_{j}|>d|V^{*}_{j}|/2.$

Moreover, by (3.2) for each edge $ij\in E(\mathcal{G}^{*})$ the pair
$\big{(}V^{*}_{i},V^{*}_{j}\big{)}$ in $G^{*}$ is
$(2\varepsilon,d/2)$-regular. In other words, $G^{*}$ with the partition
$\mathcal{V}^{*}$ is $(2\varepsilon,d/2)$-regular on $\mathcal{G}^{*}$ and
$\big{(}V^{*}_{i},V^{*}_{j}\big{)}$ is $(2\varepsilon,d/2)$-super-regular for
each $ij\in\mathcal{M}$. Hence $G^{*}$, with the partition $\mathcal{V}^{*}$
and the graph $\mathcal{G}^{*}$ with subgraph
$\mathcal{G}^{\prime}=\mathcal{M}$, satisfies Lemma 3.10(B 0 ).

As explained before, for edges $e\in H$ we shall replace the edge $f_{e}$
(which is part of some $D_{i}$) by a path in the same colour of length
$t^{\prime}_{e}$. Let us now choose the values $t^{\prime}_{e}$ with the help
of Lemma 4.7. To this end, set $z:=\lfloor\tfrac{n}{4m}\rfloor$ and for each
$i\in[m]$, set $t_{i}:=\big{|}V^{*}_{i}\big{|}-2z$. Observe that
$\sum_{i\in[m]}t_{i}=|V(G^{*})|-2mz$, which is even by (4.6). Moreover, since
$(1-\varepsilon)n/m\leq|V_{i}|\leq n/m$ holds by Lemma 3.8() ‣ 3.8, and since
$V(D)$ is $\sqrt{\delta}$-sparse in $\mathcal{V}$, we have
$(1-\varepsilon)n/m-\sqrt{\delta}n/m\leq|V^{*}_{i}|\leq n/m$ and hence
$t_{i}=(1\pm 3\sqrt{\delta})n/(2m)=(1\pm\frac{1}{5}\gamma)n/(2m)$ for each
$i\in V(H)$. Since $H$ is $\gamma$-robust Tutte by (H: ) and connected by (H:
), we can apply Lemma 4.7 to obtain non-negative integers $(t_{e})_{e\in
E(H)}$ such that $\sum_{e\in E(H):i\in e}t_{e}=t_{i}$ holds for each $i$.
Setting $t^{\prime}_{e}:=t_{e}+\omega(e)z$, where $\omega(f)=2$ if $e$ is on
an edge of $\mathcal{M}$, $\omega(f)=1$ if $e$ is on a cycle of $\mathcal{M}$,
and $\omega(e)=0$ otherwise, we obtain

(4.7) $\sum_{e\in E(H)\colon i\in
e}t^{\prime}_{e}=\big{|}V^{*}_{i}\big{|}\quad\text{and}\quad
t^{\prime}_{\hat{e}}\geq z\geq\frac{n}{5m}$

for each $i\in[m]$ and each $\hat{e}\in\mathcal{M}$.

We now construct a graph $F$ containing the paths that we shall embed with the
help of the blow-up lemma, and define a partition $V(F)=X_{1}\cup\dots\cup
X_{m}$ as follows. For each $e=ij\in H$ with $t^{\prime}_{e}>0$, we add a path
$P_{e}$ with $2t^{\prime}_{e}$ vertices to $F$, whose vertices we put
alternately to $X_{i}$ and $X_{j}$. Thus all edges of $F$ lie on pairs
$(X_{i},X_{j})$ such that $ij\in H$. For each $i\in V(H)$, we let
$\widetilde{X}_{i}\subseteq X_{i}$ be the vertices lying on paths between
$X_{i}$ and some $X_{j}$ such that $ij\in\mathcal{M}$. By (4.7) we have
$|\widetilde{X}_{i}|\geq\frac{n}{5m}\geq|V^{*}_{i}|/5$ and
$|X_{i}|=|V^{*}_{i}|$ for each $i\in[m]$. Hence $F$ and the partition
$X_{1}\cup\dots\cup X_{m}$ satisfy Lemma 3.10(B 0 ).

Finally, we set up image restrictions $I_{x}$ for $x\in V(F)$ as follows, to
guarantee that when we embed the paths in $F$ they connect appropriately to
the corresponding $D_{i}$. If $x\in X_{i}$ has degree $2$ in $F$, we set
$I_{x}=V^{*}_{i}$. Otherwise, $x$ is an end-vertex of a path whose vertices
are in $X_{i}\cup X_{j}$ and by definition, the edge $e=ij$ lies in
$H_{p(e)}$. In this case let $z$ be the end-vertex of $f_{e}\in E(D_{p(e)})$
that is in $X_{j}$ and let $I_{x}$ be the $G^{*}$-neighbours $z^{\prime}$ of
$z$ in $X^{*}_{i}$. Observe that by definition of $G^{*}$ each such edge
$zz^{\prime}$ has the same colour as $f_{e}$. Since $D_{i}$ supports path
embeddings in $H_{i}$, the vertex $z$ is typical in $(V_{i},V_{j})$ and hence
has at least
$(d-\varepsilon)|V_{i}|-\sqrt{\delta}|V_{i}|\geq\frac{1}{2}d|V^{*}_{i}|$
neighbours in $V^{*}_{i}$. Further, since for each edge $e$ of
$\mathcal{G}^{*}$ we choose a unique $f_{e}\in E(D)$, for each $i\in[m]$ there
are at most $m-1\leq\rho|X_{i}|$ vertices $x\in X_{i}$ with $I_{x}\neq
V^{*}_{i}$. Hence the $I_{x}$ satisfy Lemma 3.10(B 0 ).

Thus, applying Lemma 3.10, we find an embedding $\phi$ of $F$ into $G^{*}$
such that for each $x\in V(F)$ we have $x\in I_{x}$. We combine the embedding
of $F$ with the cycles $D_{1},D_{2},D_{3}$, by replacing for each $e\in H$
such that $t^{\prime}_{e}>0$ the edge $f_{e}=uv$ on the cycle $D_{p(e)}$ with
a path as follows. Assume without loss of generality that $u\in V_{i}$ and
$v\in V_{j}$ and that the first vertex $w$ of $\phi(P_{e})$ is in $V_{j}$ and
the last vertex $w^{\prime}$ of $\phi(P_{e})$ is in $V_{i}$. Then we replace
$f_{e}$ by the path $u,\phi(P_{e}),v$ to obtain a longer monochromatic cycle.
This is possible since $\phi(P_{e})$ has the same colour $\chi$ as $f_{e}$ by
the definition of $G^{*}$, and since, by the definition of the sets $I_{x}$,
also $uw$ and $w^{\prime}v$ have colour $\chi$. We thus obtain three
monochromatic cycles $D^{\prime}_{1},D^{\prime}_{2},D^{\prime}_{3}$, whose
vertices partition $V(G)$. ∎

##  5\. Finding components: The proof of Lemma 4.2

This section is dedicated to the proof of Lemma 4.2. Given $\gamma>0$, let
$G:=\mathcal{G}$ be a red and blue edge coloured graph on $n:=m$ vertices and
of minimum degree at least $(2/3+8\gamma)n$. Suppose that the colouring of $G$
is not $(4\gamma)$-extremal. Our goal is to find monochromatic components
$C_{1},C_{2},C_{3}\subseteq G$ whose union spans $G$ and satisfies ()–() of
Lemma 4.2.

We start by showing that $G$ is spanned by two monochromatic components.

######  Claim 5.1.

There are monochromatic components $C_{1},C_{2}$ that together span $G$.

###### Proof.

Let $\mathcal{C}$ be the set of monochromatic components of $G$. Let
$v_{1},\ldots,v_{q}$ be a maximal number of vertices such that for distinct
$i,j\in[q]$, vertices $v_{i}$ and $v_{j}$ are both in distinct red and in
distinct blue components. Then

$\frac{2}{3}nq\leq\sum_{i\in[q]}\deg(v_{i})=\sum_{i\in[q]}d_{\text{red}}(v_{i})+\sum_{i\in[q]}d_{\text{blue}}(v_{i})\leq
2(n-q),$

and therefore, $q\leq 2$. Now consider the bipartite graph $H$ whose partition
classes are the red and blue components respectively and which has an edge
$CC^{\prime}$ whenever and $V(C)\cap V(C^{\prime})\neq\emptyset$. Observe that
the size of any matching in $H$ is at most $q\leq 2$. So by Kőnig’s theorem,
the edges of $H$ are covered by two vertices. These vertices are monochromatic
components spanning $G$. ∎

We fix monochromatic components $C_{1}$ and $C_{2}$ that together span the
vertices of $G$ and distinguish three cases:

Case 1:

One of $C_{1}$ and $C_{2}$ is spanning,

Case 2:

$C_{1}$ and $C_{2}$ have distinct colours,

Case 3:

$C_{1}$ and $C_{2}$ have the same colour.

We introduce the notion of contracting sets, which will be convenient when
arguing about part () of Lemma 4.2.

######  Definition 5.2.

For a spanning subgraph $H\subseteq G$, we call a stable set $S\subseteq V(G)$
_contracting_ in $H$, if $|N_{H}(S)|<|S|+\gamma n$.

Note that if $S$ is contracting in $H$, then $2|N_{H}(S)|-\gamma
n<|S|+|N_{H}(S)|\leq n$ and, therefore,

(5.1) $|N_{H}(S)|<(1/2+\gamma/2)n.$

###  5.1. Case 1: One of $C_{1}$ and $C_{2}$ is spanning

We assume that $R:=C_{1}$ is spanning and red. We will show that either there
exist one or two blue components which together with $R$ satisfy the
conditions of Lemma 4.2, or the colouring is $(4\gamma)$-extremal as in
Definition 4.1() ‣ 4.1 in contradiction to our assumption.

Let us begin with the following observation. For a collection of blue
components $\\{B_{i},i\in I\\}$, consider a subgraph $H=R\cup\bigcup_{i\in
I}B_{i}\subseteq G$, and assume that some stable set $S$ is contracting in
$H$. If $B$ is a blue component with $v\in S\cap V(B)$, then

(5.2) $|S|+\gamma n>|N_{H}(S)|\geq\deg_{H}(v)\geq(2/3+8\gamma)n-|V(B)|.$

Furthermore, we must have that $B\neq B_{i}$, $i\in I$, since otherwise
$|N_{H}(S)|\geq\deg_{H}(v)=\deg_{G}(v)\geq(2/3+8\gamma)n$, in contradiction to
(5.1). Hence, for any $B_{i}$, $i\in I$, we have

(5.3) $S\cap V(B_{i})=\emptyset.$

The next claim summarizes a few observations on contracting sets.

######  Claim 5.3.

Let $H=R\cup\bigcup_{i\in I}C_{i}$ for blue components $C_{i}$, $i\in I$.
Suppose $S$ is a contracting set in $H$, and let $B_{1},\ldots,B_{t}$ be the
blue components that have non-empty intersection with $S$. Then

  1. ()

$t\leq 2$ and $\big{|}V(\bigcup_{j\in[t]}B_{j})\big{|}\geq(1/3+3\gamma)n$.

In addition, we have the following:

  1. ()

If $S$ intersects with a bipartite blue component, then $t=1$.

  2. ()

If $t=2$, then $V(G)\setminus N_{H}(S)\subseteq V(\bigcup_{j\in[t]}B_{j})$ and
$V(G)\setminus V(\bigcup_{j\in[t]}B_{j})\subseteq N_{H}(S)$.

Before we prove Claim 5.3 let us note that, by (5.3), the sets $V(B_{j})$,
$j\in[t]$, are distinct from the sets $V(C_{i})$, $i\in I$.

###### Proof.

Set $W=V(G)\setminus(N_{H}(S)\cup S)$ and note that

(5.4) $H$ has no edges in $S$ and no edges between $S$ and $W$.

For each $j\in[t]$, fix a vertex $v_{j}\in V(B_{j})\cap S$ and observe that

(5.5) $|(S\cup W)\cap V(B_{j})|\geq\deg_{B_{j}}(v_{j},S\cup
W)\overset{\eqref{equ:C-no-edges-in-S}}{\geq}(2/3+8\gamma)n-|N_{H}(S)|.$

To prove $t\leq 2$, let us assume that $t\geq 3$ and obtain a contradiction.
Since $B_{1},B_{2},B_{3}$ are vertex disjoint, we have By (5.4) we have

$\displaystyle|S\cup W|$ $\displaystyle\geq\sum_{i\in[3]}|(S\cup W)\cap
V(B_{j})|\overset{\eqref{equ:ScupWcapB-
geq-2/3-NS}}{\geq}(2+24\gamma)n-3|N_{H}(S)|.$

This, together with the fact that $V(G)=S\cup N_{H}(S)\cup W$, contradicts
(5.1):

$\displaystyle 3|N_{H}(S)|+|S\cup W|$
$\displaystyle\overset{}{\geq}(6/3+24\gamma)n$ $\displaystyle\Leftrightarrow$
$\displaystyle 2|N_{H}(S)|$ $\displaystyle\geq(3/3+24\gamma)n$
$\displaystyle\Leftrightarrow$ $\displaystyle|N_{H}(S)|$
$\displaystyle\geq(1/2+12\gamma)n.$

Hence $t\leq 2$.

In preparation for proving parts () ‣ 5.3 and () ‣ 5.3, we show the following:

(5.6) If $t=2$, then $|S|\geq(1/3+15\gamma)n$.

Indeed, assuming that $t=2$, we have

$\displaystyle|W|$ $\displaystyle\geq|W\cap V(B_{1})|+|W\cap V(B_{2})|$
$\displaystyle\geq|(W\cup S)\cap V(B_{1})|-|S\cap V(B_{1})|+|(W\cup S)\cap
V(B_{2})|-|S\cap V(B_{2})|$
$\displaystyle\stackrel{{\scriptstyle\eqref{equ:ScupWcapB-
geq-2/3-NS}}}{{\geq}}2(2/3+8\gamma)n-2|N_{H}(S)|-|S\cap(V(B_{1})\cup
V(B_{2}))|$ $\displaystyle\geq(4/3+16\gamma)n-2|N_{H}(S)|-|S|.$

This, together with $V(G)=W\cup S\cup N_{H}(S)$, gives $|S|+\gamma
n>|N_{H}(S)|\geq(1/3+16\gamma)n$, which implies (5.6).

To obtain part () ‣ 5.3 suppose that $t=2$. It follows from
$\delta(G)\geq(2/3+8\gamma)n$ and (5.6) that any vertex in
$V(G)\setminus(N_{H}(S)\cup S)$ has an edge to $S$. All such edges are not in
$H$ by (5.4), so they are blue and in $B_{1}$ or $B_{2}$. Hence $V(G)\setminus
N_{H}(S)\subseteq V(\bigcup_{j\in[t]}B_{j})$ and $V(G)\setminus
V(\bigcup_{j\in[t]}B_{j})\subseteq N_{H}(S)$, as desired.

To show part () ‣ 5.3, let us assume that $t=2$ and, without loss of
generality, $B_{1}$ is bipartite. Consider any vertex $v_{1}\in S\cap
V(B_{1})$. By (5.6) and since $S$ is stable in $H$, the vertex $v_{1}$ has a
blue neighbour $v_{2}\in S$. Clearly $v_{1},v_{2}$ belong to distinct
bipartition classes of $B_{1}$ and their neighbourhoods in $B_{1}$ are
disjoint. Hence

$|(S\cup W)\cap V(B_{1})|\geq\sum_{j=1}^{2}\deg_{B_{1}}(v_{j},S\cup
W)|\overset{\eqref{equ:ScupWcapB-
geq-2/3-NS}}{\geq}2(2/3+8\gamma)n-2|N_{H}(S)|.$

We combine the last inequality with (5.5) and obtain

$\displaystyle|S\cup W|$ $\displaystyle\geq\sum_{i\in[2]}|(S\cup W)\cap
V(B_{j})|\geq(2+24\gamma)n-3|N_{H}(S)|.$

Using the fact that $V(G)=S\cup N_{H}(S)\cup W$, we get again

$\displaystyle 3|N_{H}(S)|+|S\cup
W|\overset{}{\geq}({6}/{3}+24\gamma)n\overset{\eqref{equ:ScupWcapB-
geq-2/3-NS}}{\Rightarrow}|N_{H}(S)|\geq({1}/{2}+12\gamma)n,$

which is a contradiction to (5.1). This proves part () ‣ 5.3.

Finally, to complete the proof of part (a), we must show that
$|V(\bigcup_{j\in[t]}B_{j})|\geq(1/3+3\gamma)n$. If $|S|\geq(1/3+3\gamma)n$,
this follows from $S\subseteq V(\bigcup_{j\in[t]}B_{j})$. Otherwise, we have
$|S|<(1/3+3\gamma)n$, and hence $t=1$ by (5.6). Then

$(1/3+4\gamma)n>|S|+\gamma
n\overset{\eqref{equ:S>2/3-VB}}{>}(2/3+8\gamma)n-|V(B_{1})|$

from which we obtain $|V(B_{1})|>(1/3+4\gamma n)$ as desired. ∎

Now we show that we can select two blue components which together with $R$
satisfy the conditions of Lemma 4.2.

######  Remark 5.4.

Note that since we always select $R$ and $R$ is spanning, part () of Lemma 4.2
holds trivially.

######  Claim 5.5.

If there are two blue components $B_{1},B_{2}$ with
$|V(B_{1})|,|V(B_{2})|\geq(1/3+3\gamma)n$, then Lemma 4.2 is true.

###### Proof.

Consider blue components $B_{1},B_{2}$ with
$|V(B_{1})|,|V(B_{2})|\geq(1/3+3\gamma)n$. First, suppose that one of
$R,B_{1},B_{2}$ contains an odd cycle. Let $H_{2}=R\cup B_{1}\cup B_{2}$. We
will show that $H_{2}$ satisfies the conditions of Lemma 4.2. If $H_{2}$ has a
contracting set, then by Claim 5.3 there are (up to) two more blue components
which together contain at least $(1/3+3\gamma)n$ vertices. But this
contradicts $|V(B_{1})|,|V(B_{2})|\geq(1/3+3\gamma)n.$ Hence $H_{2}$ satisfies
Lemma 4.2(). Moreover, $H_{2}$ also trivially satisfies ()()(). Since one of
$R,B_{1},B_{2}$ contains an odd cycle, $H_{2}$ satisfies Lemma 4.2(), and we
are done.

Hence we can assume that $R,B_{1},B_{2}$ are each bipartite. Denote the
bipartite partition classes of $R$ by $X$ and $Y$, where $|X|\geq|Y|$. We
claim that either $V(B_{1})=X$ and $V(B_{2})=Y$ or vice versa. Observe that
$\delta(G_{\text{blue}}[X])\geq(2/3+8\gamma)n-|Y|\geq(1/6+8\gamma)n$. Since
$B_{1}$ and $B_{2}$ have each order at least $(1/3+3\gamma)n$ and $|Y|\leq
n/2$, there must be a vertex $x\in X$ which is also in $B_{1}$ or $B_{2}$, say
in $B_{1}$.

Let us show that $X$ is contained in $V(B_{1})$. Since
$\delta(G_{\text{blue}}[X])\geq(1/6+8\gamma)n$, the component $B_{1}$ has an
edge in $X$. It follows, using
$\delta(G_{\text{blue}}[X])\geq(2/3+8\gamma)n-|Y|$ and the bipartiteness of
$B_{1}$, that $B_{1}$ has at least $(4/3+16\gamma)n-2|Y|$ vertices in $X$.
Take any vertex $x^{\prime}\in X$. Since

$(4/3+16\gamma)n-2|Y|+\delta(G_{\text{blue}}[X])\geq(2+24\gamma)n-3|Y|>|X|,$

$x^{\prime}$ must have a blue neighbour in $V(B_{1})$. This proves $X\subseteq
V(B_{1})$.

Since $X$ is contained in $V(B_{1})$, it follows that $V(B_{2})$ is contained
in $Y$. In fact, we have $V(B_{2})=Y$. To see this, recall that
$|V(B_{2})|\geq(1/3+3\gamma)n$. As $G$ has minimum degree $(2/3+8\gamma)n$ and
$Y$ contains no red edges, every vertex $y\in Y$ must have a blue neighbour in
$V(B_{2})$, and therefore also belongs to $B_{2}$. Hence $Y\subseteq
V(B_{2})$. So in fact, we have $V(B_{1})=X$ and $V(B_{2})=Y$.

Set $H_{1}=R\cup B_{1}$. If $H_{1}$ has no contracting sets, then it satisfies
the conditions of Lemma 4.2 and we are done. So suppose that $S$ is a
contracting set in $H_{1}$. Since vertices in $X$ have degree at least
$(2/3+8\gamma)n$ in $H_{1}$, the set $S$ must be contained in $Y=V(B_{2})$. In
the following, we distinguish two cases depending on the size of $S$.

Let us begin with the case, where $|S|>(1/3-8\gamma)n$. Then every vertex of
$G$ has a neighbour in $S$. In particular, every vertex in $X$ has a red
neighbour in $S$, hence $X\subseteq N_{H_{1}}(X)$. So $|Y|+\gamma
n\geq|S|+\gamma n\geq|N_{H_{1}}(S)|\geq|X|$, and hence
$|X|\geq|Y|\geq|X|-\gamma n$. It follows that the colouring is
$\gamma$-extremal as in Definition 4.1() ‣ 4.1, which contradicts our initial
assumption.

Now suppose that $|S|\leq(1/3-8\gamma)n$. We show that this results a
contradiction. Suppose first that $G[S]$ contains an edge $vw$. Such an edge
must be blue and in $B_{2}$. Using the bipartiteness of $B_{2}$, we obtain
that

$\displaystyle|V(B_{2})|$
$\displaystyle\overset{}{\geq}\deg_{G}(v,V(G)\setminus
X)+\deg_{G}(w,V(G)\setminus X)$
$\displaystyle\overset{}{\geq}(4/3+16\gamma)n-2|N_{H_{1}}(S)|$
$\displaystyle\geq(4/3+14\gamma)n-2|S|$ $\displaystyle\geq(2/3+30\gamma)n,$

where we used that $S$ is contracting in the penultimate line. Now suppose
that $G[S]$ contains no edge. It follows, for any $v\in S$, that

$\displaystyle|V(B_{2})|$
$\displaystyle\overset{}{\geq}|S|+\deg_{G}(v,V(G)\setminus N_{H_{1}}(S))$
$\displaystyle\geq|S|+(2/3+8\gamma)n-|N_{H_{1}}(S)|$
$\displaystyle\geq(2/3+7\gamma)n.$

In both cases, we have $|V(B_{2})|\geq 2n/3$, which contradicts
$|V(B_{1})|\geq(1/3+3\gamma)n$. ∎

Denote the three blue components of largest order by $B_{1},B_{2},B_{3}$,
where $|B_{1}|\geq|B_{2}|\geq|B_{3}|$. Let $H_{1}=R\cup R_{1}$ and, for
$i\in\\{2,3\\}$, let $H_{i}=R\cup B_{1}\cup B_{i}=H_{1}\cup B_{i}$.

######  Claim 5.6.

Let $i\in\\{2,3\\}$. If $H_{i}$ has no contracting set, then Lemma 4.2 holds.

###### Proof.

Suppose that $H_{i}$ has no contracting set for some $i\in\\{2,3\\}$.

First we deal with the case, when $|V(B_{1})\cup V(B_{2})|<(1/3+\gamma)n$.
Here, we shall show that $H_{1}$ satisfies the conditions of Lemma 4.2. To
begin, observe that all blue components distinct from $B_{1}$ have order at
most $(1/6+\gamma/2)n$. It follows that $H_{1}$ has minimum degree at least
$\delta(G)-(1/6+\gamma/2)n>(1/2+7\gamma)n$ and, therefore, contains no
contracting sets (see (5.1)). So $H_{1}$ satisfies Lemma 4.2(). If $R$
contains an odd cycle, then $H_{1}$ also satisfies Lemma 4.2()()() and (), and
we are done. Thus we may assume that $R$ is bipartite. Let $V(R)=X\cup Y$ be a
bipartition of $R$, where $|X|\geq|Y|$. Note that
$\delta_{\text{blue}}(G[X])\geq(2/3+8\gamma)n-|Y|\geq(1/6+8\gamma)n$. Since
$B_{1}$ is the only blue component of order (possibly) more than
$(1/6+\gamma)n$, it follows that $X\subseteq V(B_{1})$. Thus
$|V(B_{1})|\geq|X|\geq n/2$ in contradiction to the assumption of
$|V(B_{1})\cup V(B_{2})|<(1/3+\gamma)n$.

Hence we may assume that $|V(B_{1})\cup V(B_{2})|\geq(1/3+\gamma)n$. This
means that $H_{2}$ satisfies Lemma 4.2()()(). If $|V(B_{1})\cup
V(B_{3})|\geq(1/3+\gamma)n$, then also $H_{3}$ satisfies Lemma 4.2()()().
Otherwise, $|V(B_{1})\cup V(B_{3})|<(1/3+\gamma)n$ and all blue components
distinct from $B_{1}$ and $B_{2}$ have order at most $(1/6+\gamma/2)n$. It
follows that $H_{2}$ has minimum degree at least
$\delta(G)-(1/6+\gamma/2)n>(1/2+7\gamma)n$ and, therefore, contains no
contracting sets (see (5.1)). So, we may assume $i=2$. In either case, $H_{i}$
satisfies Lemma 4.2()()().

If one of $R$, $B_{1}$ and $B_{i}$ is not bipartite, then $H_{i}$ satisfies
Lemma 4.2(), and Lemma 4.2 holds. Hence assume that $R$, $B_{1}$ and $B_{i}$
are each bipartite. As before, let $V(R)=X\cup Y$ be a bipartition of $R$ with
$|X|\geq|Y|$.

We need to distinguish between two sub-cases: either $B_{1}\cap
X\neq\emptyset$ or $V(B_{1})\subseteq Y$. Suppose first that $B_{1}$ has at
least one vertex in $X$. We will show that $X\subseteq V(B_{1})$. To this end,
note that $\delta_{\text{blue}}(G[X])\geq\delta(G)-|Y|\geq(1/6+8\gamma)n$.
Since $B_{1}$ is bipartite and has at least one edge in $X$, it has at least
$2\delta_{\text{blue}}(G[X])\geq(1/3+16\gamma)n$ vertices in $X$. Using that
$\delta(G)\geq(2/3+8\gamma)n$, we obtain that any vertex $x$ in $X$ has a
neighbour $x^{\prime}$ in $V(B_{1})\cap X$. Since $R$ is bipartite,
$xx^{\prime}$ must be blue, hence $x\in V(B_{1})$ and $X\subseteq V(B_{1})$.

The situation, where $|X|<(1/2+2\gamma)n$ is easily resolved. Indeed, if
$|X|<(1/2+\gamma)n$, then $|V(B_{i})|\geq 2\delta(G_{\text{blue}}[Y])\geq
2((2/3+8\gamma)n-|X|)\geq(1/3+12\gamma)n$, where we used the bipartiteness of
$B_{i}$. Since $|V(B_{1})|\geq|V(B_{i})|$, we are done by Claim 5.5.

Thus we can assume that $|X|\geq(1/2+2\gamma)n$. Now it is not hard to see
that $H_{1}=R\cup B_{1}$ satisfies the conditions of Lemma 4.2. Note that
()()() and () are trivially satisfied as $X\subseteq V(B_{1})$. If $H_{1}$ has
no contracting sets, then () also holds, and we are done. So assume that $S$
is a contracting set in $H_{1}$. By Claim 5.3 there are blue components
$Q_{1},\dots,Q_{t}$ with $t\leq 2$ such that
$|V(\bigcup_{j\in[t]}Q_{j})|\geq(1/3+3\gamma)n$. Note that $t=2$, since
otherwise $|V(B_{1})|\geq|V(Q_{1})|\geq(1/3+3\gamma)n$ and we are done by
Claim 5.5 again. So, by Claim 5.3() ‣ 5.3, we have $X\subseteq
V(B_{1})\subseteq N_{H_{1}}(S)$. Together with $|X|\geq(1/2+2\gamma)n$, this
contradicts (5.1). This concludes the analysis of the case when $B_{1}$
intersects with $X$.

Now suppose that $V(B_{1})\subseteq Y$. We claim that no bipartite blue
component has a vertex in $X$. Indeed, assume otherwise. Then such a component
has order at least $(1/3+16\gamma)n$ due to being bipartite and
$\delta(G_{\text{blue}}[X])\geq(2/3+8\gamma)n-|Y|\geq(1/6+8\gamma)n$. Hence
$|V(B_{1})|\geq(1/3+16\gamma)n$ by the maximality of $B_{1}$, and we are done
again by Claim 5.5. So blue components with vertices in $X$ are not bipartite.
In particular, $V(B_{i})\subseteq Y\setminus V(B_{1})$.

Next, we show that $B_{5-i}$ has a vertex in $X$. Indeed, assume otherwise.
Owing to $\delta(G_{\text{blue}}[X])\geq(1/6+8\gamma)n$ and $B_{3}$ being the
third largest component, it follows that
$|V(B_{1})|\geq|V(B_{2})|\geq|V(B_{3})|\geq(1/6+8\gamma)n$. Hence
$|Y|\geq|V(B_{1})|+|V(B_{2})|+|V(B_{3})|>n/2$, which contradicts $|X|\geq|Y|$.
So $B_{5-i}$ intersects with $X$, which implies in particular that $B_{5-i}$
is not bipartite.

To finish, we show that $H_{5-i}=R\cup B_{1}\cup B_{5-i}$ satisfies the
conditions of Lemma 4.2. Note that $|V(B_{5-i})|\geq(1/6+8\gamma)n$ as
$\delta(G_{\text{blue}}[X])\geq(1/6+8\gamma)n$. Hence $|V(B_{1})\cup
V(B_{5-i})|\geq(1/3+16\gamma)n$, which gives ()()(). Moreover, () holds as
$B_{5-i}$ is not bipartite. If $H_{5-i}$ has no contracting sets, then we also
have the condition (). Hence assume that $S$ is a contracting set in
$H_{5-i}$.

By Claim 5.3 applied to $H_{5-i}$, there are blue components
$Q_{1},\dots,Q_{t}$ with $t\leq 2$ such that
$|V(\bigcup_{j\in[t]}Q_{j})|\geq(1/3+3\gamma)n$. As before, we observe that
$t=2$, since otherwise $|V(B_{1})|\geq|V(Q_{1})|\geq(1/3+3\gamma)n$, and we
are again done by Claim 5.5. As $B_{i}$ is bipartite, it follows that
$B_{i}\neq Q_{1},Q_{2}$ by Claim 5.3() ‣ 5.3. Moreover, by Claim 5.3() ‣ 5.3,
we have $V(B_{1})\cup V(B_{2})\cup V(B_{3})=V(B_{1})\cup V(B_{5-i})\cup
V(B_{i})\subseteq N_{H_{5}-i}(S)$. On the other hand,
$|V(B_{3})|\geq(1/6+\gamma)n$ since one of $Q_{1}$ and $Q_{2}$ has size at
least $(1/6+\gamma)n$ and $B_{3}$ is the blue component of third largest
order. Hence, $|N_{H_{5-i}}(S)|\geq|V(B_{1}\cup B_{2}\cup
B_{3})|\geq(1/2+3\gamma)n$ in contradiction to (5.1). ∎

By Claim 5.6, we can assume that $H_{2}$ and $H_{3}$ have each a contracting
set, which we denote by $S_{2}$ and $S_{3}$, respectively.

######  Claim 5.7.

We have $|S_{2}|,|S_{3}|\geq(1/2-\gamma)n$.

###### Proof.

Fix $i\in\\{2,3\\}$. By Claim 5.3 applied to $H_{i}$, there are blue
components $Q_{1},\dots,Q_{t}$ for $t\leq 2$, which together cover at least
$(1/3+3\gamma)n$ vertices. If $t=1$, then $Q_{1}$ has order at least
$(1/3+3\gamma)n$. In this case, $B_{1}$ (as the largest blue component) has
also order at least $(1/3+3\gamma)n$, and we are done by Claim 5.5. Hence we
have $t=2$. Now Claim 5.3() ‣ 5.3 yields $V(G)\setminus
N_{H_{i}}(S_{i})\subseteq V(\bigcup_{j\in[t]}Q_{j})$ and, therefore, we must
have $V(B_{1}\cup B_{i})\subseteq N_{H_{i}}(S_{i})$. Since $B_{1},B_{2},B_{3}$
are three blue components of largest order and
$|V(B_{1})|\geq|V(B_{2})|\geq|V(B_{3})|$, we have
$|V(Q_{1})|+|V(Q_{2})|\leq|V(B_{1})|+|V(B_{i})|$. Together, this gives

$\displaystyle n-|S_{i}|-\gamma n$ $\displaystyle\leq|V(G)\setminus
N_{H_{i}}(S_{i})|\leq|V(Q_{1})|+|V(Q_{2})|\leq|V(B_{1})|+|V(B_{i})|$
$\displaystyle\leq|N_{H_{i}}(S_{i})|\leq|S_{i}|+\gamma n.$

Hence $|S_{i}|\geq(1/2-\gamma)n$. ∎

######  Claim 5.8.

We have $|V(B_{2})\cap S_{3}|,\leavevmode\nobreak\ |V(B_{3})\cap
S_{2}|\geq(1/4-4\gamma)n$.

###### Proof.

Since $|S_{2}|\geq(1/2-\gamma)n$ by Claim 5.7, the vertices in $S_{2}$ have at
least $(1/6+7\gamma)n$ blue neighbours in $S_{2}$. It follows from Claim 5.3
that $S_{2}$ is contained in at most two blue components, one of which has
order at least $(1/4-\gamma)n$. Thus
$|V(B_{1})|\geq|V(B_{2})|\geq|V(B_{3})|\geq(1/4-\gamma)n$ by the maximality of
$B_{1},B_{2},B_{3}$. Recall that $H_{2}=R\cup B_{1}\cup B_{2}$ and, therefore,
$S_{2}\cap B_{1}=\emptyset$ and $S_{2}\cap B_{2}=\emptyset$ by (5.3). As
$|S_{2}|\geq(1/2-\gamma)n$, $|V(B_{1})\cup V(B_{2})|\geq(1/2-2\gamma)n$ and
$V(B_{1})\cup V(B_{2})\subseteq V(G)\setminus S_{2}$, the component $B_{3}$
has at most $3\gamma n$ vertices outside of $S_{2}$. Consequently,
$|V(B_{3})\cap S_{2}|\geq(1/4-4\gamma)n$.

Analogously, as $|S_{3}|\geq(1/2-\gamma)n$ by Claim 5.7 and $V(B_{1})\cup
V(B_{3})\subseteq V(G)\setminus S_{3}$, the component $B_{2}$ has at most
$3\gamma n$ vertices outside of $S_{3}$. As a result, we have $|V(B_{2})\cap
S_{3}|\geq(1/4-4\gamma)n$. ∎

Note that $V(B_{1})$ has vertices in neither $S_{2}$ nor $S_{3}$ by (5.3) and
$|V(B_{1})|\geq|V(B_{2})|\geq|V(B_{2})\cap S_{3}|\geq(1/4-4\gamma)n$. So, by
Claim 5.7, there is a vertex $v\in S_{2}\cap S_{3}$. By (5.3) and the
definition of $H_{2}$ and $H_{3}$, the vertex $v$ is not in $V(B_{2}\cup
B_{3})$. At the same time, $v$ has no red neighbours in $S_{2}\cup S_{3}$
since $S_{2},S_{3}$ are stable in $H_{2},H_{3}$ respectively. Therefore, $v$
has no neighbours in $S_{2}\cap V(B_{3})$ and no neighbours $S_{3}\cap
V(B_{2})$. Since $B_{2}$ and $B_{3}$ are distinct blue components, these sets
are disjoint. Moreover, by Claim 5.8, $B_{2}$ and $B_{3}$ have each size at
least $(1/4-4\gamma)n$. Hence $v$ has degree at most
$n-2(1/4-4\gamma)n=(1/2+8\gamma)n$ in contradiction with
$\delta(G)\geq(2/3+8\gamma)n$. This concludes the analysis of the case, where
one of $C_{1}$ and $C_{2}$ is spanning.

###  5.2. Case 2: $C_{1}$ and $C_{2}$ have distinct colours

Suppose that $R:=C_{1}$ is red and $B:=C_{2}$ is blue. If $R$ or $B$ is
spanning, we proceed as in Subsection 5.1. We will show that $R$, $B$ and
another red component together satisfy the conditions of Lemma 4.2.

Since neither $R$ nor $B$ is spanning, there are vertices $v_{R}\in
V(R)\setminus V(B)$ and $v_{B}\in V(B)\setminus V(R)$. Note that

(5.7) $|N_{G}(v_{R})\cap N_{G}(v_{B})|\geq(1/3+16\gamma)n.$

Moreover, any common neighbour of $v_{R}$ and $v_{B}$ must lie in $V(R)\cap
V(B)$ (if for instance, $v_{R}$ has a neighbour $v\in V(B)\setminus V(R)$ then
the edge $v_{R}v$ cannot be red and it cannot be blue, a contradiction). It
follows that

(5.8) $|V(R)\cap V(B)|\geq(1/3+16\gamma)n.$

Similarly, observe that, for $i\in\\{1,2\\}$,

(5.9) $|V(R)\setminus V(B)|\leq|V(G)\setminus N_{G}(v_{B})|<(1/3-8\gamma)n$

and hence $|V(B)|\geq(2/3+8\gamma)n$. By symmetry, the same is true for
colours flipped.

Let $R^{\prime}$ be the red component of largest order in $B-V(R)$. Note that
any vertex $v^{\prime}_{B}$ in $B-V(R\cup R^{\prime})$ is incident to fewer
than $(1/6-4\gamma)n$ red edges. Indeed, otherwise
$|V(R^{\prime})|\geq(1/6-4\gamma)n$ (by maximality of $R^{\prime}$), and so
$v^{\prime}_{B}$ sends a red edge to $R^{\prime}$ by (5.9) (with colours
flipped).

We claim that $H:=R\cup B\cup R^{\prime}$ satisfies items ()–() of Lemma 4.2.
As by Claim 5.1, $R\cup B$ spans $G$, part () is trivial and part () holds
because of (5.8). By (5.7), and because of our assumption on the minimum
degree of $G$, we know that $G[N(v_{R})\cap N(v_{B})]$ contains an edge. If
this edge is red, $v_{R}$ is in a red triangle, and if it is blue, $v_{B}$ is
in a blue triangle. Hence part () follows.

It remains to show that part () is satisfied. To this end, we assume there is
a contracting set $S$ in $H$ and show that this results in a contradiction.
Observe that any vertex $v$ in $V(R)\cap V(B)$ or in $V(R^{\prime})$ has
degree

$\deg_{H}(v)\geq(2/3+8\gamma)n.$

Also, recall that by definition of $R^{\prime}$, any vertex $v^{\prime}_{B}\in
V(B)\setminus V(R\cup R^{\prime})$ has
$\deg_{\text{red}}(v^{\prime}_{B})<(1/6-4\gamma)n$ and so

$\deg_{H}(v^{\prime}_{B})>(2/3+8\gamma)n-(1/6-4\gamma)n=(1/2+12\gamma)n.$

On the other hand, since $S$ is contracting, we have
$|N_{H}(S)|\leq(1/2+\gamma/2)n$ by (5.1). Since $|N_{H}(S)|\geq\deg_{H}(v)$
for any $v\in S$, this means that $S\subseteq V(R)\setminus V(B)$. By (5.9)
this gives $|S|\leq(1/3-8\gamma)n$. However, any vertex $v^{\prime}_{R}\in
V(R)\setminus V(B)$ has

$\deg_{H}(v^{\prime}_{R})\geq(2/3+8\gamma)n-|V(R)\setminus
V(B)|\overset{\eqref{equ:V(C_i)-sm-V(C_j)<1/3-gamma}}{\geq}(1/3+16\gamma)n.$

Thus $|N_{H}(S)|\geq|S|+24\gamma n$. So, contrary to our assumption, $S$ is
not contracting.

###  5.3. Case 3: $C_{1}$ and $C_{2}$ have the same colour

Suppose that $R_{1}:=C_{1}$ and $R_{2}:=C_{2}$ are both red with

(5.10) $|V(R_{1})|\geq n/2\geq|V(R_{2})|.$

Let $B_{1},\ldots,B_{t}$ be the blue components that intersect with $R_{2}$.
If $t=1$, or if one of the $B_{i}$ contains $R_{1}$, we proceed as in
Subsection 5.2. Hence we can assume that $t\geq 2$, and $R_{1}\not\subseteq
B_{i}$, for $1\leq i\leq t$.

We begin by showing that $t=2$. To this end, let $v_{i}\in V(B_{i})\cap
V(R_{2})$, for $i\in[t]$. If $t\geq 3$, then (using (5.10) for the third
inequality),

$\displaystyle|V(R_{1})|\geq\sum_{i\in[3]}\deg(v_{i},V(R_{1}))$
$\displaystyle\geq 3\big{(}(2/3+8\gamma)n-|V(R_{2})|\big{)}$
$\displaystyle>2n-(n+|V(R_{2})|)$ $\displaystyle=n-|V(R_{2})|,$

a contradiction. So indeed $t=2$.

$I_{2,1}$$I_{2,2}$$I_{1,1}$$I_{1,2}$$R_{2}$$R_{1}$$B_{1}$$B_{2}$ Figure 3. The
partition of $G$ in Case 3.

Now let us partition $V(G)$ into non-empty sets

$I_{i,j}:=V(R_{i})\cap V(B_{j})$

for $i,j\in[2]$ as illustrated in Figure 3. Since vertices in $I_{i,j}$ have
no neighbours in $I_{3-i,3-j}$ and as $\delta(G)\geq(2/3+8\gamma)n$, we obtain

(5.11) $|I_{i,j}|<(1/3-8\gamma)n\text{ for $i,j\in[2]$}.$

In particular,

(5.12) each of $R_{1},R_{2},B_{1},B_{2}$ has at least $(1/3+16\gamma)n$
vertices,

and moreover,

$\displaystyle\delta\big{(}G[I_{i,j}]\big{)}$
$\displaystyle\geq\delta(G)-|I_{{3-i},j}\cup I_{i,{3-j}}|$ (5.13)
$\displaystyle\overset{\eqref{equ:I<1/3}}{\geq}(2/3+8\gamma)n-2(1/3-8\gamma)n\geq
24\gamma n.$

We will show that three components among $R_{1},R_{2},B_{1},B_{2}$ can be
selected so that they satisfy the conditions of Lemma 4.2 unless the colouring
is $(4\gamma)$-extremal as in Definition 4.1() ‣ 4.1 in contradiction to our
assumption. Note that for any such choice, Lemma 4.2() holds since $R_{1}\cup
R_{2}$, $B_{1}\cup B_{2}$ span $G$ and part ()()() follows by (5.12). The next
claim yields part ().

######  Claim 5.9.

If one colour has a bipartite component, then the other colour has no
bipartite component.

###### Proof.

Suppose that there is a bipartite component, say $R_{1}$. We claim that

(5.14) the bipartition classes of $R_{1}$ are $I_{1,1}$ and $I_{1,2}$.

Indeed, otherwise one of the two sets, say $I_{1,1}$, contains vertices $x,y$
from different bipartition classes. Clearly, the neighbourhoods of $x$ and $y$
in $R_{1}$ are disjoint. Note that the neighbours of $x$ and $y$ in $G$ are in
$I_{1,2}\cup B_{1}$. Thus, each of $x$ and $y$ has at least
$(2/3+8\gamma)n-|V(B_{1})|$ neighbours in $I_{1,2}$. Thus by (5.11),

$2\big{(}(2/3+8\gamma)n-|V(B_{1})|\big{)}\leq|I_{1,2}|<(1/3-8\gamma)n,$

implying that $|V(B_{1})|>n/2$. Applying the same argument to neighbours
$x^{\prime},y^{\prime}$ of $x,y$ in $I_{1,2}$, we obtain that $|V(B_{2})|>n/2$
as well. This is a contradiction, which proves (5.14).

If, $B_{1}$ say, is bipartite as well, then the same reasoning shows that one
of its bipartition classes is $I_{1,1}$. Consequently $I_{1,1}$ contains no
edges, in contradiction to (5.13). This proves the claim. ∎

It remains to show that either there is a choice of three components among
$R_{1},R_{2},B_{1},B_{2}$ satisfying Lemma 4.2() or the colouring is
$(4\gamma)$-extremal as in Definition 4.1() ‣ 4.1. To this end, assume that no
choice of three components among $R_{1},R_{2},B_{1},B_{2}$ fulfils Lemma
4.2().

For each $i\in[2]$, let $S_{R_{i}}$ be a contracting set of minimum size in
$G-E(R_{i})$, and let $S_{B_{i}}$ be a contracting set of minimum size in
$G-E(B_{i})$. If $v\in V(R_{3-i})$ then $\deg_{G}(v)=\deg_{G-E(R_{i})}(v)$,
and so, $v\notin S_{R_{i}}$ by (5.1). It follows by symmetry that for
$i\in[2]$,

(5.15) $S_{R_{i}}\subseteq V(R_{i})$ and $S_{B_{i}}\subseteq V(B_{i})$.

In fact, we can show slightly more.

######  Claim 5.10.

For each $i\in[2]$ there is $j\in[2]$ such $S_{R_{i}}\subseteq I_{i,j}$.
Similarly, for each $i\in[2]$ there is $j\in[2]$ such that $S_{B_{i}}\subseteq
I_{j,i}$.

###### Proof.

Suppose that the claim does not hold for, say $S_{R_{2}}$. So, by (5.15),
$S_{R_{2}}\cap V(B_{i})\neq\emptyset$ for $i=1,2$. Then

$\displaystyle|S_{R_{2}}\cap V(B_{1})|+|$ $\displaystyle S_{R_{2}}\cap
V(B_{2})|+2\gamma n=|S_{R_{2}}|+2\gamma n$
$\displaystyle>|N_{G-E(R_{2})}(S_{R_{2}})|+\gamma n$
$\displaystyle>|N_{G-E(R_{2})}(S_{R_{2}})|$
$\displaystyle\geq|N_{G-E(R_{2})}\left(S_{R_{2}}\cap
V(B_{1})\right)|+|N_{G-E(R_{2})}\left(S_{R_{2}}\cap V(B_{2})\right)|,$

where the last line follows because the red edges incident with $S_{R_{2}}$
belong to $R_{2}$ and are therefore not present in $G-E(R_{2})$. And,
moreover, there are no blue edges between $V(B_{1})$ and $V(B_{2})$. Thus by
Definition 5.2, at least one of $S_{R_{2}}\cap V(B_{1})$, $S_{R_{2}}\cap
V(B_{2})$ is a contracting set, in contradiction to the minimality of
$S_{R_{2}}$. ∎

######  Claim 5.11.

Let $i,j\in[2]$. If $S_{R_{i}}\cap V(B_{j})\neq\emptyset$, then
$I_{3-i,j}\subseteq N_{G-E(R_{i})}(S_{R_{i}})$. Similarly, if $S_{B_{i}}\cap
V(R_{j})\neq\emptyset$, then $I_{j,3-i}\subseteq N_{G-E(B_{i})}(S_{B_{i}})$.

###### Proof.

Suppose the claim is wrong for $S_{R_{2}}$ and $B_{1}$. Let $v\in
S_{R_{2}}\cap V(B_{1})$ and $w\in I_{1,1}\setminus N_{G-E(R_{2})}(S_{R_{2}})$.
Then by Claim 5.10, $S_{R_{2}}\subseteq I_{2,1}.$ Since $S_{R_{2}}$ is
contracting in $G-E(R_{2})$, we have

$|S_{R_{2}}|+\gamma
n>|N_{G-E(R_{2})}(S_{R_{2}})|\geq\deg_{G-E(R_{2})}(v)\geq(2/3+8\gamma)n-|V(R_{2})|.$

Moreover, as $w$ has its neighbours in $G$ in $I_{2,1}\cup R_{1}$,

$|I_{2,1}\setminus
S_{R_{2}}|\geq\deg_{G-E(R_{2})}(w,I_{2,1})\geq(2/3+8\gamma)n-|V(R_{1})|.$

Summing the two inequalities (recalling that $S_{R_{2}}\subseteq I_{2,1}$)
gives

$|I_{2,1}|>(4/3+15\gamma)n-|V(R_{1}\cup R_{2})|=(1/3+15\gamma)n,$

in contradiction to (5.11). ∎

######  Claim 5.12.

For each $i,j\in[2]$, the set $I_{i,j}$ contains at most one of the sets
$S_{R_{1}},S_{R_{2}},S_{B_{1}},S_{B_{2}}$.

###### Proof.

Suppose the claim is wrong for $i=j=2$, namely, we suppose that
$S_{R_{2}},S_{B_{2}}\subseteq I_{2,2}.$ Then by Claim 5.11,

(5.16) $I_{2,1}\subseteq N_{G-E(B_{2})}(S_{B_{2}})\text{ and }I_{1,2}\subseteq
N_{G-E(R_{2})}(S_{R_{2}}).$

As $S_{R_{2}}$ and $S_{B_{2}}$ are each contracting, this gives

$|I_{2,1}|<|S_{B_{2}}|+\gamma n\text{ and }|I_{1,2}|<|S_{R_{2}}|+\gamma n.$

So, for any $v\in I_{2,2}$, we have

$\displaystyle\deg_{G}(v,I_{2,2})$
$\displaystyle\geq(2/3+8\gamma)n-|I_{1,2}|-|I_{2,1}|$
$\displaystyle\geq|I_{2,2}|-|I_{1,2}|+|I_{2,2}|-|I_{2,1}|+24\gamma n$
$\displaystyle>|I_{2,2}|-|S_{R_{2}}|+|I_{2,2}|-|S_{B_{2}}|+22\gamma n$

where the second inequality follows from (5.11). Hence $v$ satisfies at least
one of the following:

$\deg_{\text{blue}}(v,I_{2,2})>|I_{2,2}|-|S_{R_{2}}|+11\gamma n\text{ \ \ or \
\ }\deg_{\text{red}}(v,I_{2,2})>|I_{2,2}|-|S_{B_{2}}|+11\gamma n.$

Let us call $T_{B}$ the set of all vertices in $I_{2,2}$ satisfying the first
inequality and let $T_{R}$ be the set of all vertices in $I_{2,2}$ satisfying
the second inequality. Note that $T_{R}\cup T_{B}=I_{2,2}$. Moreover, vertices
in $T_{B}$ must each have a blue edge to $S_{R_{2}}$, and similarly vertices
in $T_{R}$ have each a red edge to $S_{B_{2}}$. Putting this together with
(5.16), we obtain

$T_{R}\cup I_{2,1}\subseteq N_{G-E(B_{2})}(S_{B_{2}})\text{ and }T_{B}\cup
I_{1,2}\subseteq N_{G-E(R_{2})}(S_{R_{2}}).$

By definition of $T_{R}$ and since the set $S_{R_{2}}$ is stable in
$G-E(R_{2})$, we have $S_{R_{2}}\subseteq T_{R}$. So, because of (5.13),

$|S_{R_{2}}|\leq|T_{R}|\leq|N_{G-E(B_{2})}(S_{B_{2}})|-|I_{2,1}|\leq|S_{B_{2}}|+\gamma
n-24\gamma n<|S_{B_{2}}|,$

and similarly, $|S_{B_{2}}|<|S_{R_{2}}|$, a contradiction. ∎

By Claim 5.10 and Claim 5.12 we can assume without loss of generality that
$S_{R_{2}}\subseteq I_{2,1}$, $S_{B_{1}}\subseteq I_{1,1}$,
$S_{R_{1}}\subseteq I_{1,2}$ and $S_{B_{2}}\subseteq I_{2,2}$. Thus Claim 5.11
yields the following inequalities

$\displaystyle|I_{1,1}|$
$\displaystyle\leq|N_{G-E(R_{2})}(S_{R_{2}})|<|S_{R_{2}}|+\gamma
n\leq|I_{2,1}|+\gamma n;$ $\displaystyle|I_{2,1}|$
$\displaystyle\leq|N_{G-E(B_{2})}(S_{B_{2}})|<|S_{B_{2}}|+\gamma
n\leq|I_{2,2}|+\gamma n;$ $\displaystyle|I_{2,2}|$
$\displaystyle\leq|N_{G-E(R_{1})}(S_{R_{1}})|<|S_{R_{1}}|+\gamma
n\leq|I_{1,2}|+\gamma n;\text{ and}$ $\displaystyle|I_{1,2}|$
$\displaystyle\leq|N_{G-E(B_{1})}(S_{B_{1}})|<|S_{B_{1}}|+\gamma
n\leq|I_{1,1}|+\gamma n.$

Hence the colouring is $(4\gamma)$-extremal as in Definition 4.1() ‣ 4.1,
which contradicts our initial assumption. This finishes the proof of Lemma
4.2.

##  6\. Covering exceptional vertices: The proof of Lemma 4.6

The proof of Lemma 4.6 goes roughly as follows. We first pick two sparse and
pairwise disjoint families of paths $P^{\text{Edge}}$ and
$P^{\text{\text{Exc}}}$ such that $P^{\text{Edge}}$ supports paths embeddings
in the $H_{i}$’s and $P^{\text{\text{Exc}}}$ contains the vertices $W$. We
choose the families such that each of their paths connects to one of the
$H_{i}$’s. This allows Lemma 3.9 to connect these families up to three
monochromatic cycles $C=C_{1}\cup C_{2}\cup C_{3}$. Finally, we adjust the
parity of $V(G)\setminus V(C)$ using either an odd cycle in one of the
$H_{i}$’s or the fact that otherwise $H_{3}=\emptyset$, in which case we can
set $C_{3}$ to be a single vertex.

Before we start, let us formalize what we mean by a path connecting to one of
the $H_{i}$’s.

######  Definition 6.1 ($\delta$-connect).

Suppose $G$ is a $2$-edge-coloured graph on $n$ vertices and let
$\mathcal{V}=\\{V_{1},\ldots,V_{m}\\}$ be an $(\varepsilon,d)$-regular
partition of $G$. Let $\mathcal{G}$ be the corresponding $2$-edge-coloured
$(\varepsilon,d)$-reduced multi-graph. For $\delta>0$, we say that a path
$P\subseteq G_{\chi}$ $\delta$-connects to $H\subseteq\mathcal{G}_{\chi}$, if
both ends of $P$ have at least $\delta|V_{x}|$ edges of colour $\chi$ leading
to the same cluster $V_{x}$ for some $x\in V(H)$.

###### Proof of Lemma 4.6.

Let ${1}/{n}\ll\varepsilon,1/m\ll d\ll\beta\ll 1$ such that Lemma 3.9 holds
with input $\varepsilon,d,m,\ell=m+2,n$. Let $t$ be the size of the clusters
$V_{1},\ldots,V_{m}$.

######  Claim 6.2.

Let $S\subseteq V(G)$ be $\delta$-sparse in $\mathcal{V}$. Then there is a
family $P^{\text{Edge}}$ of at most $2m^{2}$ monochromatic paths with the
following properties:

  * •

the paths of $P^{\text{Edge}}$ are pairwise disjoint and disjoint from $S$;

  * •

For each $i$, the paths of $P^{\text{Edge}}$ with the same colour as $H_{i}$
support path embeddings in $H_{i}$;

  * •

each path of $P^{\text{Edge}}$ $(d/2)$-connects to one of the $H_{i}$’s.

###### Proof.

We choose the paths $P^{\text{Edge}}$ greedily as follows. For each $i\in[3]$,
we order arbitrarily the edges of $H_{i}$. When we come to the edge $pq$ of
$H_{i}$, we choose a $2$-edge path with both ends in $V_{p}$ and the middle
vertex in $V_{q}$, which is disjoint from previously chosen paths and from
$S$, whose end-vertices both have at least $dt/2$ neighbours in the colour of
$H_{i}$ in $V_{q}$. Since at most $2\varepsilon t$ vertices of $V_{p}$ do not
have degree at least $dt/2$ to $V_{q}$ in the colour of $H_{i}$, and at most
$6m^{2}+\delta|V_{p}|$ vertices of $V_{p}$ are contained in previously chosen
paths or in $S$, we are left with at least $\tfrac{1}{2}|V_{p}|$ vertices of
$V_{p}$ to choose the endpoints from, and similarly at least
$\tfrac{1}{2}|V_{q}|$ vertices of $V_{q}$ to choose the middle vertex from.
Since $V_{p}V_{q}$ is an edge of $H_{i}$, by definition of
$\varepsilon$-regularity there is such a $2$-edge path in the colour of
$H_{i}$ as desired. ∎

The next two claims take care of the exceptional vertices.

######  Claim 6.3.

Suppose that $|\bigcup_{i\neq j}V(H_{i})\cap V(H_{j})|\geq m/3$. Let $S$ be
$\delta$-sparse in $\mathcal{V}$. Then there is a family
$P^{\text{\text{Exc}}}$ of at most $\beta^{-2}$ monochromatic paths with the
following properties:

  * •

the paths of $P^{\text{\text{Exc}}}$ are pairwise disjoint and disjoint from
$S$;

  * •

the set $V(P^{\text{\text{Exc}}})$ contains $W$ and is $\sqrt{\delta}$-sparse
in $\mathcal{V}$;

  * •

each path of $P^{\text{\text{Exc}}}$ $(d/2)$-connects to one of the $H_{i}$’s.

###### Proof.

Let us define

$\mathcal{Z}=\bigcup_{1\leq i\neq j\leq 3}V(H_{i})\cap V(H_{j})\subseteq
V(\mathcal{G}),\quad Z=\bigcup_{x\in\mathcal{Z}}V_{x}\subseteq V(G).$

We set $r=\lceil 4/\beta\rceil$. By assumption we have
$|\mathcal{Z}|\geq\tfrac{m}{3}$ and hence

$|Z|\geq(n-|V_{0}|)|\mathcal{Z}|/m\geq n/3-\varepsilon n.$

So as $\delta(G)\geq(2/3+\beta)n$, it follows that $\deg_{G}(w,Z)\geq\beta
n/2\geq 2n/r$ for any $w\in V(G)$. We partition $W$ by setting $W_{1}:=\\{v\in
W\colon\deg_{\text{red}}(v,Z)\geq n/r\\}$ and $W_{2}:=W\setminus W_{1}$. For
$i\in[2]$ define an auxiliary graph $A_{i}$ on vertex set $W_{i}$, by
connecting two vertices $v,w\in W_{i}$ if $|N_{i}(v,Z)\cap N_{i}(w,Z)|\geq
n/r^{3}$. We claim that

(6.1) the independence number of $A_{i}$ is bounded by $r$.

Indeed, suppose otherwise and let $w_{1},\ldots,w_{r+1}$ be pairwise disjoint
non-adjacent vertices in $A_{i}$. We then obtain the following contradiction.

$\displaystyle|Z|$
$\displaystyle\geq\left|\bigcup_{p\in[r+1]}N_{i}(w_{p},Z)\right|$
$\displaystyle\geq(r+1)\frac{n}{r}-\sum_{1\leq q<p\leq r+1}|N_{i}(w_{q},Z)\cap
N_{i}(w_{p},Z)|$
$\displaystyle\geq|Z|\Big{(}\frac{r+1}{r}-\frac{\binom{r+1}{2}}{r^{3}}\Big{)}>|Z|.$

This proves (6.1). Now a classic result of Pósa (see [30]) guarantees that
$A_{i}$ can be partitioned into $r_{i}\leq r$ disjoint cycles
$C_{i,1},\ldots,C_{i,r_{i}}$, where we consider edges and vertices to be
cycles of lengths respectively $2$ and $1$.

To finish, we build from each $C_{i,j}$ a path $P_{i,j}$ of colour $i$ that
$(d/2)$-connects to one of $H_{1},H_{2},H_{3}$, such that the union of these
paths is $\sqrt{\delta}$-sparse in $\mathcal{V}$. In addition to this, we
require the paths $P_{i,j}$ to be pairwise disjoint and disjoint from $S$.
This can be done greedily as follows. We break $C_{i,j}$ into a path by
removing one edge, and then create $P_{i,j}$ by connecting one after another
two adjacent vertices of this path with a vertex in $Z$.

To see that we never run out of available vertices in this process, note that
by definition of $r$ each two adjacent vertices in one of the $C_{i,j}$’s
share $(\beta/4)^{3}n$ common neighbours of colour $i$ in $Z$. So each two
adjacent vertices in one of the $C_{i,j}$’s have at least
$(\beta^{3}/8)t\geq(d/2)t$ common neighbours in some cluster of $\mathcal{Z}$.
Moreover, the restriction of $\sqrt{\delta}$-sparseness and disjointness
renders at most

$\frac{|W|}{\sqrt{\delta}t}\cdot t+2|W|+|S|\leq 3\sqrt{\delta}n$

vertices unavailable at any point of embedding.

Finally, note that since there is an edge in $C_{i,j}$ between the first and
last vertices $w$ and $z$ of $P_{i,j}$, so $w$ and $z$ have at least $n/r^{3}$
common neighbours in $Z$ in colour $i$. By averaging, some cluster $V_{p}$ of
$\mathcal{Z}$ contains at least $t/r^{3}$ of these common neighbours. Picking
$H_{i,j}$ to be one of $H_{1},H_{2},H_{3}$ which contains $V_{p}$ and is of
colour $i$ (which must exist since $V_{p}$ is in two of the
$H_{1},H_{2},H_{3}$ and these two have different colours by condition () of
Lemma 4.6) we see that $P_{i,j}$ is $(d/2)$-connected to $H_{i,j}$. ∎

######  Claim 6.4.

Suppose that ()()() of the assumptions of Lemma 4.6 holds. Let $S$ be
$\delta$-sparse in $\mathcal{V}$. Then there is a family
$P^{\text{\text{Exc}}}$ of at most $\beta^{-2}$ monochromatic paths and a
monochromatic cycle $C_{3}$ with the following properties:

  * •

the paths of $P^{\text{\text{Exc}}}$ are pairwise disjoint and disjoint from
$S$;

  * •

the set $V(P^{\text{\text{Exc}}})\cup V(C_{2})$ contains $W$ and is
$\sqrt{\delta}$-sparse in $\mathcal{V}$;

  * •

each path of $P^{\text{\text{Exc}}}$ $(d/2)$-connects to $H_{1}$.

###### Proof.

The proof is very similar to the one of Claim 6.3. Without loss of generality
we can assume that $H_{1}$ is red. We define

$\mathcal{Z}=V(H_{1})=V(\mathcal{G}),\quad
Z=\bigcup_{x\in\mathcal{Z}}V_{x}\subseteq V(G).$

By the assumptions we have

$|Z|\geq(n-|V_{0}|)|\mathcal{Z}|/t\geq(1-\varepsilon)n.$

It follows that $\deg_{G}(w,Z)\geq(2/3+\beta/2)$ for any $w\in V(G)$. As
before, we us set $r=\lceil 4/\beta\rceil$. We can partition $W$ by setting
$W_{1}:=\\{v\in W\colon\deg_{\text{red}}(v,Z)\geq n/r\\}$ and
$W_{2}:=W\setminus W_{1}$. For the set $W_{1}$ we proceed as in Claim 6.3. For
$W_{2}$, however, note we now have $\deg_{2}(v,Z)\geq(2/3+\beta/4)n$ for every
$v\in W_{2}$. Hence we can greedily construct a single blue cycle $C_{3}$ for
the vertices $W_{2}$, which has the desired properties. ∎

Now we can finish the proof of Lemma 4.6. If $H_{i}$ has no edges for some
$i\in[3]$ we replace it with $H_{i}=\emptyset$. Since $H_{1}$ and $H_{3}$ are
monochromatic components, and $H_{2}$ is the union of at most two
monochromatic components, if $H_{i}$ has no edges then it has at most two
vertices. So after this step the assumptions of the lemma still hold with
()()() relaxed to $|\bigcup_{i\neq j}V(H_{i})\cap
V(H_{j})|\geq(1/3+\gamma/2)m$. Next, if $H_{i}=\emptyset$ for some $i\in[2]$,
we take $C_{i}$ to be the empty set. If $H_{3}=\emptyset$ and we are not in
case ()()(), we also take $C_{3}$ to be the empty set. (Note that in case
()()(), $C_{3}$ plays a more active role as detailed in Claim 6.4.) In all
other cases we construct the $C_{i}$’s as follows.

Let us first handle the case, where ()()() of the assumptions of Lemma 4.6
holds. By assumption (), if $H_{2}\neq\emptyset$, then $H_{2}$ is the union of
monochromatic components $F_{1}$ and $F_{2}$, which admit bridges (Definition
4.3). Hence there are distinct vertices $u,u^{\prime}$ in $G$, which each
$d$-connect to both $F_{1}$ and $F_{2}$, and we let
$P^{\text{Bridge}}=\\{u,u^{\prime}\\}$ be the set of these two one-vertex
paths. If $H_{2}=\emptyset$ then we set $P^{\text{Bridge}}=\emptyset$. We fix
a family of paths $P^{\text{Edge}}$ obtained from an application of Claim 6.2
with $S=V(P^{\text{Bridge}})$. Next we fix a family of paths
$P^{\text{\text{Exc}}}$ of size at most $\beta^{-2}$ obtained from an
application of Claim 6.3 with $S=V(P^{\text{Edge}}\cup P^{\text{Bridge}})$.
Note that $P^{\text{Bridge}}\cup P^{\text{Edge}}\cup P^{\text{\text{Exc}}}$ is
$2\sqrt{\delta}$-sparse in $\mathcal{V}$ and contains at most
$2+2t^{4}+\beta^{-2}$ paths.

We partition the paths $P^{\text{Edge}}\cup
P^{\text{\text{Exc}}}=\mathcal{P}_{1}\cup\mathcal{P}_{2}\cup\mathcal{P}_{3}$
such that each path in $\mathcal{P}_{i}$ is $(d/2)$-connected to $H_{i}$. For
$H_{2}$ we partition $\mathcal{P}_{2}=\mathcal{P}_{2,1}\cup\mathcal{P}_{2,2}$
further such that each path in $\mathcal{P}_{2,j}$ is $(d/2)$-connected to
$F_{j}$. To finish we apply Lemma 3.9 to connect the $\mathcal{P}_{i}$’s up to
three monochromatic cycles. At this point it is important that
$H_{1},H_{3},F_{1},F_{3}$ are monochromatic connected subgraphs.

For $H_{1}$ we orient the paths of $\mathcal{P}_{1}$ arbitrarily and then
choose an arbitrary cyclic order of $\mathcal{P}_{1}$. We then use Lemma 3.9
to connect one of the $dm$ neighbours of the end of each path of
$\mathcal{P}_{1}$ with one of the $dm$ neighbours of the start of the next
path of $\mathcal{P}_{1}$ (in the chosen order). Note that since $H_{1}$ is a
connected graph on at most $m$ vertices, any such connection requires a path
with at most $m+1$ vertices. This way we obtain the cycle $C_{1}$ and
similarly $C_{3}$. For $H_{2}$ we want to use the paths $P^{\text{Bridge}}$.
So for each $j\in[2]$ we orient the paths of $\mathcal{P}_{2,j}$ arbitrarily,
then choose an order on the paths of $\mathcal{P}_{2,j}$ which starts in a
cluster with many colour-$H_{2}$-neighbours of $u$. We then proceed as before
to obtain the cycle $C_{2}$, except that after connecting the paths of
$\mathcal{P}_{2,j}$ we add one further connecting path to a
colour-$H_{2}$-neighbour of $u^{\prime}$.

Recall that $P^{\text{Bridge}}\cup P^{\text{Edge}}\cup P^{\text{\text{Exc}}}$
is $2\sqrt{\delta}$-sparse in $\mathcal{V}$ and contains at most
$2+2t^{4}+\beta^{-2}$ paths. Since each of the application of Lemma 3.9 yields
a path of order at most $2t^{2}$ and
$(2+2t^{4}+\beta^{-2})2t^{2}\ll\sqrt{\delta}m$, it follows that $C=C_{1}\cup
C_{2}\cup C_{3}$ is $(3\sqrt{\delta})$-sparse in $\mathcal{V}$. Hence by
setting $S$ to contain the vertices of all paths chosen so far in each of the
above applications of Lemma 3.9, we can guarantee that the $C_{i}$’s are
vertex disjoint.

It remains to ensure that $V(G)\setminus C$ has even size. So suppose this is
not the case. If each of the $H_{i}$’s is bipartite, then $H_{3}=\emptyset$ by
assumption and so $C_{3}=\emptyset$. In this case we set $C_{3}=v$ for some
unused vertex $v\in V(G)\setminus V(C)$. On the other hand, suppose, $F_{1}$
say, has an odd cycle. Note that this implies that $F_{1}$ contains walks of
any parity between any two vertices. Let $P$ be one of the paths obtained by
Lemma 3.9 and which connects two paths of $\mathcal{P}_{2,1}$. We use Lemma
3.9 to swap $P$ for a path $P^{\prime}$ whose order has the opposite parity to
that of $P$. Then $C^{\prime}=C_{1}\cup C_{2}\cup C_{3}\setminus P\cup
P^{\prime}$ has the desired parity. The cases where $H_{1}$, $H_{3}$, or
$F_{2}$ have an odd cycle are handled the same way. This finishes the proof
for the case ()().

Now assume that ()()() of the assumptions of Lemma 4.6 holds. We proceed very
similarly. The main difference is that the paths returned by Lemma 6.4
correspond only to $H_{1}$ and $H_{2}$, i.e. $\mathcal{P}_{3}=\emptyset$. So
for $H_{1},H_{2}$ we can proceed as in the case of ()() and obtain cycles
$C_{1},C_{2}$. Finally, we take $C_{3}$ to be the cycle returned by Lemma 6.4,
which is possible as by ()() we have $H_{3}=\emptyset$. It remains to ensure
that $V(G)\setminus C$ has even size. As in case ()() we are guaranteed that
$H_{1}$ or $H_{2}$ contains an odd cycle, we may swap a path $P$ for a path
$P^{\prime}$ whose order is of the opposite parity as we did in case ()() to
obtain a set of cycles of the desired parity. ∎

##  7\. Balancing: The proof of Lemma 4.7

In this section we prove Lemma 4.7. The idea is simple. First we set some
$t_{e}$ equal to one and others to zero such that the shortfall at each vertex
is even. Then we create an auxiliary graph $H^{\prime}$ obtained by blowing up
each vertex of $H$ to exactly half its shortfall number of vertices, and find
a $2$-matching in $H^{\prime}$; this tells us how much to increment each
$t_{e}$ by.

###### Proof of Lemma 4.7.

Suppose $t\geq m/\gamma$ and let $H$ be a connected $m$-vertex graph that is
$\gamma$-robust Tutte. For a vertex $i$ in $H$ denote by $E_{i}$ the set of
edges in $H$ such that $i\in e$.

We start with adjusting parity for $i$ by defining $\pi_{e}$ for $e\in E(H)$
such that $t_{i}-\sum_{e\in E_{i}}\pi_{e}$ is even. For this purpose let $T$
be an arbitrary spanning tree in $H$ with root $r$. The idea is that for the
leaves $i$ of this tree, the value $\pi_{e}$ for the single edge $e$
containing $i$ will adjust the parity of $t_{i}$. Then we will work upwards
from the leaves to the root, iteratively adjusting the parity of $t_{i}$ for a
vertex $i$ by appropriately setting $\pi_{e}$ for the unique edge $e$
containing $i$ in the path from $i$ to $r$. How we set this $\pi_{e}$ depends
on the value of the $\pi_{e^{\prime}}$ for the other edges containing $i$ that
we set previously.

Formally, for each $ij=e\in E(T)$ with $j$ closer to the root than $i$, let
$X(e)$ denote the set of vertices of the component of $T-e$ that contains $i$.
If $e\not\in E(T)$ then we set $\pi_{e}=0$. For $e\in E(T)$ let
$\pi_{e}=(\sum_{j\in X(e)}t_{j})\\!\\!\mod 2$. We have for each $i\in V(H)$
that

(7.1) $t_{i}-\sum_{e\in E_{i}}\pi_{e}=t_{i}-\sum_{e\in E(T)\cap
E_{i}}\pi_{e}=t_{i}-\sum_{e\in E(T)\cap E_{i}}\bigg{(}\Big{(}\sum_{j\in
X(e)}t_{j}\Big{)}\mod 2\bigg{)}\,.$

Now, let $e_{1},\dots,e_{s}$ be the edges in $E_{i}$, where $e_{1}$ is the
unique edge among these such that $j$ is closer to the root than $i$. Observe
that we have $X(e_{\ell})\cap X(e_{\ell^{\prime}})=\emptyset$ for each
$2\leq\ell<\ell^{\prime}\leq s$ and
$X(e_{1})=\\{i\\}\cup\bigcup_{2\leq\ell\leq s}X(e_{\ell})$. This implies that
in the last sum in (7.1) the terms appearing are exactly the following: The
term $t_{i}$ appears once, and for each $j\in X(e_{1})\setminus\\{i\\}$ the
term $t_{j}$ appears twice. We conclude that the quantity
$2n_{i}:=t_{i}-\sum_{e\in E_{i}}\pi_{e}$ is an even integer, so that $n_{i}$
is an integer. Since $t\geq 5m/\gamma$ we have $|E_{i}|\leq m\leq\gamma t/5$
for each $i$, and so because $t_{i}=(1\pm\frac{1}{5}\gamma)t$ we get
$n_{i}=(1\pm\frac{2}{5}\gamma)t/2$.

In the second part of this proof, we will define non-negative integers
$t^{\prime\prime}_{e}$ such that

(7.2) $\sum_{e\in E_{i}}t^{\prime\prime}_{e}=2n_{i}\,.$

This suffices to prove the lemma since setting
$t_{e}:=t^{\prime\prime}_{e}+\pi_{e}$ gives non-negative values such that
$\sum_{e\in E_{i}}t_{e}=2n_{i}+\sum_{e\in E_{i}}\pi_{e}=t_{i}$ as desired.

For obtaining these $t^{\prime\prime}_{e}$, consider the graph $H^{\prime}$
obtained from $H$ by blowing up each $i$ into an stable set $W_{i}$ of $n_{i}$
vertices, and replacing edges with complete bipartite graphs. Let $S^{\prime}$
be a stable set in $H^{\prime}$. We aim to show
$\big{|}N_{H^{\prime}}(S^{\prime})\big{|}\geq|S^{\prime}|$. Without loss of
generality, we can assume $S^{\prime}$ is a union of the blow-ups of some
vertices $S\in V(H)$ (otherwise we can add any vertices missing from such a
blow-up to $S^{\prime}$ without changing the left hand side), where $S$ must
be a stable set in $H$. Then, since $H$ is $\gamma$-robust Tutte, we have

$\begin{split}\big{|}N_{H^{\prime}}(S^{\prime})\big{|}&=\sum_{i\in
N_{H}(S)}n_{i}\geq(1-\tfrac{2}{5}\gamma)\tfrac{t}{2}\big{|}N_{H}(S)\big{|}\\\
&\geq(1-\tfrac{2}{5}\gamma)(1+\gamma)\tfrac{t}{2}|S|\geq\frac{1-\tfrac{2}{5}\gamma}{1+\tfrac{2}{5}\gamma}(1+\gamma)|S^{\prime}|\geq|S^{\prime}|\,,\end{split}$

where the last inequality uses $\gamma\leq\frac{1}{2}$. Thus by Theorem 3.2
there is a perfect $2$-matching $\mathcal{M}$ in $H^{\prime}$. For $e=ij\in
E(H)$, recall that $W_{i}\times W_{j}$ is the blow-up of this edge in
$H^{\prime}$. Now set $t^{\prime\prime}_{e}:=\sum_{f\in W_{i}\times
W_{j}}\omega(f)$, where $\omega(f)=2$ if $e$ is on an edge of $\mathcal{M}$,
$\omega(f)=1$ if $e$ is on a cycle of $\mathcal{M}$, and $\omega(e)=0$
otherwise. We have

$\sum_{e\in E_{i}}t^{\prime\prime}_{e}=\sum_{ij\in E_{i}}\sum_{f\in
W_{i}\times W_{j}}\omega(f)=\sum_{w\in W_{i}}\sum_{f\in E(H^{\prime})\colon
w\in f}\omega(f)=n_{i}\cdot 2\,,$

where the last equality uses that $|W_{i}|=n_{i}$, the definition of $\omega$
and the fact that $\mathcal{M}$ is a perfect $2$-matching. Thus we obtain
(7.2), as required. ∎

##  8\. Extremal cases: The proof of Lemma 4.4

For the proof of Lemma 4.4 it is natural to distinguish two cases
corresponding to the two cases in the definition of extremal colourings. For
both cases we choose

${1}/{n}\ll\varepsilon,1/m\ll d\ll\gamma\ll\beta\,,$

suitable for various estimates and we suppose $G$ is a graph on $n$ vertices
with minimum degree $\delta(G)\geq(2/3+\beta)n$ whose edges are coloured with
red and blue, and with a coloured $(\varepsilon,d)$-reduced multi-graph
$\mathcal{G}$ on $m$ vertices corresponding to an $(\varepsilon,d)$-regular
partition $\mathcal{V}=\\{V_{1},\dots,V_{m}\\}$ of $G$ with exceptional set
$V_{0}$. By (3.3) we have

$\delta(\mathcal{G})\geq(2/3+\beta/2)m\,.$

Further, we let $G^{\prime}$ be the “cleaned” coloured subgraph of $G$ on
vertex set ${V(G)\setminus V_{0}}$ corresponding to the
$(\varepsilon,d)$-reduced graph $\mathcal{G}$ with properties as guaranteed by
Lemma 3.8: In particular, each red (blue) edge of $G^{\prime}$ is in some pair
$(V_{i},V_{j})$ such that $ij$ is a red (blue) edge of $\mathcal{G}$. Further,
let $G^{\prime\prime}$ be the spanning subgraph of $G$ which coincides with
$G^{\prime}$ on $V(G)\setminus V_{0}$ and has all $G$-edges incident to
vertices in $V_{0}$. Clearly,

$\delta(G^{\prime}),\delta(G^{\prime\prime})\geq(2/3+\beta-2d-\varepsilon)n\geq(2/3+\beta/2)n\,.$

###  8.1. Case 1: A colouring as in Definition 4.1() ‣ 4.1

We start with the case that the coloured reduced multi-graph has one spanning
bipartite connected red component, and exactly two blue components and these
are bipartite as well and do not admit bridges.

###### Proof of Lemma 4.4 when $\mathcal{G}$ has a colouring as in Definition
4.1() ‣ 4.1.

Let $R$ be the spanning, red say, bipartite component of $\mathcal{G}$ with
bipartition classes $\mathcal{X}_{R}$ and $\mathcal{Y}_{R}$. As the colouring
is $(4\gamma)$-extremal we have
$\left||\mathcal{X}_{R}|-|\mathcal{Y}_{R}|\right|\leq 4\gamma m$ and hence

(8.1) $m/2-4\gamma m\leq|\mathcal{X}_{R}|,|\mathcal{Y}_{R}|\leq m/2+4\gamma
m.$

Set $X_{{R}}:=\bigcup_{i\in\mathcal{X}_{{R}}}V_{i}$ and
$Y_{{R}}:=\bigcup_{i\in\mathcal{Y}_{{R}}}V_{i}$. In particular, any vertex $x$
in $X_{R}$ (in $Y_{R}$, respectively) sends red edges in $G^{\prime}$ only to
vertices in $Y_{R}$ (in $X_{R}$, respectively) and blue edges in $G^{\prime}$
only to vertices in $X_{R}$ (in $Y_{R}$, respectively). Let $B_{j}$ with
$j=1,2$ be the bipartite blue components of $\mathcal{G}$ with bipartition
classes $\mathcal{X}_{B_{j}},\mathcal{Y}_{B_{j}}$. Suppose that
$V(B_{1})=\mathcal{X}_{R}$ and $V(B_{2})=\mathcal{Y}_{R}$. Let
$X_{{B_{j}}}:=\bigcup_{i\in\mathcal{X}_{{B_{j}}}}V_{i}$ and
$Y_{{B_{j}}}:=\bigcup_{i\in\mathcal{Y}_{{B_{j}}}}V_{i}$ for $j=1,2$. Thus
$\\{X_{B_{1}},Y_{B_{1}}\\}$ is a partition of $X_{R}$ and
$\\{X_{B_{2}},Y_{B_{2}}\\}$ is a partition of $Y_{R}$.

Let us next estimate the sizes of the $\mathcal{X}_{B_{j}}$,
$\mathcal{Y}_{B_{j}}$. By (8.1), we have

$\deg_{G^{\prime}_{\text{blue}}}(x,\mathcal{X}_{R}),\deg_{G^{\prime}_{\text{blue}}}(y,\mathcal{X}_{R})\geq(1/6+4\gamma)m$

for any $x,y\in\mathcal{X}_{R}$. If $xy$ is additionally a (blue) edge, then
bipartiteness implies $N_{G^{\prime}_{\text{blue}}}(x,\mathcal{X}_{R})\cap
N_{G^{\prime}_{\text{blue}}}(y,\mathcal{X}_{R})=\emptyset$ and hence

(8.2)
$|\mathcal{X}_{B_{1}}|,|\mathcal{Y}_{B_{1}}|\leq|\mathcal{X}_{R}|-(1/6+4\gamma)m\overset{\eqref{equ:|X|=|Y|}}{\leq}m/3.$

By symmetry we also have $|\mathcal{X}_{B_{2}}|,|\mathcal{Y}_{B_{2}}|\leq
m/3$. We conclude for $j=1,2$ that

(8.3) $|X_{B_{j}}|,|Y_{B_{j}}|\leq n/3\,.$

We next distribute the exceptional vertices in $V_{0}$ as follows. We let

$\displaystyle X_{{R}}^{\prime}$ $\displaystyle=\\{v\in
V(G)\colon\deg_{G^{\prime\prime}_{\text{blue}}}(v,Y_{{R}})\leq\tfrac{1}{10}\beta
n\\},$ $\displaystyle Y_{{R}}^{\prime}$ $\displaystyle=\\{v\in
V(G)\colon\deg_{G^{\prime\prime}_{\text{blue}}}(v,X_{{R}})\leq\tfrac{1}{10}\beta
n\\}.$

Clearly, $X_{R}\subseteq X_{R}^{\prime}$ since vertices in $X_{R}$ send no
blue edges to $Y_{R}$ in $G^{\prime}$ (and hence in $G^{\prime\prime}$);
analogously, $Y_{R}\subseteq Y_{R}^{\prime}$. By (8.1) this implies

(8.4) $n/2-5\gamma n\leq|X^{\prime}_{R}|,|Y^{\prime}_{R}|\leq n/2+5\gamma
n\,.$

Moreover, since by assumption $(B_{1},B_{2})$ does not admit bridges,
$V(G)\setminus(X_{{R}}^{\prime}\cup Y_{{R}}^{\prime})$ contains at most one
vertex; call this vertex $z^{*}$ if it exists, and otherwise we say $z^{*}$
does not exist.

Without loss of generality suppose that
$|X_{{R}}^{\prime}|\geq|Y_{{R}}^{\prime}|$. Our goal is to use two blue cycles
to cover $|X_{R}^{\prime}|-|Y_{R}^{\prime}|$ vertices in $X_{R}^{\prime}$ and
the vertex $z^{*}$, and to use a red cycle to cover all remaining vertices. We
now prepare for this be establishing some further degree bounds. By
definition, any $x\in X^{\prime}_{R}$ and $y\in Y^{\prime}_{R}$ satisfy

(8.5)
$\begin{split}\deg_{G^{\prime\prime}_{\text{red}}}(x,Y^{\prime}_{R})&\geq(\tfrac{2}{3}+\tfrac{1}{2}\beta)n-|X^{\prime}_{R}|-\tfrac{1}{10}\beta
n-1\\\
&\geq(\tfrac{2}{3}+\tfrac{1}{2}\beta)n-(\tfrac{1}{2}+5\gamma)n-\tfrac{1}{10}\beta
n-1\geq(\tfrac{1}{6}+\tfrac{1}{4}\beta)n\,,\\\
\deg_{G^{\prime\prime}_{\text{red}}}(y,X^{\prime}_{R})&\geq(\tfrac{1}{6}+\tfrac{1}{4}\beta)n\,.\end{split}$

For $x\in X_{R}$ and $y\in Y_{R}$ we know even more: The vertex $x$ is either
in $X_{B_{1}}$ or in $Y_{B_{1}}$. In the former (latter) case it sends all its
$G^{\prime\prime}$-edges in $X_{R}$ to $Y_{B_{1}}$ (to $X_{B_{1}}$). This
together with (8.3) (and an analogous argument for $y$) gives

(8.6)
$\begin{split}\deg_{G^{\prime\prime}_{\text{red}}}(x,Y^{\prime}_{R})&\geq(\tfrac{2}{3}+\tfrac{1}{2}\beta)n-|Y_{B_{1}}|-|V_{0}|-\tfrac{1}{10}\beta
n-1\\\ &\geq(\tfrac{1}{3}+\tfrac{1}{4}\beta)n\,.\\\
\deg_{G^{\prime\prime}_{\text{red}}}(y,X^{\prime}_{R})&\geq(\tfrac{1}{3}+\tfrac{1}{4}\beta)n\,.\end{split}$

Concerning blue edges incident to $x\in X_{R}$ and $y\in Y_{R}$ we know

(8.7)
$\deg_{G^{\prime}_{\text{blue}}}(x,X_{R})\geq(\tfrac{2}{3}+\tfrac{1}{2}\beta)n-|Y_{R}|-|V_{0}|\geq(\tfrac{1}{6}+\tfrac{1}{4}\beta)n\,.$

Let us now construct our three cycles. We first construct a blue cycle $C_{2}$
with $V(C_{2})\subseteq X_{R}$, of length

$2\ell=2\lceil(|X_{{R}}^{\prime}|-|Y_{{R}}^{\prime}|)/2\rceil\leq 10\gamma
n+1\leq 11\gamma n\,.$

For this, observe that the blue bipartite graph
$F=G^{\prime}_{\text{blue}}[X_{B_{1}},Y_{B_{1}}]$ has partition classes of
size at most $n/3$ by (8.3) and minimum degree at least
$(\frac{1}{6}+\frac{1}{4}\beta)n$ by (8.7). Hence, picking an arbitrary vertex
$x\in X_{B_{1}}$ we can greedily construct two paths $P_{1}$, $P_{2}$ with
$\ell-1$ edges starting in $x$ which are otherwise vertex-disjoint. Let
$y_{1}$ be the endpoint of $P_{1}$ and $y_{2}$ the endpoint of $P_{2}$.
Clearly, $y_{1}$ and $y_{2}$ are in the same partition class of $F$ and thus
have a common neighbour $x^{\prime}$ in $V(F)\setminus\big{(}V(P_{1})\cup
V(P_{2})\big{)}$ since $\gamma\ll\beta$. Thus, $P_{1}$, $P_{2}$ and
$x^{\prime}$ give the desired blue cycle $C_{2}$ on $2\ell$ vertices.

Our second cycle is also blue, and takes care of parity and the vertex $z^{*}$
if it exists. If $|X_{{R}}^{\prime}\setminus
V(C_{2})|=|Y_{{R}}^{\prime}\setminus V(C_{2})|$, we set $C_{3}:=z^{*}$ (a one-
vertex cycle) if $z^{*}$ exists, and if $z^{*}$ does not exist we let $C_{3}$
be the zero-vertex cycle. If $|X_{{R}}^{\prime}\setminus
V(C_{2})|=|Y_{{R}}^{\prime}\setminus V(C_{2})|+1$ and $z^{*}$ exists, then we
choose $y\in X^{\prime}_{R}\setminus V(C_{2})$ such that $yz^{*}$ is a blue
edge (which exists by definition of $z^{*}$) and let $C_{3}$ be the $2$-vertex
blue cycle $(y,z^{*})$. Finally if $|X_{{R}}^{\prime}\setminus
V(C_{2})|=|Y_{{R}}^{\prime}\setminus V(C_{2})|+1$ and $z^{*}$ does not exist,
we choose any $y\in X^{\prime}_{R}\setminus V(C_{2})$ and let $C_{3}$ be the
one-vertex blue cycle $z^{*}$. Hence we have $|X_{{R}}^{\prime}\setminus
V(C_{2}\cup C_{3})|=|Y_{{R}}^{\prime}\setminus V(C_{2}\cup C_{3})|$.

To finish we claim that
$H=G^{\prime\prime}_{\text{red}}[X^{\prime}_{R}\setminus V(C_{2}\cup
C_{3}),Y^{\prime}_{R}\setminus V(C_{2}\cup C_{3})]$ has a Hamilton cycle
$C_{1}$. This follows from Corollary 3.5. Note that the degree conditions are
fulfilled, because $\delta(H)\geq(1/6+\beta/10)n$ by (8.5), and all but at
most $\varepsilon n$ vertices of $H$ have degree at least $(1/3+\beta/10)n$ by
(8.6). ∎

###  8.2. Case 2: A colouring as in Definition 4.1() ‣ 4.1

In the second case, the reduced graph has two red and two blue components, and
there are neither bridges in red nor in blue.

###### Proof of Lemma 4.4 when $\mathcal{G}$ has a colouring as in Definition
4.1() ‣ 4.1.

We denote the red and blue components of the reduced multi-graph $\mathcal{G}$
by $\mathcal{R}_{1},\mathcal{R}_{2}$ and $\mathcal{B}_{1},\mathcal{B}_{2}$ and
suppose that there are no red or blue bridges. We set
$\mathcal{I}_{i,j}=V(\mathcal{R}_{i})\cap V(\mathcal{B}_{j})$ for $i,j\in[2]$.
We may assume that all but at most $\sqrt{\gamma}m$ vertices
$\mathcal{Q}_{i,j}\subseteq V(\mathcal{R}_{i})\cap V(\mathcal{B}_{i})$ have
more than $\sqrt{\gamma}m$ red neighbours in $V(\mathcal{R}_{i})\cap
V(\mathcal{B}_{i})$ if $i=j$ and more than $\sqrt{\gamma}m$ blue neighbours
otherwise. Let
$I_{i,j}=\bigcup_{x\in\mathcal{I}_{i,j}\setminus\mathcal{Q}_{i,j}}V_{x}$ for
$i,j\in[2]$ and
$V_{0}^{\prime}=V_{0}\cup\bigcup_{x\in\mathcal{Q}_{i,j}}V_{x}$. We have

(8.8) $\displaystyle(1/4-{5\sqrt{\gamma}})n$
$\displaystyle\overset{}{\leq}(1-\varepsilon)|\mathcal{I}_{i,j}|{n}/{m}\overset{}{\leq}|I_{i,j}|\overset{}{\leq}|\mathcal{I}_{i,j}|{n}/{m}\leq({1}/{4}+{5\sqrt{\gamma}})n,$
(8.9) $\displaystyle|V_{0}^{\prime}|$
$\displaystyle\leq|V_{0}|+4|\mathcal{Q}_{i,j}|n/m\leq\varepsilon
n+4\sqrt{\gamma}n\leq 5\sqrt{\gamma}n.$

For $i,j\in[2]$ and any vertex $v\in I_{i,j}$, all $G^{\prime}$-neighbours of
$v$ in $I_{3-i,j}$ are blue, all $G^{\prime}$-neighbours of $v$ in $I_{i,3-j}$
are red, $v$ has no $G^{\prime}$-neighbours in $I_{3-j,3-j}$, and all
$G^{\prime}$-neighbours of $v$ in $I_{i,j}$ are blue if $i=j$ and red
otherwise. This implies the following neighbourhood profiles of vertices in
$\bigcup_{i,j\in[2]}I_{i,j}$.

######  Claim 8.1.

For each $i,j\in[2]$, every vertex $v\in I_{i,j}$ we have

$\displaystyle\deg_{G^{\prime}_{\text{blue}}}(v,I_{3-i,j})$
$\displaystyle\geq(1/6+\beta/2)n\,,$
$\displaystyle\deg_{G^{\prime}_{\text{red}}}(v,I_{i,3-j})$
$\displaystyle\geq(1/6+\beta/2)n\,,$
$\displaystyle\deg_{G^{\prime}_{c}}(v,I_{i,j})$
$\displaystyle\geq(1/6+\beta/2)n\,,$

where $c$ is blue if $i=j$, and $c$ is red otherwise.

###### Proof.

We will show the third part for a vertex $v\in I_{1,1}$. The other cases
follow by analogous arguments. By (8.9), all but $|V_{0}^{\prime}|\leq
5\sqrt{\gamma}n$ vertices of $G$ are covered by $\bigcup_{i,j\in[2]}I_{i,j}$.
Suppose that $v\in V_{x}$ for some
$x\in\mathcal{I}_{i,j}\setminus\mathcal{Q}_{1,1}$. By definition of
$\mathcal{Q}_{1,1}$, it follows that
$|N_{\mathcal{G}_{\text{red}}}(x)\cap\mathcal{I}_{1,1}|\leq\sqrt{\gamma}n$.
Moreover, we have $|V_{y}|\leq n/m$ for each $y\in\mathcal{I}_{1,1}$. This and
(8.8) implies that

$\displaystyle\deg_{G^{\prime}_{\text{blue}}}(v,I_{1,1})$
$\displaystyle=(2/3+\beta)n-|I_{1,2}|-|I_{2,1}|-5\sqrt{\gamma}n-\sqrt{\gamma}m\cdot
n/m$ ∎ $\displaystyle\geq(1/6+\beta/2)n\,.$

Note that since $(\mathcal{R}_{1},\mathcal{R}_{2})$ does not admit red or blue
bridges, there is at most one vertex $x_{\text{red}}^{*}\in V_{0}^{\prime}$
with $dn$ red $G^{\prime\prime}$-neighbours in $I_{1,1}\cup I_{1,2}$ and $dn$
red $G^{\prime\prime}$-neighbours in $I_{2,1}\cup I_{2,2}$. If there is no
such vertex, we say $x_{\text{red}}^{*}$ does not exist. Similarly, there is
at most one vertex $x_{\text{blue}}^{*}\in V_{0}^{\prime}$ with $dn$ blue
$G^{\prime\prime}$-neighbours in $I_{1,1}\cup I_{2,1}$ and $dn$ blue
$G^{\prime\prime}$-neighbours in $I_{1,2}\cup I_{2,2}$, and if there is no
such vertex we say $x_{\text{blue}}^{*}$ does not exist. Let $X^{*}$ be the
set containing the existing vertices among $x^{*}_{\text{red}}$ and
$x^{*}_{\text{blue}}$ (so $0\leq|X^{*}|\leq 2$).

We shall next distribute the exceptional vertices in $V_{0}^{\prime}$.

######  Claim 8.2.

We can partition the vertices of $V_{0}^{\prime}\setminus X^{*}$ into sets
$\\{I_{i,j}^{\prime}\\}_{i,j\in[2]}$ (of size at most $5\sqrt{\gamma}n$) such
that every $v\in I_{i,j}^{\prime}$ satisfies

$\deg_{G^{\prime\prime}_{\text{blue}}}(v,I_{3-i,j})\geq({1}/{6}+\beta/2)n\,,\qquad\deg_{G^{\prime\prime}_{\text{red}}}(v,I_{i,3-j})\geq({1}/{6}+\beta/2)n\,.$

###### Proof.

Let $v\in V_{0}^{\prime}\setminus X^{*}$. Suppose that $v$ has at least $2dn$
neighbours in each $I_{i,j}$ with $i,j\in[2]$, so that $v$ sends at least $dn$
edges in one or the other (or possibly both) colours to each $I_{i,j}$. If
there are three or more $I_{i,j}$ such that $v$ has $dn$ or more red
neighbours in each, then by definition we would have $v\in X^{*}$; the same
holds for three or more $I_{i,j}$ such that $v$ has $dn$ or more red
neighbours in each. It follows that there are some two $I_{i,j}$ to which $v$
sends less than $dn$ red edges, and because $v$ is not in $X^{*}$ these two
sets come from a blue component, namely they are $I_{1,j}$ and $I_{2,j}$ for
some $j\in[2]$. Now $v$ must send more than $dn$ red edges to each of the sets
$I_{1,3-j}$ and $I_{2,3-j}$. But these two sets are in different red
components, so $v\in X^{*}$. This contradiction shows that there are
$i,j\in[2]$, such that $\deg(v,I_{i,j})<2dn$. Moreover, all but
$|V_{0}^{\prime}|\leq 5\sqrt{\gamma}n$ vertices are covered by
$\bigcup_{i,j\in[2]}I_{i,j}$. By (8.8), this implies that $v$ has at least

$(2/3+\beta)n-2(1/4+{5\sqrt{\gamma})n-2dn-5\sqrt{\gamma}n}\geq({1}/{6}+\beta/2)n$

neighbours in each of $I_{3-i,j}$ and $I_{i,3-j}$. As $v\notin X^{*}$, we
cannot have that $v$ sends $dn$ red edges to both $I_{i,3-j}$ and $I_{3-i,j}$,
nor at least $dn$ blue edges to both. Thus all but at most $dn$ edges from $v$
to $I_{i,3-j}$ are of one colour, and all but at most $dn$ edges from $v$ to
$I_{3-i,j}$ are of the other colour, and we can add $v$ either to
$I_{i,j}^{\prime}$ or to $I_{3-i,3-j}^{\prime}$. ∎

Now set $J_{i,j}=I_{i,j}\cup I_{i,j}^{\prime}$ for $i,j\in[2]$. Note that by
definition the sets $J_{i,j}$, together with $X^{*}$, partition the vertices
of $G$. Observe that by (8.8) and Claim 8.2 we have

(8.10)
$(1/4-5\sqrt{\gamma})n\leq|J_{i,j}|=|I_{i,j}|+|I_{i,j}^{\prime}|\leq(1/4+5\sqrt{\gamma})n+5\sqrt{\gamma}n\leq(1/4+10\sqrt{\gamma})n\,.$

Suppose $|J_{1,1}|\geq|J_{2,1}|$. Then either we find a partition of $V(G)$
into three cycles, or $G$ has one of two rather special structures. This
claim, together with a short case distinction, is enough for Case 2: the claim
(with sets $J_{i,j}$ and colours changed appropriately) applies equally if
$|J_{2,1}|\geq|J_{2,2}|$, and so on; and we will argue that in at least one of
these four situations we do find the cycle partition. Let us now state
precisely what structural information we obtain.

######  Claim 8.3.

Suppose $|J_{1,1}|\geq|J_{2,1}|$. Then one of the following three statements
holds.

  1. (i)

There are three cycles in $G$, two blue and one red, whose vertex sets
partition $V(G)$.

  2. (ii)

$x_{\text{red}}^{*}$ exists and has less than $\tfrac{1}{2}dn$ neighbours in
$J_{1,2}$, and $|J_{1,1}|=|J_{2,1}|$.

  3. (iii)

$x_{\text{red}}^{*}$ exists and has less than $\tfrac{1}{2}dn$ neighbours in
$J_{1,2}$, and $|J_{1,1}|=|J_{2,1}|+1$, and either $x_{\text{blue}}^{*}$ does
not exist or it exists and has less than $\tfrac{1}{2}dn$ blue neighbours in
$J_{2,1}$.

Before we prove this claim, we explain why it is enough to complete the proof
of Case 2 of Lemma 4.4. To begin with, we may suppose without loss of
generality that $J_{1,1}$ is of maximum size among the $J_{i,j}$. Then Claim
8.3 (as written above) applies. Either we are done, or $G$ has one of the
structures described in (ii) and (iii) above. We distinguish these two
separate cases. Note that in both situations $x_{\text{red}}^{*}$ exists and
has less than $\tfrac{1}{2}dn$ neighbours in $J_{1,2}$. We will only need to
use the extra structure given by (iii) at this point; within the following two
cases, when we apply Claim 8.3 we will simply conclude that either we obtain a
cycle partition, or the two sets differ in size by at most one and
$x_{\text{red}}^{*}$ exists and has less than $\tfrac{1}{2}dn$ neighbours in
$J_{1,2}$.

Case 2.1: Suppose $x_{\text{red}}^{*}$ exists and has less than
$\tfrac{1}{2}dn$ neighbours in $J_{1,2}$, and $|J_{1,1}|=|J_{2,1}|$. Because
$J_{1,1}$ is maximum size, we have $|J_{2,1}|\geq|J_{2,2}|$. This means we can
again apply Claim 8.3. Either we obtain the desired cycle partition, or
$|J_{2,1}|=|J_{2,2}|$, or $|J_{2,1}|=|J_{2,2}|+1$. Either way, we have that
$x_{\text{blue}}^{*}$ exists and has less than $\tfrac{1}{2}dn$ neighbours in
$J_{2,2}$. If $|J_{2,2}|\geq|J_{1,2}|$ we can yet again apply Claim 8.3, and
it necessarily returns a partition into three cycles, since otherwise
$x_{\text{red}}^{*}$ must have less than $\tfrac{1}{2}dn$ neighbours in both
$J_{1,2}$ and $J_{2,1}$, which violates the minimum degree condition of $G$.
We have $|J_{2,2}|\geq|J_{1,2}|$ except when
$|J_{2,1}|-1=|J_{2,2}|=|J_{1,2}|-1$, so it remains to consider this final
possibility. In this case we have $|J_{1,2}|\geq|J_{1,1}|$ (in fact, with
equality). That means we can yet again apply Claim 8.3. Again it necessarily
returns the desired partition into three cycles since otherwise we are told
that $x_{\text{blue}}^{*}$ has less than $\tfrac{1}{2}dn$ neighbours in
$J_{2,2}$. Since we already know it has less than $\tfrac{1}{2}dn$ neighbours
in $J_{1,1}$ this violates the minimum degree condition of $G$.

Case 2.2: Suppose that $x_{\text{red}}^{*}$ exists and has less than
$\tfrac{1}{2}dn$ neighbours in $J_{1,2}$, and $|J_{1,1}|=|J_{2,1}|+1$, and
either $x_{\text{blue}}^{*}$ does not exist or it does exist and has fewer
than $\tfrac{1}{2}dn$ blue neighbours in $J_{2,1}$. If $x_{\text{blue}}^{*}$
exists, then it links $B_{1}$ and $B_{2}$ in blue, so it must have at least
$\tfrac{1}{2}dn$ blue neighbours in $J_{1,1}$. The point is that either
$x_{\text{blue}}^{*}$ does not exist, or it does but has at least
$\tfrac{1}{2}dn$ neighbours in $J_{1,1}$. This means that if
$|J_{2,1}|\geq|J_{2,2}|$, then Claim 8.3 necessarily returns the desired
three-cycle partition and we are done. Thus we have $|J_{2,1}|<|J_{2,2}|$, and
this is only possible if $|J_{2,2}|=|J_{1,1}|$. So $J_{2,2}$ is of maximum
size, and we have $|J_{2,2}|\geq|J_{1,2}|$, which is what we need to apply
Claim 8.3. As in Case 1, we must obtain a three-cycle partition, since
otherwise $x_{\text{red}}^{*}$ violates the minimum degree condition on $G$.

What remains to do is to show that Claim 8.3 holds. There are a few ways we
might obtain the required cycle decomposition; in any case, the first thing we
need to do is construct a suitable red cycle, and the following claim provides
several possibilities for this.

######  Claim 8.4.

The following three types of red cycle $C_{\text{red}}$ are in $G$.

  * •

$C_{\text{red}}$ is contained in $J_{1,2}$.

  * •

if $x_{\text{red}}^{*}$ has at least $\tfrac{1}{4}dn$ red neighbours in
$J_{1,2}$, then $C_{\text{red}}$ contains $x_{\text{red}}^{*}$ and its
remaining vertices are in $J_{1,2}$.

  * •

if $x_{\text{red}}^{*}$ has at least $\tfrac{1}{4}dn$ red neighbours in
$J_{1,1}$, then $C_{\text{red}}$ contains $x_{\text{red}}^{*}$, two vertices
of $J_{1,1}$, and its remaining vertices are in $J_{1,2}$.

Furthermore, in each case we have $|V(C_{\text{red}})|\leq 20\sqrt{\gamma}n$,
$\big{|}J_{1,2}\setminus V(C_{\text{red}})\big{|}\leq|J_{2,2}|-2$.
Additionally, for each $c\in\\{\text{red},\text{blue}\\}$, if $x_{c}^{*}$
exists and has more than $100$ blue-neighbours in $J_{1,2}$, then
$V(C_{\text{red}})$ covers at most half of the blue-neighbours of $x_{c}^{*}$
in $J_{1,2}$.

###### Proof.

For the first type of cycle, we pick an edge $uu^{\prime}$ in $I_{1,2}$ and
let $P$ be the path $(u,u^{\prime})$. For the second, we choose two distinct
red neighbours $u,u^{\prime}$ in $I_{1,2}$ of $x_{\text{red}}^{*}$ and let
$P=(u,x_{\text{red}}^{*},u^{\prime})$. For the third, we pick two distinct red
neighbours $v,v^{\prime}$ of $x_{\text{red}}^{*}$ in $I_{1,1}$, let $u$ be a
red-neighbour of $v$ in $I_{1,2}$, and $u^{\prime}\neq u$ be a red-neighbour
of $v^{\prime}$ in $I_{1,2}$, and set
$P=(u,v,x_{\text{red}}^{*},v^{\prime},u^{\prime})$. In each case, we have a
path $P$ on at most five vertices whose ends are in $I_{1,2}$.

We now extend $P$ to the desired cycle $C_{\text{red}}$ as follows. We first
let $S^{*}$ be a vertex set containing $V(P)$, together with some other
vertices as follows. For each $c\in\\{\text{red},\text{blue}\\}$, if
$x_{c}^{*}$ has between $100$ and $\tfrac{n}{1000}$ blue-neighbours in
$J_{1,2}$, we add an arbitrary half of them, not contained in $P$, to $S^{*}$;
this is possible since $P$ contains at most five vertices. In total we have
$|S^{*}|\leq 2\tfrac{n}{2000}+9<\tfrac{n}{100}$. We let
$\ell=\max\big{(}2,2+|J_{1,2}|-|J_{2,2}|\big{)}$. By Claim 8.1 we have
$\deg_{G^{\prime\prime}_{\text{red}}}(u,I_{1,2}),\deg_{G^{\prime\prime}_{\text{red}}}(u,I_{1,2})\geq(1/6+\beta/2)n$.
Since $|I_{1,2}|=(1/4\pm 5\sqrt{\gamma})n$ by (8.8), this implies that $u$ and
$u^{\prime}$ have a common neighbour $u_{1}$ in
$I_{1,2}\setminus(S^{*}\cup\\{u,u^{\prime}\\}$, hence we get a path
$u,u_{1},u^{\prime}$ of length $\ell=2$. We can then repeat this argument to
get a common neighbour $u_{2}$ of $u_{1}$ and $u^{\prime}$ in
$I_{1,2}\setminus\big{(}S^{*}\cup\\{u\\}\big{)}$ and hence a path
$u,u_{1},u_{2},u^{\prime}$ of length $\ell=3$, and so on. In general we thus
obtain a path $u,u_{1},\dots,u_{\ell-1},u^{\prime}$ of length $\ell$ by
extending the path of length $\ell-1$ by finding a common neighbour
$u_{\ell-1}$ of $u_{\ell-2}$ and $u^{\prime}$ in
$I_{1,2}\setminus\big{(}S^{*}\cup\\{u,u_{1},\dots,u_{\ell-3}\\}\big{)}$, which
we certainly can do since by (8.10) the difference in size between $J_{1,2}$
and $J_{2,2}$ is at most $15\sqrt{\gamma}n$, so $\ell\leq{17\sqrt{\gamma}n}$.

We claim this $C_{\text{red}}$ has all the required properties. What remains
to check is that $|V(C_{\text{red}})|\leq{20\sqrt{\gamma}n}$, that
$\big{|}J_{1,2}\setminus V(C_{\text{red}})\big{|}\leq|J_{2,2}|-2$, and that it
does not cover too many blue-neighbours of the vertices of $X^{*}$. The first
two of these follow by definition of $\ell$. So we need to check
$C_{\text{red}}$ does not cover too many blue-neighbours of the vertices of
$X^{*}$. If $x_{c}^{*}\in X^{*}$ has less than $100$ blue-neighbours in
$J_{1,2}$, there is nothing to check. If $x_{c}^{*}$ has between $100$ and
$\tfrac{n}{1000}$ blue-neighbours in $J_{1,2}$, then at least half are in
$S^{*}\setminus V(P)$ and hence not covered by $C_{\text{red}}$ as desired. If
$x_{c}^{*}$ has more than $\tfrac{n}{1000}$ blue-neighbours in $J_{1,2}$, then
at most $|V(C_{\text{red}})|\leq{20\sqrt{\gamma}n}$ are covered by
$C_{\text{red}}$, which is less than half as desired. ∎

Next, we need to construct the two blue cycles covering the vertices left over
after $C_{\text{red}}$ is constructed. We need one cycle contained in
$J_{1,1}\cup J_{2,1}\cup X^{*}$ and another in $J_{1,2}\cup J_{2,2}\cup
X^{*}$. These two sets satisfy the same conditions, and the following lemma
applies to both (though we state it for $J_{1,1}\cup J_{2,1}\cup X^{*}$).
Since at this point $C_{\text{red}}$ is not fixed (Claim 8.4 above gives
several possible constructions) we simply avoid a vertex set $S$ of size at
most ${20\sqrt{\gamma}n}$.

######  Claim 8.5.

Let $S$ be a set of at most ${20\sqrt{\gamma}n}$ vertices. Choose any
(possibly empty) disjoint subsets $A,B\subseteq X^{*}\setminus S$ with the
following property: $x_{c}^{*}$ may only be in $A$ if it has at least
$\tfrac{1}{8}dn$ blue-neighbours in $J_{2,1}\setminus S$, and $x_{c}^{*}$ may
only be in $B$ if it has at least $\tfrac{1}{8}dn$ blue-neighbours in
$J_{1,1}\setminus S$. Suppose that

$\big{|}A\cup J_{1,1}\setminus S\big{|}\geq\big{|}B\cup J_{2,1}\setminus
S\big{|}\,.$

Then there is a blue cycle in $G$ whose vertex set is $\big{(}A\cup B\cup
J_{1,1}\cup J_{2,1}\big{)}\setminus S$.

###### Proof.

We begin by constructing disjoint blue paths outside $S$ greedily as follows.
Given a vertex $x$ of $A$, choose two blue-neighbours in $I_{2,1}\setminus S$,
giving a three-vertex blue path containing $x$ with ends in $I_{2,1}\setminus
S$; extend this to a five-vertex blue path with ends in $I_{1,1}\setminus S$
by choosing blue neighbours in $I_{1,1}\setminus S$. This is possible by the
condition on $A$, since $|J_{i,j}|\leq|I_{i,j}|+{5\sqrt{\gamma}n}$, and by
Claim 8.1. Given a vertex $x$ of $B$, we create a three-vertex blue path
containing $x$ with ends in $I_{1,1}\setminus S$ by simply choosing two blue-
neighbours of $x$ in $I_{1,1}\setminus S$. Observe that at each step we have
more than $10$ choices for the next vertex to pick; since $|A\cup B|\leq 2$
the paths we construct have in total at most $10$ vertices, so we can perform
the construction vertex-disjointly.

At this point we have $|A\cup B|$ disjoint blue paths with ends in
$I_{1,1}\setminus S$. If this is zero paths, choose a blue edge $uu^{\prime}$
from $I_{1,1}\setminus S$ to $I_{2,1}\setminus S$ and let $P=(u,u^{\prime})$.
If it is one path, let $u$ be one end and let $u^{\prime}$ be a blue-neighbour
in $I_{2,1}\setminus S$ not used on the path: this gives a blue path $P$ from
$u$ to $u^{\prime}$. If it is two paths, suppose they go from $u$ to $v$ and
$v^{\prime}$ to $v^{\prime\prime}$. Choose a common blue-neighbour $w$ of $v$
and $v^{\prime}$ in $I_{2,1}\setminus S$, and a different blue neighbour
$u^{\prime}$ of $v^{\prime\prime}$ in $I_{2,1}\setminus S$, which are not used
on the paths: this gives a blue path $P$ from $u$ to $u^{\prime}$. Each of
these constructions is possible by Claim 8.1. In any case, $P$ uses the same
number of vertices in $J_{1,1}\cup A$ as in $J_{2,1}\cup B$.