% !TEX TS-program = pdflatex
% !TEX encoding = UTF-8 Unicode

% This is a simple template for a LaTeX document using the "article" class.
% See "book", "report", "letter" for other types of document.

\documentclass[12pt]{article} % use larger type; default would be 10pt
\usepackage{e-jc}

\synctex=1

\usepackage{amssymb, amsmath, amsthm, xcolor, enumerate}
\usepackage{mathtools}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{fullpage}
\usepackage{hyperref}
\usepackage{microtype}

\usepackage{graphicx}

%%% SECTION TITLE APPEARANCE
%\usepackage{sectsty}
%\allsectionsfont{\sffamily\mdseries}

%%% ToC (table of contents) APPEARANCE
%\usepackage[nottoc,notlof,notlot]{tocbibind} % Put the bibliography in the ToC
%\usepackage[titles,subfigure]{tocloft} % Alter the style of the Table of Contents
%\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
%\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % No bold!
\usepackage{enumerate}

\newcommand{\eps}{\varepsilon}
\newcommand{\NN}{\mathbb N}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{obsv}{Observation}
%\newtheorem{prop}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
%\newtheorem*{sk}{High-level Sketch}
%\newtheorem{conj}[theorem]{Conjecture}
%\theoremstyle{definition}
%\newtheorem{rmk}[theorem]{Remark}
\newtheorem{definition}{Definition}

\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}

\newcommand{\parag}[1]{\vskip\baselineskip\noindent\textbf{#1}\hskip1em}

\title{\textbf{Stability for vertex cycle covers}}

\author{
    J\'ozsef Balogh\thanks{Research is partially supported by Simons Fellowship, NSF
    CAREER Grant DMS-0745185, Marie Curie FP7-PEOPLE-2012-IIF 327763.}\\
    \small Department of Mathematical Sciences\\[-0.8ex]
    \small University of Illinois at Urbana-Champaign\\[-0.8ex]
    \small Urbana, Illinois 61801, USA\\[-0.8ex]
    \small\tt jobal@math.uiuc.edu\\
    \and
    Frank Mousset\thanks{Supported by grant no.\ 6910960 of the Fonds National de la Recherche, Luxembourg.}\\
    \small Institute of Theoretical Computer Science\\[-0.8ex]
    \small ETH Z\"urich\\[-0.8ex]
    \small 8092 Z\"urich, Switzerland\\[-0.8ex]
    \small\tt frank.mousset@inf.ethz.ch\\
    \and
    Jozef Skokan\\
    \small Department of Mathematics\\[-0.8ex]
    \small London School of Economics\\[-0.8ex]
    \small Houghton Street, London, WC2A 2AE, England\\[-0.8ex]
    \small and\\[-0.8ex]
    \small Department of Mathematical Sciences\\[-0.8ex]
    \small University of Illinois at Urbana-Champaign\\[-0.8ex]
    \small Urbana, Illinois 61801, USA\\[-0.8ex]
\small\tt jozef@member.ams.org}

\date{\small \today\\
\small Mathematics Subject Classifications: 05C35, 05C38, 05C75}

\begin{document}

\maketitle

\thispagestyle{empty}

\clearpage
\begin{abstract}
In 1996 Kouider and Lonc proved the following natural generalization of Dirac's
Theorem: for any integer $k\geq 2$, if $G$ is an $n$-vertex graph with
minimum degree at least $n/k$, then there are $k-1$ cycles in $G$ that
together cover all the vertices. 

This is tight in the sense that there are $n$-vertex graphs that
have minimum degree $n/k-1$ and that do not contain $k-1$ cycles with
this property. A concrete example is given by $I_{n,k} =
K_n\setminus K_{(k-1)n/k+1}$ (an edge-maximal graph on $n$ vertices with an
independent set of size $(k-1)n/k+1$). This graph has minimum degree
$n/k-1$ and cannot be covered
with fewer than $k$ cycles. More generally, given positive integers
$k_1,\dotsc,k_r$ summing to $k$, the disjoint union $I_{k_1n/k,k_1}+ \dotsb
+ I_{k_rn/k,k_r}$ is an $n$-vertex graph with the same properties.

In this paper, we show that there are no extremal examples
that differ substantially from the ones given by this construction. More
precisely, we obtain the following stability result: if a graph $G$
has $n$ vertices and minimum degree \emph{nearly} $n/k$, then it either
contains $k-1$ cycles covering all vertices, or else it must be close
(in `edit distance') to a  subgraph of $I_{k_1n/k,k_1}+ \dotsb +
I_{k_rn/k,k_r}$, for some sequence $k_1,\dotsc,k_r$ of positive integers
that sum to $k$.

Our proof uses Szemer\'edi's Regularity Lemma and the related
machinery.
\end{abstract}

\section{Introduction}

The theorem of Dirac~\cite{Dir1952} saying that any graph $G$ on $n\ge 3$ vertices
with minimum degree at least $n/2$ contains a Hamilton cycle is one of the
classical results of graph theory. There is a rich collection of extensions of
this theorem in various directions. One possibility to replace the Hamilton
cycle with another spanning subgraph and ask what minimum degree guarantees its
existence. 

For example, Bollob\'as~\cite{Bol1978} conjectured that for $c>1/2$ and
$\Delta>0$, every sufficiently large $n$-vertex graph $G$ with minimum degree
at least $cn$ contains every spanning tree of maximum degree at most $\Delta$.
The proof of this conjecture was given by Koml\'os, S\'ark\"ozy and
Szemer\'edi~\cite{KSS1995}, using the regularity method. Another example is the
famous Hajnal-Szemerédi theorem~\cite{HS1970}, saying that every graph on $kn$
vertices with minimum degree $(k-1)n$ contains $n$ vertex-disjoint copies of
$K_k$. Yet another well-known example is the conjecture of P\'osa
\cite{Erd1964} and Seymour \cite{Sey1974} that any $n$-vertex graph with
minimum degree at least $kn/(k+1)$ contains the $k$-th power of a Hamilton
cycle. If true, this would imply both Dirac's theorem and the Hajnal-Szemerédi
theorem. The Pósa-Seymour conjecture was proved for large $n$ by Koml\'os, S\'ark\"ozy, and
Szemer\'edi~\cite{KSS1996a}, \cite{KSS1998}. Later, Levitt, S\'ark\"ozy,
Szemer\'edi \cite{LSS2010} and Chau, DeBiasio, and Kierstead~\cite{CDK2011}
proved the same result with different methods, for smaller values of~$n$. When
we consider the square of a~Hamilton path instead of the square of a Hamilton
cycle, Fan and Kierstead~\cite{FK1996} proved that $(2n-1)/3$ is the optimal
minimum degree for every $n$.

All of these results are about graphs with minimum degree larger than $n/2$.
Indeed, as soon as the minimum degree can be below $n/2$, one loses a lot of
global structure: for example, the graph may no longer be connected. Here we
will explore the direction where the minimum degree can be smaller than $n/2$.
Already Dirac observed that every $2$-connected graph $G$ contains a cycle of
length at least $\min{\{v(G),2\delta(G)\}}$~\cite{Dir1952}. The connectivity
assumption in this result might seem artificial, and indeed several
researchers have looked at the case without this assumption.
Alon~\cite{Alo1986} proved that any $n$-vertex graph $G$ with minimum degree at
least $n/k$ must contain a cycle of length at least $\floor{n/(k-1)}$. Later
Bollob\'as and Häggkvist~\cite{BH1989} proved that such a graph must in fact
contain a cycle of length $\ceil{n/(k-1)}$, which is optimal. An Ore-type
condition for the same problem is considered in~\cite{EM1989}. More recently,
Nikiforov and Schelp~\cite{NS2006} and Allen~\cite{All} have considered the
problem of finding cycles of a specified length in graphs of minimum degree at
least $n/k$.

In 1987 Enomoto, Kaneko and Tuza~\cite{EKT1988} conjectured that any graph $G$
on $n$ vertices with $\delta(G)\geq n/k$ contains a collection of at most $k-1$
cycles that cover all vertices of $G$. Note that in the case $k=2$ this reduces
to Dirac's theorem. Moreover, since at least one of these cycles would need to
have length at least $\ceil{n/(k-1)}$, the conjecture implies the result of
Bollobás and Häggkvist mentioned above. The case $k=3$ was already shown by Enomoto,
Kaneko and Tuza~\cite{EKT1988}. For the case of $2$-connected graphs $G$, the
conjecture was shown by Kouider in~\cite{Kou1994}. An Ore-type condition for
$k=3$ was given in~\cite{EKKT1995}. Finally, Kouider and Lonc solved the
conjecture (even in the stronger Ore-version) in~\cite{KL1996}. Thus:

\begin{theorem}[Kouider and Lonc~\cite{KL1996}]\label{thm:kl}
    Let $k\geq 2$ be an integer and let $G$ be an $n$-vertex graph 
    with minimum degree $\delta(G)\ge n/k$. Then the vertex set of $G$
    can be covered with $k-1$ cycles\footnote{Edges and vertices count as cycles.}.
\end{theorem}

This leaves open the problem of determining the structure of the extremal
examples. The minimum degree condition in Theorem~\ref{thm:kl} is tight by a
family of examples of graphs with $n$ vertices and minimum degree $n/k-1$ that
cannot be covered with $k-1$ cycles.

First, we can consider the disjoint union of $k$ copies of $K_{n/k}$. This
graph has $n$ vertices and minimum degree $n/k-1$ and yet clearly cannot be
covered with $k-1$ cycles, because every cycle must be confined to a single
copy of $K_{n/k}$. On the other extreme, we can imagine a graph on $n$ vertices
with minimum degree $n/k-1$ that contains an independent set of size
$(k-1)n/k+1$. A concrete example is given by the graph $I_{n,k}:= K_{n}
\setminus K_{(k-1)n/k+1}$, although there are also sparser examples that still
have minimum degree $n/k-1$. Note that every cycle in such a graph can cover at
most $n/k-1$ vertices of the independent set, so at least $k$ cycles are needed
to cover all vertices. Finally, the we can interpolate between these two types
of examples as follows. For any sequence $k_1,\dotsc,k_r$ of positive integers
such that $k_1+\dotsb=k_r=k$, we may consider the disjoint union $G= I_{k_1n/k,k_1}+ \dotsb +
I_{k_rn/k,k_r}$. Then $G$ is an 
$n$-vertex graph with minimum degree $n/k-1$ that
cannot be covered with $k-1$ cycles.
Note here that $I_{n/k,1}=K_{n/k}$, so this construction includes the disjoint union
of cliques.

It is natural to ask whether there are families of examples that are
substantially different. The main result of this paper is that this is not
the case: if the minimum degree is close to $n/k$ then either
the graph can be covered by $k-1$ cycles, or it is close to a subgraph of
$I_{k_1n/k,k_1}+ \dotsb + I_{k_rn/k,k_r}$ for a sequence $k_1,\dotsc,k_r$ of
positive integers summing to $k$. To make this precise, we need the following definitions:

\begin{definition}[separable partition]
  A partition of the vertices of a graph $G$ into sets
  $X_1,\dotsc,X_r$ is \emph{separable} if for all $i\neq
  j$ there exists a single-vertex $X_i$-$X_j$-cut in $G$.
\end{definition}

\begin{definition}[$(k',k,\beta)$-stable]\label{def:stable}
    Let $G$ be a graph of order $n$. Given a positive integer $k$ and real numbers
    $k'\in [1,k]$ and $\beta\in (0,1)$, we say that a subset $X\subseteq V(G)$ is
    \emph{$(k', k, \beta)$-stable} if there exists a subset $I\subseteq X$
    such that:
    \begin{enumerate}[(S1)]
        \item $|X|= k'n/k\pm \beta n$ and $|I|= (k'-1)n/k\pm \beta n$;
        \item we have $\delta(G[X])\geq n/k^4-\beta n$ and all but at most
          $\beta n$ vertices in $X$ have degree at least $n/k-\beta n$ in
          $G[X]$;
        \item $e(G[I])\leq\beta n^2$.
    \end{enumerate}
\end{definition}

With these definitions, our main result reads as follows:

\begin{theorem}\label{thm:stability}
    Given an integer $k\geq 2$ and $\beta>0$, there is $\alpha>0$ such that the
    following holds for sufficiently large $n$. Assume that $G$ is a graph with
    $n$ vertices and minimum degree at least $(1-\alpha)n/k$ whose vertices
    cannot be covered by $k-1$ cycles. 
    Then there is a separable partition $X_1,\dotsc,X_r$ of the vertices of $G$
    and positive integers $k_1,\dotsc,k_r$ such that
    \begin{itemize}
      \item each $X_i$ is $(k_i, k, \beta)$-stable in $G$, and
      \item $k_1+\dotsb+k_r = k$.
    \end{itemize}
\end{theorem}

Note that if $X_i$ is $(k_i,k,\beta)$-stable, then $G[X_i]$ is `$\beta$-close'
to a subgraph of $I_{k_in/k,k_i}$ with minimum degree $n/k$, with the set
$I$ in Definition~\ref{def:stable} playing the role of the (nearly) independent set.
Note also that if
$X_1,\dotsc,X_r$ is a separable partition, then $G$ can only contain very few
(say, at most $n$) edges going between different parts $X_i$ and $X_j$. Thus every
graph $G$ as in the theorem can be turned into a
subgraph of $I_{k_1n/k,k_1}+\dotsb +I_{k_rn/k,k_r}$ by changing at most
$C \beta n^2$ edges, for a constant $C>0$ independent of $\beta$.

Results of this type are usually referred to as
\emph{stability theorems}, the most famous example being the
Erd\H{o}s-Simonovits stability theorem for the Turán
problem~\cite{Sim1968}. It would also be interesting to find the
characterization of extremal families when $k=k(n)\to\infty$ as $n\to\infty$.

For the proof of Theorem~\ref{thm:stability}, we use the method of connected
matchings, invented by \L{}uczak~\cite{L1999}, which is based on an application
of Szemer\'edi's Regularity Lemma~\cite{Sze1976}. This method seems to be
widely applicable; for more applications (especially in Ramsey theory)
see~\cite{BBG+2014, BS2009a, BHP2012, FL2007, SSS2013, LS2017}.

\section{Preliminaries}

The following lemma states several useful properties of stable sets. The proof
of the lemma is not very interesting but quite technical, so we postpone it to
Section~\ref{sec:stable-sets} at the end of this paper.

\begin{lemma}[Properties of stable sets]\label{lemma:connecting}
    For every integer $k\geq 2$, there is some $\beta >0$ such that the
    following holds for all sufficiently large $n$. Let $G$ be a graph
    of order $n$ and assume that $X$ is an $(k',k,\beta)$-stable subset of
    $V(G)$, for some $k'\in [1,k]$. Then
    \begin{enumerate}[(a)]
        \item the vertices of $G[X]$ can be covered with $\ceil{k'}$ 
            cycles;
        \item given any two vertices $x,y\in X$, the vertices of $G[X]$ can be
            covered by $\ceil{k'}-1$ cycles and a single path with endpoints $x$ and
            $y$;
        \item if, additionally, all but at most $n/k^3$ vertices $x\in X$ satisfy
            $d(x,X)\geq |X|/k'$, then the vertices of $G[X]$ can be covered with
            $\ceil{k'}-1$ cycles.
    \end{enumerate}
\end{lemma}

We will also have occasion to use Szemerédi's Regularity Lemma~\cite{Sze1976}
and some related results. Given $\eps\in(0,1)$, we say that a pair $(A,B)$ of
disjoint sets of vertices of a graph $G$ is \emph{$\eps$-regular} if, for all
subsets $X\subseteq A$ and $Y\subseteq B$ such that $|X|\geq \eps |A|$ and
$|Y|\geq
\eps |B|$, we  have \[ \big| d_G(X,Y) - d_G(A,B)\big| \leq \eps. \]
A pair
$(A,B)$ is called $(\eps,\delta)$-\emph{super-regular} if it is
$\eps$-regular and \[ d_G(a,B) \geq \delta |B| \text{ for all } a\in A\qquad
\text{and} \qquad d_G(b,A) \geq \delta|A| \text{ for all } b\in B. \]

\begin{theorem}[Degree form of the Regularity Lemma~\cite{KS1996}]
    \label{thm:regularity} For every $\eps >0$ and every positive integer
    $t_0$, there is an $M=M(\eps, t_0)$ such that the following holds for
    every graph $G=(V, E)$ of order $n\ge M$ and every real number $d \in [0,1]$.
    There exists an integer $t\in [t_0, M]$, a partition $(V_i)_{i=0}^t$ of the
    vertex set $V$ into $t+1$ sets (called \emph{clusters}), and a subgraph
    $G'\subseteq G$ with the following properties:
    \begin{enumerate}
        \item[(R1)] $|V_{0}| \leq \eps |V|$,
        \item[(R2)] all clusters $V_{i}$ are of the same size $m\in ((1-\eps)n/t, n/t)$,
        \item[(R3)] $d_{G'}(v) > d_{G}(v) -(d+\eps)n$ for all $v\in V\setminus V_0$,
        \item[(R4)] $e(G'\left[V_{i}\right])=0$ for all $1\leq i\leq t$,
        \item[(R5)] for all $1\leq i< j \leq t$, the pair $(V_{i},V_{j})$ is
            $\eps$-regular, with a density either $0$ or greater than $d$.
    \end{enumerate}
\end{theorem}

A partition as in Theorem~\ref{thm:regularity} is usually called an
\emph{$\eps$-regular partition} with \emph{exceptional set} $V_0$. Given a
partition $(V_i)_{i=0}^t$ of the vertex set $V$ and a subgraph $G'\subseteq G$
satisfying conditions (R1)--(R5), we define the \emph{$(\eps, \delta)$-reduced
graph} as the graph $R$ with vertex set $[t]$ and edges corresponding to those
pairs $ij$ for which $(V_i, V_j)$ is $\eps$-regular and with density at least
$\delta$.

We shall also use the following special case of the famous Blow-up Lemma of
Komlós, Sárközy, and Szemerédi~\cite{KSS1996} (see also Lemma 24 and the first
remark after Lemma~25 in~\cite{Kom1999}). 

\begin{lemma}[Blow-up Lemma]\label{lemma:blowup} For every $\delta>0$ there exists an
    $\eps >0$ such that the following holds. Assume that a graph $G$ contains
    an $(\eps,\delta)$-super-regular pair $(A,B)$ with $|A|= |B|$ and let $x
    \in A, y \in B$. Then $G[A,B]$ contains a Hamilton path with endpoints $x$
    and $y$.
\end{lemma}

We will also need the Chernoff bounds for binomial and hypergeometric random
variables. Recall that a random variable $X$ is binomially distributed
if it is a sum of a fixed number of i.i.d.\ $\{0,1\}$-valued random variables,
while it is hypergeometrically distributed with parameters $N,K,n$ if it counts
the number of successes in a subset of size $n$ drawn uniformly at random from
a population of $N$ elements that
contains $K$ successes.

\begin{lemma}[Chernoff bounds~{\cite[Theorem 1.17]{Doe2011}}]\label{lemma:cher}
    Assume that $X$ is either binomially or hypergeometrically distributed.
    Then for all $\eps\in (0,1)$
    \[ \Pr[|X-\mathbf E[X]|\geq \eps\mathbf E[X]] \leq 2\exp(-\eps^2\mathbf E[X]/3). \]
\end{lemma}

\section{Proof of Theorem \ref{thm:stability}}

Let $k\ge 2$ be a fixed integer. Without loss of generality, we may assume that
the given $\beta>0$ is sufficiently small. Let us choose constants
$\eps,d,\alpha\in (0,1)$ and $t_0\in \NN$ such that \[ \frac{1}{t_0} \prec
\alpha \prec \eps \prec d \prec \beta, \] where by $a \prec b$ we mean that $a$
is chosen to be sufficiently smaller than $b$.

Let $G$ be a graph of order $n$ with $\delta(G)\geq (1-\alpha)n/k$, where $n$
is sufficiently large. Let $\hat\eps := \eps/(4k)$ and $\hat d := d+(k+1)\hat
\eps$. We apply the Regularity Lemma (Theorem~\ref{thm:regularity}) to $G$ with
parameters $\hat\eps$, $t_0$, and $\hat d$ to obtain a partition
$(V_i)_{i=0}^t$ and a subgraph $G'\subseteq G$ satisfying (R1--5), for some
integer $t_0\le t\le M$ and with $\hat\eps,\hat d$ instead of $\eps,\delta$. We
denote by $R$ the $(\hat \eps,\hat d)$-reduced graph corresponding to this
partition. 

\paragraph{Structure of the reduced graph.} The reduced graph $R$ is has $t$ vertices and it satisfies
\begin{equation}\label{eq:mindeg-R}
    \delta(R) \geq \frac{(1-2dk)t}{k}> \frac{t}{k+1}.
\end{equation}
To see this, simply observe that the vertices of every cluster in $R$ with
degree less than $(1-2dk)t/k$ would have degree at most $(1-2dk)(t/k)\cdot
(n/t) +\hat\eps n < (1-\alpha)n/k - (\hat d+\hat\eps)n$ in $G'$,
contradicting property (R3) of Theorem~\ref{thm:regularity}.

Let us denote by $r$ the number of components of $R$ and by
$R_1,\ldots,R_r$ the components themselves. Since each component has size at
least $\delta(R)> t/(k+1)$, there can be at most $k$ components altogether,
i.e., $r \leq k$.

For each component $R_i$, define a real number
\begin{equation}\label{eq:def-s_i}
    s_i:=\frac{k v(R_i)}{(1-2dk)t}\in (1,k+1),
\end{equation}
where the given bounds follow from $\delta(R_i) < v(R_i) \leq t$ and \eqref{eq:mindeg-R}.
Note that by combining \eqref{eq:mindeg-R} and \eqref{eq:def-s_i} we have
\begin{equation}\label{eq:mindegree-in-reduced-component}
    \delta(R_i)\geq v(R_i)/s_i.
\end{equation}
Finally, since $v(R_1)+\dotsc+v(R_r) = t$, we have 
\begin{equation}\label{eq:s_i-sum}
    \sum_{i=1}^r s_i =\frac{ k}{1-2dk} \leq (1+3dk)k,
\end{equation}
a fact that will be important later.

The components where $s_i < 2+4dk^2$ have such a large minimum degree that we
can treat them by a special argument. For the others, we have the following
structural lemma, whose proof we postpone to a later point.
\begin{lemma}\label{lemma:matchings}
  Let $i\in [r]$ and assume that $s_i \geq 2+4dk^2$. Let $m_i =
  \floor{s_i-4dk^2}$ and $t_i = v(R_i)$. Then at least one of the following is
  the case:
  \begin{enumerate}[(i)]
    \item the graph $R_i$ contains a subset $I\subseteq V(R_i)$ of size $(s_i-1)t_i/s_i-6dk^2 s_i t_i$
      that is almost independent in the sense that $e(I) \leq 4dk^2 s_i t_i^2$, or
    \item the graph $R_i$ contains matchings $M_1,\ldots,M_{m_i}$
      and disjoint subsets of vertices $D_1,D_2$ with the following properties:
      \begin{enumerate}[(a)]
        \item $D_1\cap V(M_1)=\emptyset$, and for $j>1$, $D_2\cap V(M_j) = \emptyset$;
        \item each vertex of $R_i$ has at least $d t_i/(3s_i)$ neighbours in each set $D_1,D_2$;
        \item the matchings $M_1,\dotsc,M_{m_i}$ cover the vertex set of $R_i$.
      \end{enumerate}
  \end{enumerate}
\end{lemma}

We apply Lemma~\ref{lemma:matchings} to each component $R_i$ where $s_i \geq
2+4dk^2$. From all such components that are in case (ii) of the lemma, we
obtain a collection $\mathcal M$ of matchings in $R$. Since each component
$R_i$ contributes at most $m_i$ matchings, and using~\eqref{eq:s_i-sum}, we see
that $\mathcal M$ contains at most $k$ matchings.

The significance of the matchings and the sets $D_1$ and $D_2$ will become
clear at a later point. Essentially, we will see that for each matching $M\in
\mathcal M$, we can cover the vertices in the subgraph of $G$ induced by the
clusters participating in the matching using a single cycle (covering also a
certain number of exceptional vertices in $V_0$ that are `assigned' to the
matching $M$). This will be an application of the Blow-up Lemma. Here the sets
$D_1$ and $D_2$ are used on the one hand to balance the sizes of the clusters
in $M$ and also to absorb the exceptional vertices assigned to
the matching.
However, to be able to apply the Blow-up Lemma, we need to modify the
regular partition a little, which we will do next.

\paragraph{Modifying the regular partition.}
We need to modify the initial regular partition $V_0,\dotsc,V_t$ in such a
way that each edge in each matching in $\mathcal M$ corresponds not just to an
$\hat \eps$-regular pair of density at least $\hat d$, but in fact to an
$(\eps, d$)\emph{-super-regular} pair (this is the reason why we applied
the Regularity Lemma with the slightly stronger parameters $\hat\eps,\hat
d$ instead of $\eps,d$). For this, we proceed as follows. For each edge
$(V_i,V_j)$ of a given matching $M\in \mathcal M$, we observe that by
regularity, at most $\hat \eps |V_i|$ vertices of $V_i$ have fewer then
$\hat d|V_j| - \hat\eps |V_j| = d|V_j|+k\hat\eps |V_j|$ neighbours in
$V_j$ and vice-versa. We move all vertices in these sets to the exceptional
set. Since $\mathcal M$ contains at most $k$ matchings, we remove at most
$k\hat \eps |V_i|$ vertices from each cluster $V_i$. By removing some
additional vertices, we can make sure that after this, all clusters are still
of the same size. Then one can check that the properties (R1--5) of
Theorem~\ref{thm:regularity} hold for the new partition with $\eps, d$
instead of $\hat\eps,\hat d$ (and with the same $G'$ and $t$). Moreover, we
have gained the property that the edges of the matchings in $\mathcal M$
correspond to $(\eps,d)$-super-regular pairs in $G$.

\paragraph{Partitioning into stable sets.}
For each $i\in[r]$, let us define $G_i$ as the subgraph of $G$ induced by the
vertices in clusters in $R_i$. Note that
\[ \bigcup_{i=1}^r V(G_i) = V(G)\setminus V_0. \]
Using (R2), we have \[ \frac{(1-\eps) n v(R_i)}{t} \leq v(G_i) \leq
\frac{nv(R_i)}{t}, \] so by plugging in the definition of $s_i$, we get
\begin{equation}\label{eq:g_i-size} \frac{(1-\eps)(1-2dk)n s_i}{k} \leq
v(G_i) \leq \frac{(1-2dk) n s_i}{k}. \end{equation} Using the inequalities \[
(1+dk)(1-2dk) = 1-dk-2d^2k^2 \leq 1-\alpha -(d+\eps)k \] and $\delta(G)\geq
(1-\alpha)n/k$ and properties (R3)--(R5), we obtain that
\begin{equation}\label{eq:mindegree-in-component} \delta(G_i) \geq
  \frac{(1-\alpha)n}{k}-(d+\eps)n \geq (1+dk)\frac{v(G_i)}{s_i}.
\end{equation}

Since $1\leq r\leq k$ and since $|V(G_1)\cup \dotsb \cup V(G_r)| \geq n - \eps
n$, it is clear that for every vertex $v\in V(G)$, there exists at least one
$i\in [r]$ such that the degree of $v$ into $V(G_i)$ is at least
$(\delta(G)-\eps n)/k$. Thus, we can partition the exceptional set $V_0$
into sets $U_1,\dotsc,U_r$, where $U_i$ contains only vertices with at least \[
(1-\alpha-k\eps)n/k^2 \geq n/k^3 \] neighbours in $V(G_i)$. The sets $Y_i:=
V(G_i)\cup U_i$ form a partition of the vertex set of $G$. This is
\emph{almost} the partition $X_1,\dotsc,X_r$ that Theorem~\ref{thm:stability}
asks for; as we will see, the sets $Y_i$ for which $s_i\in [2,2+4dk^2)$ might
have to be partitioned further.

To complete the proof of Theorem~\ref{thm:stability}, we need to distinguish
three cases. Each case is handled by one of the following lemmas.

\begin{lemma}\label{lemma:dirac}
  If $1\leq s_i < 2$, then $G[Y_i]$ is Hamiltonian. Moreover,
  if $s_i < 1+4dk^2$, then $Y_i$ is actually $(1, k, \beta)$-stable in $G$.
\end{lemma}

\begin{lemma}\label{lemma:almost-dirac}
  If $2 \leq s_i < 2+4dk^2$, then at least one of the following holds:
  \begin{enumerate}[(i)]
    \item $G[Y_i]$ is Hamiltonian,
    \item $Y_i$ is $(2,k,\beta)$-stable in $G$, or
    \item there is a partition of $Y_i$ into two $(1,k,\beta)$-stable sets in $G$.
  \end{enumerate}
\end{lemma}

\begin{lemma}\label{lemma:non-dirac}
  If $2+4dk^2 \leq s_i$, then either $Y_i$ can be covered with $\floor{s_i-4dk^2}$ 
  cycles in $G[Y_i]$, or $Y_i$ is $(\floor{s_i},k,\beta)$-stable in $G$.
\end{lemma}

The proofs of the first two lemmas are elementary. However, for the last lemma,
we will need to use the structure given by Lemma~\ref{lemma:matchings} and the
Blow-up Lemma (Lemma~\ref{lemma:blowup}). Given these three lemmas, we can
complete the proof of Theorem~\ref{thm:stability}.

\begin{proof}[Proof of Theorem \ref{thm:stability}]
  By combining Lemmas~\ref{lemma:connecting}, \ref{lemma:dirac},
  \ref{lemma:almost-dirac} and \ref{lemma:non-dirac}, we see that each graph
  $G[Y_i]$ can be covered with at most $\floor{s_i}$ cycles. By
  \eqref{eq:s_i-sum}, we have $\floor{s_1} + \dotsb + \floor{s_r} \leq k$.
  Since we assume that $G$ cannot be covered with $k-1$ cycles, this
  inequality is really an equality, i.e., $\floor{s_1}+\dotsb+\floor{s_r} = k$.

  This implies that for every $i\in [r]$, we have $\floor{s_i}\leq s_i <
  \floor{s_i} + 4dk^2$, as otherwise~\eqref{eq:s_i-sum} yields the
  contradiction
  \[ k = \sum_{i=1}^r\floor{s_i} = \sum_{i=1}^r s_i-\sum_{i=1}^r
  (s_i-\floor{s_i}) \leq (1+3dk)k-4dk^2 < k. \]

  But then, using again that we cannot cover the vertices of $G$ with $k-1$ cycles, 
  Lemmas~\ref{lemma:dirac}, \ref{lemma:almost-dirac} and \ref{lemma:non-dirac} 
  tell us that the situation is as follows:
  \begin{itemize}
    \item if $1\leq s_i < 2$, then $Y_i$ is $(1,k,\beta)$-stable;
    \item if $2 \leq s_i < 2+ 4dk^2$, then $Y_i$ is either $(2,k,\beta)$-stable
      or the union of two disjoint $(1,k,\beta)$-stable sets;
    \item if $s_i \geq 2+4dk^2$, then $Y_i$ is $(\floor{s_i},k,\beta)$-stable.
  \end{itemize}
  By splitting some of the sets $Y_i$ into two stable sets (if they are in the
  second case and not stable already), we obtain a partition of the vertices
  into $r'\geq r$ sets $X_1,\dotsc,X_{r'}$ such that each $X_i$ is
  $(k_i,k,\beta)$-stable for some integer $k_i$, where moreover
  $k_1+\dotsb+k_{r'}=k$.
  
  To complete the proof, we show that $X_1,\dotsc,X_{r'}$ is a separable
  partition. For this, let $i\neq j$ and assume for a contradiction that there is no
  single-vertex $X_i$-$X_j$-cut in $G$. Then by Menger's theorem there are
  two vertex-disjoint $X_i$-$X_j$-paths in $G$, and so using
  Lemma~\ref{lemma:connecting} (b) it is possible to cover $X_i\cup X_j$ by a
  $k_i+k_j-1$ cycles in $G$. Moreover, by Lemma~\ref{lemma:connecting} (a) it is
  possible to cover all other sets $X_\ell$ by $k_\ell$ cycles. Hence, there is
  a cover of the vertices of $G$ by $k_1+\dotsb+k_{r'}-1 =k-1$ cycles, which we
  assumed is not the case.
\end{proof}

It remains to give the proofs of Lemmas~\ref{lemma:matchings}, \ref{lemma:dirac},
\ref{lemma:almost-dirac}, and \ref{lemma:non-dirac}. 

\begin{proof}[Proof of Lemma \ref{lemma:matchings}]
  Since by \eqref{eq:mindeg-R}, we have $v(R_i) \geq t/(k+1)\geq t_0/(k+1)$, we
  can assume that $t_i=v(R_i)$ is very large compared to $1/d$. The only other
  property of $R_i$ that we will need is that $\delta(R_i)\geq v(R_i)/s_i$,
  by~\eqref{eq:mindegree-in-reduced-component}.

  First, we show that it is possible to choose disjoint subsets
  $D_1,D_2\subseteq V(R_{i})$, each of size at most $2d t_i$, in such a way
  that every vertex in $V(R_{i})$ has at least $d t_i/(3s_i)$ neighbours in
  $D_j$, for $j\in\{1,2\}$. For this, let $D$ be a random subset of $V(R_i)$ in
  which every cluster is included independently with probability $d$. Then let
  $D_1\cup D_2 = D$ be a partition of $D$ into two sets chosen uniformly at
  random. The expected size of $D_1$ and $D_2$ is $dt_i/2$. Thus, by Markov's
  inequality, with probability at least $1/2$, we have $|D_1|,|D_2|\leq 2d
  t_i$. Fix some vertex $v\in V(R_i)$. The expected number of neighbours of $v$
  that are in $D_1$ is at least $d \delta(R_i)/2 \geq dt_i/(2s_i)$. Using the
  Chernoff bounds, the probability that the neighborhood of $v$ does not
  contain at least $d t_i/(3s_i)$ elements of $D_1$ is smaller than $1/(4t_i)$,
  provided that $t_i$ is large enough. Similarly, the probability that the
  neighborhood of $v$ does not contain at least $\beta t_i/(3s_i)$ elements of
  $D_2$ is smaller than $1/(4t_i)$. The union bound shows that there exists a
  good choice for $D_1$ and $D_2$. From now on, fix such a choice.

  Let $m_i:=\floor{s_i-4dk^2}$ and observe that by assumption, we have $m_i\geq
  2$. We want to cover the set $V(R_i)$ by $m_i$ matchings
  $M_1,\dotsc,M_{m_i}$, so that $M_1$ is disjoint from $D_1$ and $M_2,\dotsc,
  M_{m_i}$ are disjoint from $D_2$. To do this, we first let $M_1$ be a maximal
  matching in $R_i$ that covers $D_2$ and is disjoint from $D_1$.
  Note that there certainly exists such a matching because of the minimum
  degree condition~\eqref{eq:mindegree-in-reduced-component} and because
  $D_1$ and $D_2$ are very small. Now, to choose the matchings $M_j$ for $j\geq
  2$, we partition the set $V(R_i)\setminus V(M_1)$ equitably into sets
  $A_2,\dotsc,A_{m_i}$. Then we let $M_j$ be a matching that is disjoint from
  $D_2$ and that covers the maximum number of vertices of $A_j$ (among all
  matchings that are disjoint from $D_2$); moreover, we assume that $M_j$ has
  maximum size among all such matchings. There are now two cases.

  \paragraph{Non-extremal case.} If $|M_1|\geq t_i/s_i+ 2dk^2 s_i t_i$, then we
  claim that we are in case (ii) of the lemma. The only thing to check is
  whether the matchings cover $R_i$. The set $V(R_i)\setminus V(M_1)$ has size
  \begin{align*}
    t_i-2|M_1| &\leq t_i -\frac{2t_i}{s_i} -4dk^2s_i t_i =\frac{t_i(s_i-2-4dk^2 s_i^2)}{s_i}\\
               & \leq \frac{t_i(s_i-4dk^2-2)(1-2ds_i)}{s_i} \leq \frac{t_i(m_i-1)(1-2ds_i)}{s_i},
  \end{align*}
  so for each $2\leq j\leq m_i$, we have \[|A_j| \leq
    \ceil*{\frac{t_i-2|M_1|}{m_i-1}} \leq \ceil{t_i/s_i - 2d t_i}
  \leq \delta(R_i) - |D_2|.\] Thus, there exists a matching disjoint from $D_2$
  that covers $A_j$ completely, and since $M_j$ was chosen to cover the most
  vertices of $A_j$ among all matchings disjoint from $D_2$, the matchings
  cover every vertex of  $R_i$.

  \paragraph{Extremal case.} If $|M_1|<t_i/s_i+2dk^2 s_i t_i$, then we will see
  that the graph must have a special structure.

  We will first show that $|M_1|\geq t_i/s_i -2dt_i$. Write $U$ for the set
  $V(R_i)\setminus(D_1 \cup V(M_1))$ of \emph{uncovered} vertices that are not
  in $D_1$. Note that $U$ is an independent set in $R_i$ (or the matching $M_1$
  would not be maximal). If $|U|\leq 1$, then, since $s_i\geq 2+4dk^2\geq 2/(1-2d-1/t_i)$ and
  $|D_1|\leq 2dt_i$, we have \[2|M_1|\geq t_i-|D_1|-1 \geq t_i - 2dt_i-1\geq
  2t_i/s_i,\] and we are done.
  Otherwise, there are at least two vertices $u,v\in U$.
  Since $M_1$ is maximal, we know that every neighbor of $u$ is either
  in $D_1$ or is covered by an edge of $M_1$, and similarly for $v$. Moreover, there are \emph{no}
  edges of $M_1$ between a neighbor of $u$ and a neighbor of $v$. Therefore
  \[ 2t_i/s_i \leq 2\delta(R_i)\leq d(u)+d(v)\leq 2|D_1|+2|M_1|, \]
  which implies that
  \begin{equation}\label{eq:m_j_lower} |M_1| \geq t_i/s_i - |D_1|\geq t_i/s_i-2dt_i.
  \end{equation}
  Now, since $|M_1|< t_i/s_i+2dk^2 s_i t_i$, we have
  \begin{equation}\label{eq:u_lower} |U|= t_i-|D_1|-2|M_1| \geq (s_i-2)t_i/s_i - 5dk^2 s_it_i.
  \end{equation}

  To complete the proof of the lemma, we will show that there exists a set of
  size $|U|+|M_1|$ which contains very few edges. For this, observe that by the
  maximality of $M_1$, for every edge $xy\in M_1$ at least one of the vertices
  $x,y$ has at most one neighbor in $U$. Thus, we may split $V(M_1)$ into two
  disjoint sets $A$ and $B$ of size $|M_1|$ by placing, for each edge of $M_1$,
  an endpoint with at most one neighbor in $U$ into $A$, and the other endpoint
  into $B$. Then we have $e(U,A)\leq |A|$; the `nearly independent set' that we
  are looking for will be $U\cup A$.

  To show that $U\cup A$ contains few edges, we will first show that most
  vertices in $B$ have at least two neighbours in $U$. Indeed, let $X:=\{v\in B
  \mid d(v,U)< 2\}$. Since $U$ is an independent set and since $V(R_i) = A\cup
  B \cup U \cup D_2$, we have
  \begin{align*}
    |X|& +|U|(|B|-|X|)\geq e(B,U)
    \geq |U|\delta(R_i)-e(U, V(R_i)\setminus B)\\
    & \geq |U|\delta(R_i)-e(U, A) - e(U,D_2))
    \geq |U|\delta(R_i)-|B| - |U||D_2|.
  \end{align*}
  Rearranging this inequality, and using that $|B|-\delta(R_i)\leq 2dk^2s_it_i$ and
  $|D_2|\leq 2dt_i$, as well as the fact that $|U|=\Omega(t_i)$ is sufficiently
  large, we get
  \[ |X| \leq \frac{|B| + |U||B|-|U|\delta(R_i)+|U||D_2|} {|U|-1}\leq 3dk^2s_i t_i.\]

  Let us now estimate the number of edges inside of $U\cup A$. We know that
  $e(U) = 0$ and $e(U,A)\leq |A|$. To bound $e(A)$, consider some edge $xy\in E(A)$
  and denote by $x'$ and $y'$ the vertices matched to $x$ and $y$ in $M_1$, respectively.
  Then, by the maximality of $M_1$, we can see that at least one of $x'$ and $y'$ has at
  most one neighbor in $U$. It follows that $e(A)\leq |A||X|$. Thus, using
  $e(U,A)\leq |A|$, $|X|\leq 3dk^2s_it_i$, $|A|\leq t_i$ and the fact that $U$ is
  an independent set, we get
  \[ e(U\cup A)\leq e(A)+e(U,A)\leq |A||X|+|A|\leq 4dk^2 s_it_i^2 \]
  and, using \eqref{eq:m_j_lower} and \eqref{eq:u_lower},
  \[ |U\cup A| =|U| + |M_1|\geq (s_i-1)t_i/s_i - 6dk^2s_i t_i. \]
  So we are in case (i) of the lemma.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lemma:dirac}]
  We start with the first part. Recall that $Y_i = V(G_i)\cup U_i$, where
  $U_i$ is a set of at most $\eps n$ vertices that have degree at least
  $n/k^3$ into $V(G_i)$. Also recall that by \eqref{eq:mindegree-in-component},
  we have $\delta(G_i) \geq (1+dk)v(G_i)/s_i \geq (1+dk)v(G_i)/2$. In
  particular, any two vertices $u,v\in V(G_i)$ are connected by at least
  $dkv(G_i)\geq 3|U_i|$ disjoint paths of length two. Then we can greedily construct a
  path $P$ of length $4|U_i|-2$ in $G[Y_i]$ such that $P$ starts and ends in
  vertices of $G_i$ and contains all vertices of $U_i$. More precisely, for each
  vertex $u\in U_i$, we can find two neighbours in $V(G_i)$ such that all neighbours are distinct;
  then we can connect these into a path by using the fact that any two neighbours have more than
  $3|U_i|$ common neighbours in $G_i$.

  The graph $G_i-V(P)$ still satisfies Dirac's condition. Let $C$ be a Hamilton cycle in $G_i-V(P)$
  and let $u,v\in G_i$ be the endpoints of $P$. Then, by the minimum degree condition, there are
  vertices $u',v'$ that are adjacent on $C$ and such that $uu',vv'\in E(G_i)$. By opening the cycle
  $C$ on the edge $u'v'$ and connecting $u'$ to $u$ and $v'$ to $v$, we obtain a Hamilton cycle in $G[Y_i]$.

  To see the second statement of the lemma, just let $X=Y_i$ and $I=\emptyset$.
  Since $d$ is very small compared to $\beta$, the conditions of
  Definition~\ref{def:stable} are easily verified. Specifically, (S1) follows
  from \eqref{eq:g_i-size}, (S2) follows from \eqref{eq:mindegree-in-component}
  and the definition of $U_i$, and (S3) is trivially true.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lemma:almost-dirac}]
  Assume that $2 \leq s_i < 2+4dk^2$.
  By \eqref{eq:mindegree-in-component} we have
  \[ \delta(G_i) \geq (1+dk)v(G_i)/s_i \geq (1-3dk^2)v(G_i)/2.\]
  Moreover, recall that $Y_i = V(G_i)\cup U_i$, where $U_i$ is a set of at most
  $\eps n$ vertices that each have at least $n/k^3$ neighbours in
  $V(G_i)$.

  We will show that at least one of the following holds:
  \begin{enumerate}[(i)]
    \item $G[Y_i]$ is Hamiltonian,
    \item $G[Y_i]$ contains an independent set of size at least $(1-10dk^2)|Y_i|/2$, or
    \item $Y_i$ contains two disjoint sets $A,B$ of size at least $(1-5dk^2)|Y_i|/2$ such that
      $e(A,B) = 0$.
  \end{enumerate}
  It is straightforward to verify that if we are in case (ii), then $Y_i$ is
  $(2,k,\beta)$-stable (let $I$ be the independent set of size
  $(1-10dk^2)|Y_i|/2$ and let $X := Y_i\setminus I$). Similarly, if we are
  in case (iii), then one easily checks that $Y_i = A\cup B$ is a partition into two
  $(1,k,\beta)$-stable sets.

  Thus, from now on, we shall assume that neither (ii) nor (iii) holds.
  Then for any two vertices $u,v\in V(G_i)$ and every subset $A\subseteq V(G_i)$ of size at least
  $v(G_i)-dn$, the graph $G[A \cup \{u,v\}]$ contains a path of length at most three that goes from $u$ to $v$.
  To see this, observe that both $u$ and $v$ have at least 
  \[ (1-3dk^2)v(G_i)/2-dn-1 \geq (1-5dk^2)v(G_i)/2 \]
  neigbors in $A$.
  If they have a common neighbor in $A$,
  or if there is an edge from a neighbor of $u$ in $A$ to a neighbor of $v$ in $A$, then we are done.
  Otherwise, the neighborhoods of $u$ and $v$ are disjoint subsets of size at least
  $(1-5dk^2)v(G_i)/2$
  with no edges between them, and we are in case (iii).

  From this observation, it is now easy to see that $G[Y_i]$ must contain a
  path $P$ of length $5|U_i|-3$ that contains all vertices of $U_i$ and whose
  endpoints are in $Y_i$. The construction is the same as in the proof of Lemma~\ref{lemma:dirac}:
  for each vertex of $U_i$ we find two neighbours in $V(G_i)$ such that all neighbours are distinct,
  and then we connect these neighbours using the observation to build the path $P$.
  Let us write $a_P$ and $b_P$ for the endpoints of $P$.

  Let $G_i'$ be the subgraph of $G_i$ induced by $\{a_P, b_P\} \cup V(G_i-P)$.
  Note that $v(G'_i)\geq v(G_i)- 5\eps n$, and that, consequently, $G'_i$ has minimum
  degree at least $(1-4dk^2)|Y_i|/2$.
  We may also assume that $G_i'-\{a_P,b_P\}$ is at least two-connected, since otherwise, by the minimum degree
  of $G_i'$, the graph would contain two sets $X,Y$ of size at least
  \[ \delta(G_i')-2 \geq (1-4dk^2)|Y_i|/2-2 \]
  that intersect only in an articulation point. But then, we would be in case (iii), contradicting our assumption.

  We will show that $G_i'$ contains a Hamilton 
  path joining $a_P$ to $b_P$. Clearly, this path will combine with $P$ to yield a 
  Hamilton cycle in $G[Y_i]$.
  Our strategy is the following. First, we will prove that $G_i'-\{a_P,b_P\}$ must contain a nearly spanning cycle. 
  Then, we will connect $a_P$ and $b_P$ with this cycle to form a nearly 
  spanning path from $a_P$ to $b_P$ in $G_i'$. Finally, we will absorb the few remaining vertices of 
  $G_i'$ into the path to get a Hamilton path.

  To obtain the first part, we use the well-known fact (also due to Dirac~\cite{Dir1952})
  that every two-connected graph with minimum degree $\delta$
  contains a cycle of length at least $2\delta$. In our case, this means that $G_i'-\{a_P,b_P\}$ contains
  a cycle $C$ of length
  \[ |C|\geq  2\delta(G_i'-\{a_P,b_P\}) \geq (1-5dk^2)|Y_i|.\]

  For the second step, as both $a_P$ and $b_P$ have degree larger than $|C|/3$
  into $C$, there must be a neighbor of $a_P$ on $C$ that is within distance at
  most two to a neighbor of $b_P$ on $C$, the distance being measured along the
  cycle $C$ (and making sure that the neighbours are distinct). Therefore, if we
  are generous, there is a path $P'$ in $G_i'$ with endpoints $a_P$ and $b_P$
  that has length at least $(1-6dk^2)|Y_i|$.

  To complete the proof, we show how to handle the at most $6dk^2 |Y_i|$
  vertices of $G_i'$ that do not belong to $P'$. Consider any such vertex $v\in
  V(G_i')$ and let $X$ be the set of all neighbours of $v$ on $P'$ that are not
  within distance less than two of either $a_P$ or $b_P$ (again, the distance
  being measured on $P'$). There must be at least $(1-10dk^2)|Y_i|/2$ such
  vertices. If any two neighbours $u$ and $w$ of $v$ are neighbours on $P'$, then we
  can absorb $v$ to $P'$ by following $P'$ from $a_P$ to $u$, using $uv$ and
  $vw$, and following $P'$ from $w$ to $b_P$. So, assume this is not the case.

  Orient $P'$ from $a_P$ to $b_P$, and let $Y$ be the set of the immediate
  successors of vertices in $X$ on the path. Since this is a set of size at
  least $(1-10dk^2)|Y_i|/2$, it must contain at least one edge $uw$, or else we
  would be in case (ii). However, using this edge, one can rotate the path $P'$
  to obtain a path going from $a_P$ to $b_P$ that contains all vertices of
  $P'$, as well as the additional vertex $v$. Indeed: let $u'\in X$ be the
  predecessor of $u$ and $w'\in X$ be the predecessor of $w$ on $P'$. We absorb
  $v$ to $P'$ by following  $P'$ from $a_P$ to $u'$, using $u'v$ and $vw'$,
  following $P'$ from $w'$ to $u$ , using $uw$, and following $P'$ from $w$ to
  $b_P$.

  In this way, it is possible to absorb all left-over vertices until the path
  spans the whole of $G_i'$.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lemma:non-dirac}]
  If $s_i \geq 2+4dk^2$, then by Lemma~\ref{lemma:matchings}, we know that the
  corresponding component $R_i$ of the reduced graph has a certain structure: either
  \begin{enumerate}[(i)]
    \item there is a subset $I\subseteq V(R_i)$ of size $(s_i-1)/s_i - 6dk^2s_it_i$
      with the property that $e(I)\leq 4dk^2s_it_i^2$, or 
    \item $R_i$ contains matchings $M_1,\dotsc,M_{m_i}$, where $m_i=\floor{s_i-4dk^2}$,
      and subsets $D_1,D_2\subseteq V(R_i)$ such that
      \begin{enumerate}[(a)]
        \item $D_1\cap V(M_1)=\emptyset$, and for $j>1$, $D_2\cap V(M_j) = \emptyset$;
        \item each vertex of $R_i$ has at least $d t_i/(3s_i)$ neighbours in each set $D_1,D_2$;
        \item the matchings $M_1,\dotsc,M_{m_i}$ cover the vertex set of $R_i$.
      \end{enumerate}
  \end{enumerate}

  Recall that $U_i$ is a set of at most $\eps n$ vertices that have degree at
  least $n/k^3$ into $V(G_i)$. If (i) is the case, then it follows easily from
  \eqref{eq:mindegree-in-component} and the
  properties of regularity that $Y_i=V(G_i)\cup U_i$ is a $(s_i,k,\beta)$-stable
  set in $G$ (note that $\eps,d$ are tiny compared to $\beta$).
  Since by \eqref{eq:mindegree-in-component}, all but $|U_i|\leq \eps n$ vertices
  of $Y_i$ have degree at least $|Y_i|/s_i$ in $G[Y_i]$, 
  it follows from Lemma~\ref{lemma:connecting} (c) that $G[Y_i]$
  can be covered with $\ceil{s_i}-1$ cycles. Therefore, either
  we can cover $G[Y_i]$ with $\floor{s_i-4dk^2}$ cycles, or $
  \floor{s_i-4dk^2} < \ceil{s_i}-1\leq s_i$ and so $s_i \leq \floor{s_i}+4dk^2$.
  In the former case, we are done, and in the latter case, it is again easy to verify
  that $Y_i$ must actually be $(\floor{s_i},k,\beta)$-stable (again, the extra
  $4dk^2$ gets lost in the much larger $\beta$). Thus if we are in case (i),
  then the lemma holds.

  From now on, assume that we are in case (ii). Recall that each edge of each
  matching $M_j$ is $(\eps,d)$-super-regular. We may assume that $\eps$
  is so small that Lemma~\ref{lemma:blowup} applies with $\delta = d$. The
  general idea is to use Lemma~\ref{lemma:blowup} to cover the preimage of each
  matching (meaning: the vertices of $G$ participating in clusters of the
  matching) by a single cycle in $G[Y_i]$, and to do this in such a way that
  all the vertices in $U_i$ are absorbed. Of course, if we manage to do so,
  then we are done. We start by assigning the exceptional vertices of $U_i$ to
  clusters $C$ into which they have large degree.

  \paragraph{Assigning the exceptional vertices.} For each matching $M_j$, let us
  write $V_{M_j}\subseteq V(G_i)$ for the union of all clusters in $M_j$. As
  the matchings $M_j$ cover the vertices of $R_i$, we have
  $\bigcup_{j=1}^{m_i}V(M_j)=V(G_i)$. Since each vertex of $U_i$ has degree at
  least $n/k^3$ into $V(G_i)$, and since $m_i\leq k$, we see that for every
  $u\in U_i$ there exists a $j_u\in [m]$ such that $u$ has $n/k^4$ neighbours
  in $V_{M_{j_u}}$. Let us write $U_i^{(j)} := \{u\in U_i \mid j_u = j\}$ for
  the exceptional vertices assigned to the matching $M_j$ in this way.

  Since $|V(M_j)|\leq |V(R)|\leq t$ and since each cluster has size at most
  $2n/t$, it follows that for each vertex $u\in U_i^{(j)}$, there are at least
  $t/(4k^4)$ clusters $C\in V(M_j)$ such that $d(u,C)\geq n/(2k^4 t)$. Indeed,
  if this were not true, then the degree of $u$ into $V(M_j)$ would be strictly
  below \[ t\cdot \frac{n}{2k^4t} + \frac{t}{4k^4}\cdot \frac{2n}{t} =
  \frac{n}{k^4}, \] a contradiction with the definition of $U_i^{(j)}$.

  We now assign the vertices of $U^{(j)}_i$ to clusters in $V(M_j)$ in such a way that
  \begin{enumerate}[(i)]
    \item if $u$ is assigned to the cluster $C$, then $d(u,C)\geq n/(2k^4t)$, and
    \item at most $4k^4\eps n/t$ vertices are assigned to each cluster.
  \end{enumerate}
  Since $|U_i^{(j)}|\leq \eps n$ and since each vertex has $t/(4k^4)$ candidates, such an assignment
  exists. Take any such assignment and write $U_C$
  for the exceptional vertices assigned to the cluster $C\in V(M_j)$.

  \paragraph{Covering the matchings.}
  From the above, it is clear that the sets
  \[V_{M_1}\cup U_i^{(1)},V_{M_2}\cup U_i^{(2)},\dotsc,V_{M_{m_i}}\cup U_i^{(m_i)}\]
  cover the set $Y_i$.
  In the following,
  we will cover each set $V_{M_j}\cup U_i^{(j)}$ by a single cycle in $H_i$
  (however, this cycle might use vertices outside of $V_{M_j}\cup U_i^{(j)}$).

  Fix some $j\in [m_i]$, and assume $\ell\in \{1,2\}$ is such that $D_\ell$ is
  disjoint from the matching $M_j$. The embedding proceeds in two steps: first,
  for each cluster $C\in V(M_j)$, we connect the vertices of $U_C$ by a short
  path using only vertices from $D_\ell$, $C$, and $U_C$ (and making sure that
  the paths for different $C$ are vertex-disjoint); second, we use Lemma~\ref{lemma:blowup} to
  connect these short paths into a cycle spanning the whole of $V_{M_j}\cup
  U_i^{(j)}$.

  In the first step, it is important to make sure that each path uses exactly
  the right number of vertices in the cluster $C$, as otherwise the second step
  might fail. Because we do not want to make this completely precise at this
  point, we assign to each cluster $C$ an integer
  \[ \ell_C\in [8k^4 \eps n/t, 100k^4\eps n/t],\]
  and we will make sure that after creating the short path for $C$, the number
  of vertices of $C$ not used by the path is exactly $|C|-\ell_C$. The bounds
  of $\ell_C$ allow us enough control over the number of remaining vertices per
  cluster, without hurting the super-regularity of the pairs corresponding to
  edges of $M_j$ in a significant way.

%  We will also assume that for each $j'<j$, we already covered the vertices in
%  $V_{M_{j'}}\cup U_i^{(j')}$ with a cycle. Since we want the new cycle to be
%  edge-disjoint from these other cycles, we remove the corresponding cycles
%  from the graph (thus removing at most $2k$ edges in each vertex). It is easy
%  to see that the remaining graph still has all necessary regularity
%  properties.

  \paragraph{Step 1: creating the small paths.} First, we assign each $C\in V(M_j)$
  to a neighbor $D_C$ of $C$ in $D_\ell$ in such a way that we assign at most
  $3s_i/ d$ clusters of $V(M_j)$ to each cluster in $D_\ell$. This is
  possible because each vertex of $R_i$ has at least $d t_i/(3s_i)\geq  d
  t_i/(3s_i)$ neighbours in $D_\ell$ and because there are at most $t_i$
  clusters in $V(M_j)$.

  During the construction of the paths, for every $D\in D_\ell$ and $C\in
  V(M_j)$, we maintain sets $A(D)\subseteq D$ and $A(C)\subseteq C$ of
  \emph{available} clusters; initially $A(D)= D$ and $A(C)=C$ for all $D$ and
  $C$, i.e., all clusters are available. The sets $A(D)$ and $A(C)$ will shrink
  during the construction of the paths; however, it will be true throughout
  that for each $C\in V(M_j)$ and $D\in D_\ell$, we have $|A(C)|\geq
  |C|-K\eps |C|/ d$ and $|A(D)|\geq |D| - K\eps |D|/
  d$, where $K=K(k)$ is a sufficiently large constant depending only on $k$,
  but not on $\eps$ or $ d$. Since $\eps$ is very small
  compared to $ d$, this means that almost all clusters are available
  throughout the process.

  For each cluster $C\in V(M_j)$, we shall first build a path $P_C'$ covering
  the vertices of $U_C$. The path will have the form
  \[ P_C' = x_1u_1y_1\;z_2\;x_2u_2y_2\;z_3\;x_3u_3y_3\;\dotsb\;z_{|U_C|}\; x_{|U_C|} u_{|U_C|} y_{|U_C|},\]
  where $x_p,y_p\in C$, $u_p\in U_C$ and $z_p\in D_C$. After doing this, we
  will extend this path to a path $P_C$ that uses exactly $\ell_C$ vertices of
  $C$, completing the first step in the outline given above.

  We now describe how to construct $P_C'$. Recall that every vertex $u\in U_C$ has
  $n/(2k^4t)\geq 2K\eps |C|/ d$ neighbours in $C$.  Order the vertices of
  $U_C$ arbitrarily. For the first vertex $u_1\in U_C$, let $x_1$ be an
  arbitrary neighbor of $u_1$ in $A(C)$, and let $y_1$ be a vertex in
  $A(C)\setminus \{x_1\}$ that has at least $ d n/(3t)$ neighbours in
  $A(D_C)$. Assuming that $|A(C)|\geq |C|-K\eps |C|/ d$ and
  $|A(D_C)|\geq |D_C|-K\eps |D_C|/ d$, such neighbours exist by the
  fact that the pair $(C,D_C)$ is $\eps$-regular with density at least
  $ d$. Remove $x_1,y_1$ from $A(C)$.

  At every subsequent step, consider the current $u_p\in U_C$. Provided that
  $|A(C)|\geq |C|-K\eps |C|/ d$, there is a neighbor $x_p$ of $u_p$ in
  $A(C)$ that has a neighbor $z_p$ in the neighborhood of $y_{p-1}$ in
  $A(D_C)$, which we may assume (by induction) to be of size at least $ d
  n/(3t)\geq \eps |D_C|$. Similarly, there is a neighbor $y_p\in A(C)$
  that has at least $ dn/(3t)$ neighbours in $A(D_C)\setminus\{z_p\}$, again
  provided that $A(C)$ and $A(D_C)$ are large. Remove $z_p$ from $A(D_C)$ and
  remove $x_p,y_p$ from $A(C)$.

  We can continue in this way as long as $A(C)$ and $A(D_C)$ are sufficiently
  large. For every vertex in $U_C$ we remove at most one vertex from $A(D_C)$
  and two from $A(C)$. Since (for large enough $K$) we have $|U_C|\leq
  4k^4\eps n/t\leq K\eps |C|/(6s_i)$, and as only at most
  $3s_i/ d$ clusters have chosen $D_C$, it follows that both $A(C)$ and
  $A(D)$ lose at most $K\eps |C|/ d$ vertices throughout this
  process. In other words, the process can be carried out until all vertices of
  $U_C$ are covered.

  Note that the path $P_C'$ uses exactly $2|U_C|\leq 8k^4\eps n/t$ vertices
  from $C$. However, we would like to have a path that uses exactly $\ell_C\in
  [8k^4\eps n/t, 100k^4\eps n/t]$ vertices of $C$. For this reason, we
  will extend the path in the following way.

  By construction, $y_{|U_C|}$ has $ d n/(3t)\geq \eps |D_C|$
  neighbours in $A(D_C)$. The typical vertex in $A(C)$ has a neighbor in this
  neighborhood, as well as $ dn/(3t)$ additional neighbours in $A(D_C)$. Thus we
  may take such a vertex $x_{|U_C|+1}$ and a common neighbor $z_{|U_C|+1}\in
  A(D_C)$ of $x_{|U_C|+1}$ and $y_{|U_C|}$, and create a longer path $P_C' \;
  z_{|U_C|+1}\; x_{|U_C+1|}$. Then, we remove $z_{|U_C|+1}$ from $A(D_C)$ and
  $x_{|U_C|+1}$ from $A(C)$. As before, this process will not fail while
  $|A(C)|\geq |C|-K\eps |C|/ d$ and $|A(D_C)|\geq |D_C|-K\eps
  |D_C|/ d$ hold for all $C\in V(M_j)$. If $K$ is large
  enough, then this means that we can continue for at least $100(k+1)k^3
  \eps n/t$ steps, and we do so until the path contains exactly $\ell_C$
  vertices of $C$.

  Call the resulting path $P_C$. Observe that for different
  $C,C'\in V(M_j)$, the paths $P_C$ and $P_{C'}$ are vertex-disjoint. Moreover, each path $P_C$ has its endpoints
  in $C$,  uses $\ell_C$ vertices of $C$ (and no vertices of other clusters in $V(M_j)$), and
  visits all vertices in $U_C$.

  \paragraph{Step 2: finishing the embedding.}

  Let $T_j$ be a minimal tree in $R_i$ containing the matching $M_j$ as a
  subgraph (such a tree exists because $R_i$ is connected), and let $m =
  |T_j|-1$ be the number of edges of $T_j$. 
  For each $C\in V(M_j)$, choose
  $\ell_C\in [8(k+1)k^3\eps n/t, 100(k+1)k^3\eps n/t]$ such that
  \[ |C| - \ell_C = \floor{n/t} - \floor{20k^4\eps n/t} + d_{T_j}(C). \]
  This is possible since $n/t \geq |C|\geq (1-\eps)n/t$ and since
  $d_{T_j}(C)\leq t$ is bounded by a constant.

  By doubling the edges of $T_j$ and considering an Euler tour in the resulting
  graph, one can see that there exists a surjective homomorphism $\pi\colon
  C_{2m} \to T_j$  that covers each edge of $T_j$ exactly twice, i.e., for each
  edge $e\in T_j$, there are exactly two edges $e_1,e_2\in E(C_{2m})$ such that
  $\pi(e_1)=\pi(e_2)=e$. For each edge $e\in M_j$, we (arbitrarily) color the
  edge $e_1$ red. Let us, for the moment, remove all red edges from $C_{2m}$,
  resulting in the graph $C_{2m}'$, which is just a system of disjoint paths.
  We now choose any embedding \[\iota\colon C_{2m}'\to G\] with the property
  that every $x\in V(C_{2m}')$ is mapped to a vertex in the cluster $\pi(x)$, and whose
  image is disjoint from the vertices of the paths $P_C$. Such an embedding
  exists by regularity: for every path $x_1,\dotsc,x_r$ in $C_{2m}'$, we may
  first embed $x_1$ to a vertex in $\pi(x_1)$ that has at least $ d|\pi(x_2)|/2$
  neighbours in $\pi(x_2)$. Of these neighbours, at least half will have at least
  $d|\pi(x_3)|/2$ neighbours in $\pi(x_3)$, so we may embed $x_2$ to any such
  neighbor. Continuing in this way, we can completely embed $x_1,\dotsc,x_r$ in
  $G$ in the desired way, and we can do this for every path in $C_{2m}'$. Note
  that some vertices might be embedded into the same cluster of $R_i$; however,
  as $m\leq t$ is a constant and as each cluster has linear size, this does not
  pose any difficulty.

  At this point, we have merely embedded some disjoint paths into $G$. For each
  red edge $xy\in E(C_{2m})$, we will now embed into $G$ a path with endpoints
  $\iota(x)$ and $\iota(y)$ that contains the paths $P_{\pi(x)}$ and 
  $P_{\pi(y)}$, and that, moreover, contains all vertices of $\pi(x)\cup \pi(y)$
  that are not in the image of $\iota$. Thus, we will extend $\iota$ to an
  embedding of a subdivision of $C_{2m}$ into $G$ whose image contains the set
  $V_{M_j}\cup U_i^{(j)}$, as required. Since for each red edge $xy$, the pair
  $(\pi(x),\pi(y))$ is $(\eps,d/2)$-super-regular, this is relatively easy
  to achieve: first, we connect an endpoint of $P_{\pi(x)}$ to $\iota(x)$ by a
  path of length four (such a path exists by regularity); similarly, we connect an endpoint of $P_{\pi(y)}$ to
  $\iota(y)$ by a path of length four; finally, we use the
  Lemma~\ref{lemma:blowup} to connect the other endpoint of $P_{\pi(x)}$ to the
  other endpoint of $P_{\pi(y)}$ by a Hamilton path in the bipartite subgraph
  of $G[\pi(x),\pi(y)]$ induced by the remaining vertices. The only thing to
  check is that this subgraph is balanced. However, this follows from our choice
  of $\ell_C$ and the fact that the image of $\iota$ intersects each cluster $C$
  in exactly $d_{T_j}(C)$ vertices.
\end{proof}

\section{Proof of Lemma \ref{lemma:connecting}}\label{sec:stable-sets}

It remains to prove Lemma~\ref{lemma:connecting}. In this section, we will use
the notations $G-e$ and $G+e$ to denote the graph obtained from $G$ by adding
or removing a given edge $e$. We also use the notation $G+H$ to denote the
\emph{union} of the graphs $G$ and $H$, i.e., the graph $(V(G)\cup
V(H),E(G)\cup E(H))$ (note that before, the same notation was used for the
\emph{disjoint} union).
In the proof, we will use the following auxiliary results:

\begin{lemma}[{Berge~\cite[Chapter 10.5, Theorem
  13]{Ber1973}}]\label{lemma:ham-connect}
  Let $G=(V,E)$ be a graph with $n\geq 3$ vertices such that for each $2\leq
  j\leq (n+1)/2$, fewer than $j-1$ vertices have degree at most
  $j$ in $G$. Then for any two vertices $u\neq v$, there is a Hamilton
  path with endpoints $u$ and $v$ (and in particular, $G$ is Hamiltonian).
\end{lemma}


%(see e.g.~\cite[Corollary~3]{MM1963}).
%
%\begin{lemma}\label{lemma:bp-dirac}
%  Let $n\geq 2$ and let $G$ be a balanced bipartite graph on $2n$ vertices with
%  minimum degree $\delta(G)> n/2$. Then $G$ is Hamiltonian.
%\end{lemma}

\begin{lemma}[{Berge~\cite[Chapter 10.5, Theorem
  15]{Ber1973}}]\label{lemma:ham-connect-bp}
  Let $G=(A,B,E)$ be a bipartite graph with $|A|=|B|=n\geq 2$ such that for
  each $2\leq j\leq (n+1)/2$, fewer than $j-1$ vertices have degree at most
  $j$ in $G$. Then for any two vertices $a\in A$ and $b\in B$, there is a Hamilton
  path with endpoints $a$ and $b$.
\end{lemma}

\begin{lemma}\label{obs}
  Let $G=(A,B,E)$ be a bipartite graph. Let $s,t$ be
  positive integers. Suppose that $G$ contains a cycle $C$ and a collection
  of paths $P_1,\dotsc,P_t$ such that $|V(P_1)\cup \dotsb \cup V(P_t)| \leq
  s$ and such that the following hold:
  \begin{itemize}
    \item each $P_i$ has one endpoint in $a_i\in A$ and one endpoint in $b_i\in B$;
    \item these endpoints satisfy $d(b_i,A) > (|A|+s)/2$ and $d(a_i,B)
      > (|B|+s)/2$, for every $i\in [t]$;
    \item $C,P_1,\dotsc,P_t$ are vertex-disjoint and cover all vertices of $G$.
  \end{itemize}
  Then $G$ is Hamiltonian.
\end{lemma}
\begin{proof}
  We can define a sequence $C_0,C_1,\dotsc,C_t$ of cycles in $G$ such that
  $C_i$ covers exactly the vertices in $V(C)\cup V(P_1)\cup \dotsb \cup
  V(P_i)$. For this, let $C_0 = C$. Suppose that we have defined $C_{i-1}$.
  Using the condition on the degrees of $a_i$ and $b_i$, the pigeonhole
  principle implies that $C_{i-1}$ contains some edge $uv$ such that $a_iu$ and
  $b_iv$ are edges of $G$. Then we can define $C_i := C_{i-1} - uv + a_iu +
  b_iv + P_i$. Finally, $C_t$ is a Hamilton cycle in $G$.
\end{proof}

To keep the proof of Lemma~\ref{lemma:connecting} as short as possible,
we define the following notion:

\begin{definition}[Good pair]
  Let $G$ be a graph of order $n$ and let an integer $r\geq 1$ and real
  numbers $\gamma,\delta \in (0,1)$ be given. A pair $(A,B)$ of disjoint
  subsets of $V(G)$ is said to be \emph{$(\gamma,\delta,r)$-good} if the
  following hold:
  \begin{enumerate}[(P1)]
    \item $\gamma n \leq |A|\leq |B| \leq r\cdot |A|$;
    \item $d(b,A) \geq |A|-\delta n$ for all but at most $\delta n$ vertices $b\in B$;
    \item $d(a,B) \geq |B|-\delta n$ for all but at most $\delta n$ vertices $a\in A$;
    \item for all $a\in A$ and $b\in B$, we have $d(b,A)\geq \gamma n$ and
      $d(a,B)\geq \gamma n$.
  \end{enumerate}
\end{definition}

\begin{lemma}\label{lemma:goodpair}
  For every integer $k\geq 1$ and every $\gamma > 0$, there is an integer $n_0$
  and a real number $\delta \in (0,1)$ such that the following holds for every
  $n\geq n_0$. Let $G$ be a graph on $n$ vertices and let
  $(A,B)$ be a $(\gamma,\delta,r)$-good pair in $G$, for some integer $r\in
  [k]$. Then $G[A, B]$ can be covered by at most $r$ cycles.
\end{lemma}

\begin{proof}
  Let $k$ and $\gamma$ be given and let $G$ be a graph $n\geq n_0$ vertices, where
  $n_0 = n_0(k,\gamma)$ is a sufficiently large constant. Suppose further that
  $\delta=\delta(k,\gamma)$ is sufficiently small. For $r\in [k]$ let us
  define $\gamma_r := \gamma\cdot (2k)^{r-k}$. We will show by induction on $r$
  that $(\gamma_r,\delta,r)$-good pair $(A,B)$ in $G$ can be covered by at most
  $r$ cycles, for all $1\leq r \leq k$. Then the lemma follows by  noting that
  $\gamma_r \leq \gamma$ for all $r\in [k]$.

  The base case $r=1$ follows easily from Lemma~\ref{lemma:ham-connect-bp}
  applied to $G[A,B]$.
  Indeed, suppose $(A,B)$ is $(\gamma_1,\delta,r)$-good in $G$. Then by (P1) we
  have $|A| = |B|\geq 2$, and for $\gamma_1 n \leq j\leq (|A|+1)/2$, the number
  of vertices with degree at most $j$ is at most $\delta n < j-1$, while for
  $j<\gamma_1 n$, the number of vertices of degree at most $j$ is zero. Hence,
  $G[A,B]$ is Hamiltonian.
%  Let $S\subseteq A\cup B$ denote the `special' set of vertices $x\in A\cup B$
%  for which both $d(x,A) < |A|-\delta_1 n$ and $d(x,B) < |B|-\delta_1 n$. By
%  (P2) and (P3), we have $|S|\leq 2\delta_1 n$. By (P4) and because $\gamma_r n$ is
%  much larger than $|S|$, we can greedily find a collection
%  $P_1,\dotsc,P_{|S|}$ of paths of length three such that
%  $S\subseteq V(P_1)\cup \dotsb \cup V(P_{|S})$ and such that
%  each $P_i$ has endpoints $a_i\in A$ and $b_i\in B$ such that
%  $d(b_i,A) \geq |A|-\delta_1 n$ and $d(a_i,B) \geq |B|-\delta_1 n$.
%
%  Let $T := V(P_1)\cup \dotsb \cup V(P_{|S|})$. Since $|T\cap A|= |T\cap
%  B|\leq 2|S| \leq 4\delta_1 n$ and since $S\subseteq T$, by (P2) and (P3)
%  the graph $G[A\setminus T, B\setminus T]$ has minimum degree at least $|A|
%  - 5\delta_1 n> |A|/2 = |B|/2$, where we used that $|A|= |B|\geq \gamma_1
%  n>10\delta_1 n$. Moreover, $|A\setminus T| = |B\setminus T| \geq \gamma_1 n
%  - 4\delta_1 n \geq 2$. Then by Lemma~\ref{lemma:bp-dirac}, $G[A\setminus
%  T,B\setminus T]$ contains a Hamilton cycle $C$. By Lemma~\ref{obs}
%  applied to $C,P_1,\dotsc,P_{|S|}$, we get that $G[A\cup B]$ is Hamiltonian,
%  thus completing the proof in the case $r=1$.

  For the induction step, suppose that $r\geq 2$ and recall that $\gamma_r =
  \gamma\cdot (4k)^{r-k}$. Let $(A,B)$ be a $(\gamma_r,\delta,r)$-good
  pair in $G$.
  We claim that there
  exist subsets $B_1,B_2\subseteq B$ such that $B = B_1\cup B_2$ and such
  that $(A,B_1)$ is $(\gamma_1,\delta,1)$-good and $(A,B_2)$ is
  $(\gamma_{r-1},\delta,r-1)$-good. If such a partition exists, then
  the claim follows by applying the induction hypothesis on the pairs
  $(A,B_1)$ and $(A,B_2)$.

  To find the sets $B_1$ and $B_2$, we use the probabilistic method. Let $B_1$
  be a subset of $B$ chosen uniformly at random among all subsets of size $|A|$
  (such a set exists because $|B|\geq |A|$). Let $B_2' := B\setminus B_1$ and let
  $B_2''$ be a subset of $B_1$ chosen uniformly at random among all subsets of
  size $\max{\{0,|A|-|B_2'|\}}$. Finally, let $B_2 := B_2' \cup B_2''$. Note
  that $|B_2| = \max{\{|A|,|B|-|A|\}}$. Clearly $B_1$ and $B_2$ cover $B$,
  and it is enough to show that with positive
  probability, $(A,B_1)$ is $(\gamma_1,\delta,1)$-good and $(A,B_2)$ is
  $(\gamma_{r-1},\delta,r-1)$-good.
  
  We first show that $(A,B_2)$ is $(\gamma_{r-1},\delta,r-1)$-good with
  probability at least $0.6$. Since $(A,B)$ is $(\gamma_r,\delta,r)$-good we
  have $\gamma_r n \leq |A|\leq |B|\leq r|A|$. Thus also \[ \gamma_{r-1} n\leq
  \gamma_r n\leq |A|\leq  |B_2| = \max{\{|A|,|B|-|A|\}} \leq (r-1)|A|, \]
  verifying (P1) for the pair $(A,B_2)$. It is easy to see that (P2) and (P3)
  hold for $(A,B_2)$ automatically, using the assumption that $(A,B)$ satisfies
  (P2) and (P3). As far as (P4) is concerned, it follows from the goodness of
  $(A,B)$ that for all $b\in B_2$ we have $d(b,A) \geq \gamma_r n \geq
  \gamma_{r-1}n$. It remains to show that with probability at least $0.6$ we
  also have $d(a,B_2) \geq \gamma_{r-1}n$ for all $a\in A$. Fix some $a\in A$.
  The degree $d(a,B_2)$ is distributed hypergeometrically with mean \[ \mathbf
  E[d(a,B_2)] \geq d(a,B)\cdot \frac{|B_2|}{|B|}\geq \gamma_r n/r \geq
  2\gamma_{r-1} n, \] where we used $|B_2| \geq |A| \geq |B|/r$ and the
  definition of $\gamma_r$. By the Chernoff bounds,
  we obtain \[ \mathbf P[d(a,B_2) < \gamma_{r-1} n ] \leq e^{-\gamma_{r-1}n/12}
  \leq 0.6/n, \] if $n$ is sufficiently
  large given $\gamma$ and $k$. By the union bound, with probability $0.6$,
  every $a\in A$ satisfies $d(a,B_2)\geq \gamma_{r-1}$, and so (P4) holds with
  probability at least $0.6$.
  Analogously, one shows that $(A,B_1)$ is $(\gamma_1,\delta,r)$-good with
  probability at least $0.6$, so there exists a choice of $B_1$ and $B_2$
  such that $(A,B_1)$ is $(\gamma_1,\delta,1)$-good and $(A,B_2)$ is
  $(\gamma_{r-1},\delta,r-1)$-good.
\end{proof}

Before continuing, we show that for certain stable sets $X$ (namely,
those where $k'$ is not too small) we can find a
partition $X = A\cup B$ that is `almost good'. For this, we have the following
claim. Note that (P2'), (P3') and (P4') in the claim correspond exactly to
(P2), (P3) and (P4) in the definition of a good pair (with $\gamma=1/(7k^4)$).
Condition (P5') tells us something about the structure of $G[B]$ in the case
where $|B| > (\ceil{k'}-1)|A|$.

\begin{lemma}\label{lemma:ag}
  For every $\delta>0$ and $k\in \NN$, there is $\beta>0$ such that
  the following holds for all sufficiently large $n$.
  Let $G$ be a graph of order $n$ and suppose that $X$ is $(k',k,\beta)$-stable
  in $G$ where $2-4k\beta\leq k'\leq k$. Then there exists a partition $X =
  A\cup B$ with the following properties:
  \begin{enumerate}[(P1')]
    \item $|A|= n/k\pm \delta n$ and $|B| = (k'-1)n/k \pm \delta n$ and
      $|B|\geq |A|$;
    \item $d(b,A) \geq |A|-\delta n$ for all but at most $\delta n$ vertices $b\in B$;
    \item $d(a,B) \geq |B|-\delta n$ for all but at most $\delta n$ vertices $a\in A$;
    \item for all $a\in A$ and $b\in B$, we have $d(b,A)\geq n/(7k^4)$ and
      $d(a,B)\geq n/(7k^4)$.
    \item we have $\Delta(G[B])\leq n/(6k^4)$ or $|B|\leq (\ceil{k'}-1)|A|$.
  \end{enumerate}
\end{lemma}
\begin{proof}
  It is enough to  show the required properties with $18\delta$ instead of
  $\delta$.
  Assume that $\beta$ is sufficiently smaller than $\delta$. Let
  $I\subseteq X$ be a nearly independent set as in Definition~\ref{def:stable}.
  As a first approximation, we may choose $A'' := X\setminus I$ and $B'' := I$.
  Then we have (say) $|A''|= n/k \pm \delta n$ and $|B''| = (k'-1)n/k \pm
  \delta n$, using (S1). Moreover, one can use the properties (S1--3) and an
  averaging argument to show that $d(b,A'') \geq |A''|-\delta n$ holds for
  all but at most $\delta n$ vertices $b\in B''$ and $d(a,B'') \geq
  |B''|-\delta n$ holds for all but at most $\delta n$ vertices $a\in A''$.
  Thus we already have (P2') and (P3') and also very nearly (P1') (but not
  quite, because it could be that $|B|<|A|$).

  We now modify $(A'',B'')$ to make sure that (P4') holds. Let $S\subseteq X$
  be the set of at most $2\delta n$ vertices with a deficient degree, i.e.,
  the set of vertices $x\in A''$ for which $d(x,A'') < |A''|-\delta n$ and of
  vertices $x\in B''$ for which $d(x,B'') < |B''| - \delta n$. Since by (S2)
  we have $\delta(G[X]) \geq n/k^4-\beta n$, we can
  partition $S$ into disjoint sets $S_A\cup S_B$ such that the vertices of
  $S_A$ have at
  least $k^{-4}n/3$ neighbours in $B''$ and the vertices of $S_B$ have at least
  $k^{-4}n/3$ neighbours in $A''$. Then we let $A' := A''\cup S_A\setminus S_B$
  and $B' := B''\cup S_B\setminus S_A$. Since we only moved around
  at most $2\delta n$ vertices, we still have
  $|A'|= n/k \pm 3\delta n$ and $|B'| = (k'-1)n/k \pm 3\delta n$,
  and we have $d(a,B') \geq |B'|-3\delta n$ for all but at most $3\delta n$
  vertices $a\in A'$, and similarly for the vertices in $B'$.
  However, we have gained the property that every vertex in $A$ has degree
  at least $k^{-4}n/4$ in $B$, and vice-versa.

  Next, we make sure that (P1') holds. The only issue is that it might be that
  $|B'|< |A'|$. If so, then 
  \[ (k'-1)n/k - 3\delta n\leq |B'| < |A'| \leq n/k+3\delta n \]
  implies $k'\leq 2+6k\delta n$. Since we further assumed that
  $k' \geq 2-4k\beta\geq 2-6k\delta n$, we see that in fact, we have
  $|A'|= (k'-1)n/k \pm 9\delta n$ and $|B'|= n/k\pm 9\delta
  n$, and so by switching $A'$ with $B'$ we obtain (P1'). Note that this
  swtiching cannot invalidate any of the symmetric properties (P2'), (P3'), or
  (P4').
  
  Finally, to obtain (P5'), we further modify these sets $A'$ and $B'$
  as follows: as long as both $\Delta(G[B']) > k^{-4}n/6$ and $|B'| >
  (\ceil{k'}-1)|A'|$, we move a vertex $b\in B'$ with $d(b,B') > k^{-4}n/6$
  from $B'$ to $A'$. Since we have $|B'| \leq (k'-1)|A'| + 9\delta n$, we do
  no move more than $9\delta n$ vertices during this process. Call the sets
  resulting from these modifications $A$ and $B$. Then it is easy to verify
  that (P1'--P5') hold with $18\delta$ instead of $\delta$
  -- note in particular that it is still the case that $|A|\leq|B|$ since
  we stop the process 
  the latest
  when $|B|=(\ceil{k'}-1)|A|\geq |A|$.
\end{proof}

The next lemma will take care of the stable sets where $k'\leq 2-4k\beta$.

\begin{lemma}\label{lemma:ac}
  Let $k\in \NN$ and $\beta>0$, where $\beta>0$ is sufficiently small. Let $G$
  be a graph of order $n\geq 3$ and let $X$ be $(k',k,\beta)$-stable in $G$ where
  $1\leq k' \leq 2-4k\beta$. Then for any two distinct vertices $x,y\in X$,
  there exists a Hamilton path in $G[X]$ whose endpoints are $x$ and $y$.
\end{lemma}
\begin{proof}
  This follows easily from Lemma~\ref{lemma:ham-connect}.
  Indeed, by (S1) the graph $G[X]$ has at most
  \[ |X| \leq k'n/k+ \beta n\leq (2-4k\beta)n/k+\beta n \leq 2n/k-3\beta n
  \] vertices.
  By (S2), every vertex in $G[X]$ has degree at least $n/k^4-\beta n
  \geq n/(2k^4)$
  and all but $\beta n$ vertices have degree at least $n/k-\beta n
  > (|X|+1)/2$.
  Thus, for $n/(2k^4)\leq j \leq (|X|+1)/2$, there are at most
  $\beta n< j-1$ vertices with degree at most $j$, while for $j <
  n/(2k^4)$, there are no vertices with degree at most $j$.
%  Let $S$ be the set of vertices in $X$ that do not have degree at least
%  $n/k-\beta n$ in $G[X]$. Note that by (S2) we have $|S| \leq \beta n$. 
%  Using (S1) and $k' \leq 2-15k\beta n$, we have
%  $|X|\leq k'n/k + \beta n \leq 2n/k - 14\beta n$.
%  Therefore, every vertex $x\in X\setminus S$ satisfies
%  \begin{equation}\label{eq:d1}
%    d(x,X) \geq n/k-\beta n \geq |X|/2+ 6\beta n.
%  \end{equation}
%
%  Let $x',y'\in X\setminus S$ be such that $xx'\in E(G)$ and $yy'\in
%  E(G)$ and such that $x,y,x',y'$ are all distinct. Such vertices must exist
%  because by (S2) the minimum degree of $G[X]$ is at least $n/k^4-\beta n
%  \geq |S| + 2$, if $\beta$ is sufficiently small. Let us
%  write $A := X\setminus (S\cup \{x,x',y,y'\})$ and $B := S
%  \setminus \{x,x',y,y'\}$, Note that $A\cup B = X\setminus \{x,x',y,y'\}$.
%
%  Since $|X\setminus A| \leq 2\beta n$, we have
%  \[  |X|/2 = |A|/2 + |X\setminus A|/2  \geq  |X\setminus A| + |A|/2 - \beta n. \]
%  As $A\subseteq X\setminus S$, it follows from this and~\eqref{eq:d1} that any two
%  vertices in $A$ have at least $10\beta n \geq 3|B|$ common neighbours in $A$.
%  Additionally, using (S2), every vertex of $B$ has at least $n/k^4-2\beta n -4
%  \geq 2|B|$ neighbours in $A$.
%
%  We now claim that $G[A\cup B]$ contains a path $P$ of length at most $4|B|-2$
%  such that the endpoints of $P$ lie in $A$ and such that
%  $B\subseteq V(P)$. Indeed, by the observations in the previous
%  paragraph, a path like this can be built as follows: first, for every vertex $x_i$ of
%  $B$, we may choose two neighbours $x_{2i}, x_{2i+1}\in A$ in such a way that
%  all chosen neighbours are distinct (since by (S3) each $x_i$ has more than
%  $2|B|$ neighbours in $A$); then, using the fact that any two vertices of $A$
%  have at least $3|B|$ common neighbours in $A$, we can connect each
%  $x_{2i+1}$ to $x_{2(i+1)}$ via a path of length two that avoids all other
%  involved vertices.
%
%  Since $|A\setminus V(P)| \geq |X|-5\beta n$, it follows from \eqref{eq:d1}
%  that $G[A\setminus V(P)]$ satisfies Dirac's condition and thus contains a
%  Hamilton cycle $C$. Since the endpoints $u,v$ of $P$ lie in $A\subseteq X\setminus S$, 
%  \eqref{eq:d1} and the pigeonhole principle imply that there exists an edge
%  $u'v'\in E(C)$ such that $uu'$ and $vv'$ are edges of $G$. Then $C' :=
%  (C-u'v') + uu' + vv' + P$ is a Hamilton cycle in $G[A\cup B]$. Finally, again
%  using~\eqref{eq:d1} and the pigeonhole principle, there exists an edge
%  $x''y''\in E(C')$ such that $x'x''$ and $y'y''$ are edges of $G$ (recall that
%  $x',y'\in X$). Then $P' := (C'-x''y'') + xx' + yy' + x'x'' + y'y''$ is a
%  Hamilton path in $G[X]$ with endpoints $x$ and $y$, as required.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lemma:connecting}]
  Let $G$ be a graph on $n$ vertices and assume that $X$ is
  $(k',k,\beta)$-stable in $G$ for some real number $k'\in [1,k]$,
  i.e., $X$ satisfies properties (S1), (S2) and (S3) from
  Definition~\ref{def:stable}. Throughout the proof, we will assume that
  $\delta>0$ and $\beta>0$ are sufficiently small constants, where $\beta$ is
  assumed to be much smaller than $\delta$, and that $n$ is sufficiently large.

  The case $k'\leq 2-4k\beta$ of the lemma follows immediately from
  Lemma~\ref{lemma:ac}. Therefore, we will from now on assume that $k'\geq
  2-4k\beta$. In particular there is a partition $(A,B)$ of $X$ satisfying the
  properties (P1'--P5') of Lemma~\ref{lemma:ag}. We now prove the different
  parts of Lemma~\ref{lemma:connecting}.

  \paragraph{Proof of (a).} Note that if $\delta$ is sufficiently small,
  which we assume, then the pair
  $(A,B)$ is automatically $(k^{-4}/7,\delta,\ceil{k'})$-good. Thus by
  Lemma~\ref{lemma:goodpair}, the graph $G[A,B]$ can be covered by $\ceil{k'}$
  cycles, which immediately yields statement (a) of
  Lemma~\ref{lemma:connecting}.

  \paragraph{Proof of (b).} To see that (b) holds, fix two vertices $x,y\in X$.
  By
  (P2'), (P3') and (P4'), it is straightforward to find vertices $a\in A$ and
  $b\in B$ such that $x,y,a,b$ are all distinct, such that $d(a,B)\geq |B|-\delta
  n$ and $d(b,A)\geq |A|-\delta n$, and such that there exist two vertex-disjoint
  paths of length at most two from $x$ to $a$ and from $y$ to $b$, respectively.
  Let $P_1$ and $P_2$ be these paths and let $A' := A\setminus (V(P_1)\cup
  V(P_2))$ and $B' := B\setminus (V(P_1)\cup V(P_2))$. Since $k'\geq 2-4k\beta
  n$, one can check that one of the pairs $(A',B')$ and $(B',A')$ is
  $(k^{-4}/8,2\delta,\ceil{k'})$-good (note that $(A',B')$ can fail to be good if
  $|B'|<|A'|$). By Lemma~\ref{lemma:goodpair} this allows us to cover $G[A'\cup
  B']$ with at most $\ceil{k'}$ cycles. At least one of these
  cycles, call it $C$, has length at least $|A'|/k\geq n/k^3$. Then, since
  $d(b,A)\geq |A|-\delta n$ and $d(a,B) \geq |B|-\delta n$, the pigeonhole
  principle implies that we can find an edge $uv$ in $C$ such that $au,bv$ are
  edges of $G$ that are not used by any of the cycles used for covering $A'\cup
  B'$. Then we can replace $C$ by the $x$-$y$-path $P_1 +  P_2 +  au+ bv
  +(C-uv)$.

  \paragraph{Proof of (c).} Here we assume that all but at most $n/k^3$
  vertices $x\in X$ satisfy $d(x,X) \geq |X|/k'$, and we need to show that
  $G[X]$ can be covered with $\ceil{k'}-1$ cycles. If we have $|B|\leq
  (\ceil{k'}-1)|A|$ then $(A,B)$ is a $(k^{-4}/7,\delta,\ceil{k'}-1)$-good pair
  and using Lemma~\ref{lemma:goodpair}, we are done immediately. 
  So assume that $|B|> (\ceil{k'}-1)|A|$. Then by property (P5'), we have
  $\Delta(G[B]) \leq n/(6k^4)$.

  We first claim that $G[B]$ contains a matching of size
  $|B|-(\ceil{k'}-1)|A|$. To see this, observe that if a vertex $x\in B$
  satisfies $d(x,X)\geq |X|/k'$ then \[ d(x,B) = d(x,X) - d(x,A) \geq |X|/k' -
  |A| = \frac{|B|-(k'-1)|A|}{k'}, \] using $|X| =|A|+ |B|$ for the last
  equality. Since there are at least $|B|-n/k^3 \geq n/(2k)$ vertices $x\in B$
  such that $d(x,X)\geq |X|/k'$, this implies \[ e(G[B]) \geq
  \frac{|B|-(k'-1)|A|}{4k^2}\cdot n. \] Since the maximum degree of $G[B]$ is
  at most $n/(6k^4)$, Vizing's theorem implies that the edges of $G[B]$ can be
  properly edge-colored with $n/(5k^4)$ colors. This in turn means that $G[B]$
  contains a matching of size at least \[ \frac{e(G[B])}{n/(5k^4)} \geq
  |B|-(k'-1)|A| \geq |B| - (\ceil{k'}-1)|A|, \] as claimed.

  Denote by $M$ any matching of size $|B|-(\ceil{k'}-1)|A|$ in $G[B]$. Note
  that by (P1') we have $|M| \leq |B|-(k'-1)|A| \leq k\delta n$. By (P4') each
  vertex in $B$ has at least $n/(7k^3) \geq 5|M|$ neighbours in $A$. Similarly,
  each vertex of $A$ has at least $n/(7k^3)-\delta n \geq 5|M|$ neighbours in
  $B$. Using these properties, we can now greedily find a system of $|M|$
  vertex-disjoint paths $P_1,\dotsc,P_{|M|}$ of length four with the following
  properties: each $P_i$ contains one edge of $M$ and visits exactly three
  vertices in $B$ and two vertices in $A$; moreover, the endpoints of $P_i$ are
  vertices $a_i\in A$ and $b_i\in B$ such that $d(a_i,B)\geq |B|-\delta n$ and
  $d(b_i,A)\geq |A|-\delta n$.

  Let $S := V(P_1)\cup \dotsb \cup V(P_{|M|})$.
  We will use a probabilistic
  argument to show that there exists a partition of $B$ into disjoint sets
  $B_1$ and $B_2$ such that the pairs $(A,B_1)$ and $(A\setminus S,
  B_2\setminus S)$ are $(k^{-5}/30,\delta,\ceil{k'}-2)$-good and
  $(k^{-5}/30,\delta,1)$-good, respectively. If we manage to do so, it will
  be easy to 
  complete the proof. Indeed, by Lemma~\ref{lemma:goodpair} we will be able to
  cover $G[A,B_1]$ with $\ceil{k'}-2$ cycles and cover
  $G[A\setminus S,B_2\setminus S]$ by a single cycle $C$. Then it follows from
  Lemma~\ref{obs} applied to $C,P_1,\dotsc,P_{|M|}$ that we can in fact
  cover $G[A,B_2]$ by a single cycle, meaning that we can cover $G[A,B]$ with
  $\ceil{k'}-1$ cycles, as required.

  It remains for us to show how to obtain $B_1$ and $B_2$. Let $B_1 \subseteq
  B\setminus S$ be a subset of $B\setminus S$ chosen uniformly at random among
  all subsets of size $(\ceil{k'}-2)|A|$ and let $B_2 := B\setminus B_1$. Note
  that since $|M|=|B|-(\ceil{k'}-1)|A|$, we have
  \[ |B_2| = |B|- (\ceil{k'}-2)|A| = |M| + |A|. \] 
  We claim that with positive probability, the pairs $(A,B_1)$ and $(A\setminus
  S, B_2\setminus S)$ are $(k^{-5}/30,\delta,\ceil{k'}-2)$-good and
  $(k^{-5}/30,\delta,1)$-good, respectively. First of all, both pairs satisfy
  (P1). For $(A,B_1)$ this is clear since
  $|B_1|=(\ceil{k'}-2)|A|$.
  For $(A\setminus S, B_2\setminus S)$,
  we have
  \[ |B_2\setminus S| = |B_2| - 3|M| = |A| -2|M| = |A\setminus S|, \]
  since every path $P_i$ uses three vertices of $B_2$ and two vertices of $A$.
  Properties (P2) and (P3) hold because of (P2') and (P3'). Finally, using
  Chernoff bounds we may show that (P4) holds for both
  pairs with positive probability. For example, for the pair
  $(A\setminus S, B_2\setminus S)$, we proceed as follows: for $a\in A$, the degree
  $d(a,B_2\setminus S)$ is distributed hypergeometrically with mean
  \[\mathbf E[d(a,B_2\setminus S)] \geq \frac{n}{7k^4} \cdot \frac{|B_2\setminus S|}{|B|}
  \geq \frac{n}{15k^5}, \]
  using $|B_2\setminus S| \geq |A|-|S| \geq n/(2k)$. Then the required bound
  on the probability that some $a\in A$ satisfies $d(a,B_2)< n/(30k^5)$ follows from
  the Chernoff and union bounds.
  On the other hand, we have $d(b,A\setminus S) \geq n/(7k^4) - |S| \geq n/(8k^4)$
  for all $b\in B_2$ deterministically. The argument for $(A,B_1)$ is similar.
\end{proof}

\begin{thebibliography}{10}

\bibitem{All}
Peter Allen.
\newblock Minimum degree conditions for cycles.
\newblock Unpublished.

\bibitem{Alo1986}
Noga Alon.
\newblock The longest cycle of a graph with a large minimal degree.
\newblock {\em J. Graph Theory}, 10(1):123--127, 1986.

\bibitem{BBG+2014}
József Balogh, János Barát, Dániel Gerbner, András Gyárfás, and
  Gábor~N. Sárközy.
\newblock Partitioning $2$-edge-colored graphs by monochromatic paths and
  cycles.
\newblock {\em Combinatorica}, 34:507--526, 2014.

\bibitem{BS2009a}
Fabricio~S. Benevides and Jozef Skokan.
\newblock The 3-colored {R}amsey number of even cycles.
\newblock {\em J. Combin. Theory Ser. B}, 99:690--708, 2009.

\bibitem{Ber1973}
Claude Berge.
\newblock {\em Graphs and Hypergraphs}.
\newblock North-Holland, Amsterdam, second edition, 1973.

\bibitem{Bol1978}
Béla Bollobás.
\newblock {\em Extremal {G}raph {T}heory}.
\newblock Academic Press, London, 1978.

\bibitem{BH1989}
Béla Bollobás and Roland Häggkvist.
\newblock The circumference of a graph with a given minimal degree.
\newblock In A.~Baker, B.~Boll\'obas, and A.~Hajnal, editors, {\em A Tribute to
  Paul Erdős}. Cambridge University Press, 1989.

\bibitem{BHP2012}
Julia Böttcher, Jan Hladký, and Diana Piguet.
\newblock The tripartite {R}amsey number for trees.
\newblock {\em J. Graph Theory}, 69(3):264--300, 2012.

\bibitem{CDK2011}
Phong Chau, Louis DeBiasio, and Henry~A. Kierstead.
\newblock P\'osa's conjecture for graphs of order at least $2\cdot 10^8$.
\newblock {\em Random Structures Algorithms}, 39:507--525, 2011.

\bibitem{Dir1952}
Gabriel~A. Dirac.
\newblock Some theorems on abstract graphs.
\newblock {\em Proc. London Math. Soc.}, s3-2(1):69--81, 1952.

\bibitem{Doe2011}
Benjamin Doerr.
\newblock Analyzing randomized search heuristics: tools from probability
  theory.
\newblock In A.~Auger and B.~Doerr, editors, {\em Theory of Randomized Search
  Heuristics}. World Scientific, Singapore, 2011.

\bibitem{EM1989}
Yoshimi Egawa and Takashi Miyamoto.
\newblock The longest cycles in a graph {$G$} with minimum degree at least
  {$|G|/k$}.
\newblock {\em J. Combin. Theory Ser. B}, 46(3):356--362, 1989.

\bibitem{EKKT1995}
Hikoe Enomoto, Atsushi Kaneko, Mekkia Kouider, and Zsolt Tuza.
\newblock Degree sums and covering cycles.
\newblock {\em J.~Graph Theory}, 20(4):419--422, 1995.

\bibitem{EKT1988}
Hikoe Enomoto, Atsushi Kaneko, and Zsolt Tuza.
\newblock {$P_3$}-factors and covering cycles in graphs of minimum degree
  $n/3$.
\newblock In {\em Combinatorics} (Colloq. Math. Soc. János Bolyai 52, Eger), 213--220. North-Holland, Amsterdam,
  1988.

\bibitem{Erd1964}
Paul Erd\H{o}s.
\newblock {\em Theory of graphs and its applications}.
\newblock Czech Acad. Sci. Publ., Prague, 1964.

\bibitem{FK1996}
Genghua Fan and Henry~A. Kierstead.
\newblock Hamiltonian square-paths.
\newblock {\em J. Combin. Theory Ser. B}, 67:167--182, 1996.

\bibitem{FL2007}
Agnieszka Figaj and Tomasz \L{}uczak.
\newblock The {R}amsey number for a triple of long even cycles.
\newblock {\em J. Combin. Theory Ser. B}, 97(4):584--596, 2007.

\bibitem{HS1970}
András Hajnal and Endre Szemerédi.
\newblock Proof of a conjecture of {P}. {E}rdős.
\newblock In P.~Erdős, A.~Rényi, and V.~T. Sós, editors, {\em Combinatorial
  theory and its applications}, volume~2, pages 601--623. North-Holland,
  Amsterdam, 1970.

\bibitem{Kom1999}
J{\'{a}}nos Koml{\'{o}}s.
\newblock The blow-up lemma.
\newblock {\em Combin. Probab. Comput.}, 8:161--176, 1999.

\bibitem{KSS1995}
J{\'{a}}nos Koml{\'{o}}s, G{\'{a}}bor~N. S{\'{a}}rk{\"{o}}zy, and Endre
  Szemer{\'{e}}di.
\newblock Proof of a packing conjecture of {B}ollobás.
\newblock {\em Combin. Probab. Comput.}, 4:241--255, 1995.

\bibitem{KSS1996}
J{\'{a}}nos Koml{\'{o}}s, G{\'{a}}bor~N. S{\'{a}}rk{\"{o}}zy, and Endre
  Szemer{\'{e}}di.
\newblock The blow-up lemma.
\newblock {\em Combinatorica}, 17:109--123, 1996.

\bibitem{KSS1996a}
J{\'{a}}nos Koml{\'{o}}s, G{\'{a}}bor~N. S{\'{a}}rk{\"{o}}zy, and Endre
  Szemer{\'{e}}di.
\newblock On the square of a {H}amiltonian cycle in dense graphs.
\newblock {\em Random Structures Algorithms}, 9:193--211, 1996.

\bibitem{KSS1998}
J{\'{a}}nos Koml{\'{o}}s, G{\'{a}}bor~N. S{\'{a}}rk{\"{o}}zy, and Endre
  Szemer{\'{e}}di.
\newblock Proof of the {S}eymour conjecture for large graphs.
\newblock {\em Ann. Comb.}, 2(1):43--60, 1998.

\bibitem{KS1996}
J{\'{a}}nos Koml{\'{o}}s and Miklós Simonovits.
\newblock Szemer\'edi's regularity lemma and its applications in graph theory.
\newblock In D.~Miklós, T.~Sz\H{o}nyi, and V.~T. Sós, editors, {\em
  Combinatorics, Paul Erd\H os is Eighty, 2}, Bolyai Soc. Math. Stud., pages
  295--352, 1996.

\bibitem{Kou1994}
Mekkia Kouider.
\newblock Covering vertices by cycles.
\newblock {\em J.~Graph Theory}, 18(8):757--776, 1994.

\bibitem{KL1996}
Mekkia Kouider and Zbigniew Lonc.
\newblock Covering cycles and $k$-term degree sums.
\newblock {\em Combinatorica}, 16(3):407--412, 1996.

\bibitem{LS2017}
Richard Lang and Maya Stein.
\newblock Local colourings and monochromatic partitions in complete bipartite
  graphs.
\newblock {\em European J. Combin.}, 60:42--54, 2017.

\bibitem{LSS2010}
Ian Levitt, Gábor~N. S\'ark\"ozy, and Endre Szemer\'edi.
\newblock How to avoid using the {R}egularity {L}emma: {P}\'osa’s conjecture
  revisited.
\newblock {\em Discrete Math.}, 310:630--641, 2010.

\bibitem{L1999}
Tomasz \L{}uczak.
\newblock $r(c_n,c_n,c_n)\le (4+o(1))n$.
\newblock {\em J. Combin. Theory Ser. B}, 75:174--187, 1999.

\bibitem{NS2006}
Vladimir Nikiforov and Richard~H. Schelp.
\newblock Cycle lengths in graphs with large minimum degree.
\newblock {\em J. Graph Theory}, 52(2):157--170, 2006.

\bibitem{SSS2013}
Gábor~N. S\'ark\"ozy, Stanley~M. Selkow, and Fei Song.
\newblock An improved bound for vertex partitions by connected monochromatic
  k-regular graphs.
\newblock {\em J. Graph Theory}, 73:127--145, 2013.

\bibitem{Sey1974}
Paul Seymour.
\newblock Problem section.
\newblock In T.~P. McDonough and V.~C. Mavron, editors, {\em Combinatorics} (British Combinatorial Conference 1973), 201--202. Cambridge University Press,
1974.

\bibitem{Sim1968}
Miklós Simonovits.
\newblock A method for solving extremal problems in graph theory, stability
  problems.
\newblock In {\em Theory of Graphs} (Tihany), pages 279--319. Academic Press, New York,
  1968.

\bibitem{Sze1976}
Endre Szemerédi.
\newblock Regular partitions of graphs.
\newblock In {\em Problèmes Combinatoires et Théorie des Graphes} (Colloques internationaux CNRS 260, Orsay), pages
  399--401, 1976.

\end{thebibliography}

\end{document}