# Hamiltonicity of graphs perturbed by a random regular graph

Alberto Espuny Díaz<EMAIL_ADDRESS>and  António Girão
<EMAIL_ADDRESS>Institut für Mathematik, Technische Universität Ilmenau,
98684 Ilmenau, Germany.  Mathematical Institute, University of Oxford, Oxford
OX2 6GG, United Kingdom.

###### Abstract.

We study Hamiltonicity and pancyclicity in the graph obtained as the union of
a deterministic $n$-vertex graph $H$ with $\delta(H)\geq\alpha n$ and a random
$d$-regular graph $G$, for $d\in\\{1,2\\}$. When $G$ is a random $2$-regular
graph, we prove that a.a.s. $H\cup G$ is pancyclic for all $\alpha\in(0,1]$,
and also extend our result to a range of sublinear degrees. When $G$ is a
random $1$-regular graph, we prove that a.a.s. $H\cup G$ is pancyclic for all
$\alpha\in(\sqrt{2}-1,1]$, and this result is best possible. Furthermore, we
show that this bound on $\delta(H)$ is only needed when $H$ is ‘far’ from
containing a perfect matching, as otherwise we can show results analogous to
those for random $2$-regular graphs. Our proofs provide polynomial-time
algorithms to find cycles of any length.

This project has received partial funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement no. 786198, A. Espuny Díaz). The research leading
to these results was also partially supported by the Carl Zeiss Foundation (A.
Espuny Díaz) and the EPSRC grant no. EP/N019504/1 (A. Girão) and EPSRC grant
no. EP/V007327/1 (A. Girão).

##  1\. Introduction

Two classical areas of research in graph theory are that which deals with
extremal results, and that which studies properties of random structures. In
the former area, one often looks for sufficient conditions to guarantee that a
graph satisfies a certain property. An example of such a result is the well-
known Dirac’s theorem [16], which states that any graph $G$ on $n\geq 3$
vertices with minimum degree at least $n/2$ contains a Hamilton cycle (that
is, a cycle which contains all vertices of $G$). In the latter, one considers
a random structure, chosen according to some distribution, and studies whether
it satisfies a given property with sufficiently high probability. For
instance, the binomial random graph $G_{n,p}$ (where $G_{n,p}$ is obtained by
considering a vertex set of size $n$ and adding each of the possible
$\bigl{(}\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{2}\kern-1.00006pt\bigr{)}$
edges with probability $p$ and independently of each other) is known to
contain a Hamilton cycle asymptotically almost surely (a.a.s.) whenever
$p\geq(1+\epsilon)\log n/n$ [23], while if $p\leq(1-\epsilon)\log n/n$, then
a.a.s. the graph is not even connected.

A more recent area of research at the interface of extremal combinatorics and
random graph theory is that of _randomly perturbed graphs_. The general
setting is as follows. One considers an arbitrary graph $H$ from some class of
graphs (usually, given by a minimum degree condition) and a random graph $G$,
and asks whether the union of $H$ and $G$ satisfies a desired property a.a.s.
This can be seen as a way to bridge between the two areas described above.
Indeed, suppose that $H$ is any $n$-vertex graph with minimum degree
$\delta(H)\geq\alpha n$ and $G=G_{n,p}$ is a binomial random graph (on the
same vertex set as $H$), and consider the property of being Hamiltonian (that
is, containing a Hamilton cycle). If $\alpha\geq 1/2$, then Dirac’s theorem
guarantees that $H\cup G$ is Hamiltonian, for all values of $p$. If, on the
other hand, $\alpha=0$, $H$ could be the empty graph, so we are left simply
with the random graph $G$. The relevant question, then, is whether, for all
$\alpha\in(0,1/2)$, any graph $H$ with minimum degree $\alpha n$ is
sufficiently ‘close’ to Hamiltonicity that adding a random graph $G$ (which is
itself not a.a.s. Hamiltonian) will yield Hamiltonicity. In particular, the
goal is to determine whether the range of $p$ for which this holds is
significantly larger than the range for $G_{n,p}$ itself.

The randomly perturbed graph model was introduced by Bohman, Frieze and Martin
[5], who studied precisely the problem of Hamiltonicity. They proved that, for
any constant $\alpha>0$, if $H$ is an $n$-vertex graph with
$\delta(H)\geq\alpha n$, then a.a.s. $H\cup G_{n,p}$ is Hamiltonian for all
$p\geq C(\alpha)/n$. Note, in particular, that this increases the range of $p$
given by the random graph model. This result was very recently generalised by
Hahn-Klimroth, Maesaka, Mogge, Mohr and Parczyk [19] to allow $\alpha$ to tend
to $0$ with $n$ (that is, to consider graphs $H$ which are not dense),
similarly improving the range of $p$. In a different direction, the results of
Bohman, Frieze and Martin [5] about Hamiltonicity were generalised by
Krivelevich, Kwan and Sudakov [24] to pancyclicity, that is, the property of
containing cycles of all lengths between $3$ and $n$.

Other properties that have been studied in the context of randomly perturbed
graphs are, e.g., the existence of powers of Hamilton cycles [11, 8, 17, 2,
28], $F$-factors [3, 20, 9, 10], spanning bounded degree trees [25, 7] and
(almost) unbounded degree trees [22], or general bounded degree spanning
graphs [8]. The model of randomly perturbed graphs has also been extended to
other settings. For instance, Hamiltonicity has been studied in randomly
perturbed directed graphs [5, 24], hypergraphs [24, 27, 4, 21, 12] and
subgraphs of the hypercube [13]. A common phenomenon in randomly perturbed
graphs is that, by considering the union with a dense graph (i.e., with linear
degrees), the threshold for the probabilities of different properties is
significantly lower than that of the classical $G_{n,p}$ model.

In this paper, we study the analogous problem where the random graph that is
added to a deterministic graph is a random _regular_ graph (a graph is
_regular_ when all its vertices have the same degree). To be more precise, we
will consider a given $n$-vertex graph $H$ with $\delta(H)\geq\alpha n$, and
we will study the Hamiltonicity and pancyclicity of $H\cup G$, where $G$ is a
random $d$-regular graph, for some $d\in\mathbb{N}$. We write $G_{n,d}$ for a
graph chosen uniformly at random from the set of all $d$-regular graphs on $n$
vertices (we implicitly assume that $nd$ is even throughout). The model of
random regular graphs, though harder to analyse than the binomial model, has
been studied thoroughly. In particular, it is a well-known fact that $G_{n,d}$
is a.a.s. Hamiltonian for all $3\leq d\leq n-1$ [29, 30, 15, 26]. It follows
that, for all $d\geq 3$, $H\cup G_{n,d}$ is a.a.s. Hamiltonian independently
of $H$, so the problem we consider only becomes relevant for $d\in\\{1,2\\}$.
For more information about random regular graphs, we recommend the survey of
Wormald [31].

It turns out that the behaviour of the problem is quite different in each of
these two cases. When we consider $G=G_{n,2}$ (also referred to as a random
$2$-factor), we obtain a result similar to those obtained in the binomial
setting: for every constant $\alpha>0$, if $H$ is an $n$-vertex graph with
$\delta(H)\geq\alpha n$, then a.a.s. $H\cup G$ is Hamiltonian. Even more, we
can prove that, in this case, a.a.s. $H\cup G$ is pancyclic, and also extend
the range of $\alpha$ for which this holds to some function of $n$ which tends
to $0$.

######  Theorem 1.1.

Let $\alpha=\omega((\log n/n)^{1/4})$, and let $H$ be an $n$-vertex graph with
$\delta(H)\geq\alpha n$. Then, a.a.s. $H\cup G_{n,2}$ is pancyclic.

In contrast to this, when we consider $G=G_{n,1}$ (that is, a random perfect
matching), there is a particular value $\alpha^{*}<1/2$ such that, for all
$\alpha>\alpha^{*}$, if $H$ is an $n$-vertex graph with $\delta(H)\geq\alpha
n$, then a.a.s. $H\cup G$ is Hamiltonian.

######  Theorem 1.2.

For all $\epsilon>0$, the following holds. Let
$\alpha\coloneqq(1+\epsilon)(\sqrt{2}-1)$, and let $H$ be an $n$-vertex graph
with $\delta(H)\geq\alpha n$. Then, a.a.s. $H\cup G_{n,1}$ is pancyclic.

This result is best possible. Indeed, for every $\alpha<\sqrt{2}-1$, there
exist graphs $H$ with $\delta(H)\geq\alpha n$ such that $H\cup G_{n,1}$ is not
a.a.s. Hamiltonian. As we will discuss later (see Section 5), the main
extremal construction of $H$ for the lower bound is a complete unbalanced
bipartite graph. One key feature of this example is that $H$ does not contain
a very large matching. Indeed, when we further impose that $H$ contains an
(almost) perfect matching, we can obtain the following result analogous to
Theorem 1.1.

######  Theorem 1.3.

Let $\alpha=\omega((\log n/n)^{1/4})$, and let $H$ be an $n$-vertex graph with
$\delta(H)\geq\alpha n$ which contains a matching $M$ which covers
$n-o(\alpha^{2}n)$ vertices. Then, a.a.s. $H\cup G_{n,1}$ is pancyclic.

The rest of the paper is organised as follows. In Section 2 we present our
notation and some preliminary results which will be useful for us, and in
Section 3 we prove some properties of $G_{n,1}$ and $G_{n,2}$ regarding their
edge distribution and component structure which are crucial for our proofs. We
devote Section 4 to proving Theorems 1.1 and 1.3, and defer the proof of
Theorem 1.2 to Section 5. Finally, we discuss some possible extensions in
Section 6.

##  2\. Preliminaries

###  2.1. Notation

For any $n\in\mathbb{Z}$, we denote $[n]\coloneqq\\{i\in\mathbb{Z}:1\leq i\leq
n\\}$ and $[n]_{0}\coloneqq\\{i\in\mathbb{Z}:0\leq i\leq n\\}$. In particular,
$[0]=\varnothing$. Given any $a,b,c\in\mathbb{R}$, we write $c=a\pm b$ if
$c\in[a-b,a+b]$. Whenever we use a hierarchy, the constants are chosen from
right to left. To be more precise, when claiming that a statement holds for
$0<a\ll b\leq 1$, we mean that it holds for all $0<b\leq 1$ and all $0<a\leq
f(b)$, for some unspecified non-decreasing function $f$. For our asymptotic
statements we often use the standard $\mathcal{O}$ notation; when doing so, we
always understand that the functions are non-negative.

Throughout this paper, the word _graph_ will refer to simple, undirected
graphs. Whenever we consider graphs with loops or parallel edges, we will call
them _multigraphs_. Whenever we consider a (multi)graph $G$ on $n$ vertices,
we implicitly assume that $V(G)=[n]$ (in particular, all graphs are labelled).

Given any (multi)graph $G=(V,E)$ and any two (not necessarily disjoint) sets
$A,B\subseteq V$, we denote the (multi)set of edges of $G$ with both endpoints
in $A$ by $E_{G}(A)$, and the (multi)set of edges with one endpoint in $A$ and
one in $B$ by $E_{G}(A,B)$. If $A=\\{a\\}$ is a singleton, for simplicity we
will write $E_{G}(a,B)\coloneqq E_{G}(\\{a\\},B)$, and similarly in the rest
of the notation. We denote $e_{G}(A)\coloneqq|E_{G}(A)|$ and
$e_{G}(A,B)\coloneqq|E_{G}(A,B)|$. We write $G[A]\coloneqq(A,E_{G}(A))$ for
the subgraph of $G$ induced by $A$. If $A$ and $B$ are disjoint, we write
$G[A,B]\coloneqq(A\cup B,E_{G}(A,B))$ for the bipartite subgraph of $G$
induced by $A$ and $B$. Given two (multi)graphs $G$ and $H$, we write $G\cup
H\coloneqq(V(G)\cup V(H),E(G)\cup E(H))$, and if $V(H)\subseteq V(G)$, we
write $G\setminus H\coloneqq(V(G),E(G)\setminus E(H))$. We denote
$G-A\coloneqq G[V\setminus A]$. We will write $A\triangle B\coloneqq(A\cup
B)\setminus(A\cap B)$ for the symmetric difference of $A$ and $B$. We will
often abbreviate edges $e=\\{x,y\\}$ as $e=xy$; recall, however, that edges
are sets of vertices, and will be used as such throughout. Given any vertex
$x\in V$, we let $d_{G}(x)\coloneqq|\\{e\in E:x\in e\\}|+|\\{e\in E:e=xx\\}|$
denote its _degree_ in $G$ (that is, loops count twice towards the degree of a
vertex). We write $\Delta(G)$ and $\delta(G)$ for the maximum and minimum
vertex degrees in $G$, respectively. We write $N_{G}(x)$ for the neighbourhood
of $x$ in $G$, that is, the set of vertices $y\in V$ such that $xy\in E$.
Given any set $A\subseteq V$, we denote $N_{G}(A)\coloneqq\bigcup_{x\in
A}N_{G}(x)$. Given any set of edges $E^{\prime}$, we write
$V(E^{\prime})\coloneqq\bigcup_{e\in E^{\prime}}e$.

A _path_ $P$ can be seen as a set of vertices which can be labelled in such a
way that there is an edge between any two consecutive vertices. Equivalently,
they can be defined by the corresponding set of edges. We will often consider
isolated vertices as a degenerate case of paths. If the _endpoints_ of $P$
(that is, the first and last vertices, according to the labelling) are $x$ and
$y$, we often refer to $P$ as an $(x,y)$-path. We refer to all vertices of a
path $P$ which are not its endpoints as _internal_ vertices. The _length_ of a
path is equal to the number of edges it contains (the same definition holds
for cycles). The _distance_ between two vertices $x,y$ in a (multi)graph $G$,
denoted by $\operatorname{dist}_{G}(x,y)$, is the length of the shortest
$(x,y)$-path $P\subseteq G$ (if there is no such path, the distance is said to
be infinite). Given any two sets of vertices $A,B\subseteq V(G)$, we define
$\operatorname{dist}_{G}(A,B)\coloneqq\min_{x\in A,y\in
B}\operatorname{dist}_{G}(x,y)$.

Whenever we consider asymptotic statements, we will use the convention of
abbreviating a sequence of graphs $\\{G_{i}\\}_{i\in\mathbb{N}}$ such that
$|V(G_{i})|\to\infty$ by simply writing that $G$ is an $n$-vertex graph (and
implicitly understanding that $n\to\infty$). In this setting, we say that an
event $\mathcal{E}$ holds _asymptotically almost surely_ (a.a.s. for short) if
$\mathbb{P}[\mathcal{E}]=1-o(1)$. We will ignore rounding issues whenever this
does not affect the arguments.

###  2.2. The configuration model

In order to study random regular graphs, one of the most useful tools is the
_configuration model_ , first introduced by Bollobás [6], which gives a
process that samples $d$-regular graphs uniformly at random. In its simplest
form, the process works as follows. For each $i\in[n]$, consider a set of $d$
vertices $x_{i,1},\ldots,x_{i,d}$. Then, choose a uniformly random perfect
matching $M$ covering the set $\\{x_{i,j}:i\in[n],j\in[d]\\}$. Now, generate a
multigraph $G=G(M)=([n],E)$ where, for each edge
$x_{i,j}x_{i^{\prime},j^{\prime}}\in M$, an edge $ii^{\prime}$ is added to $E$
(if $i=i^{\prime}$, this creates a loop). For any $i\in[n]$, we will refer to
$\\{x_{i,j}:j\in[d]\\}$ as the _extended set_ of $i$. Similarly, for any
$A\subseteq[n]$, we will refer to $\\{x_{i,j}:i\in A,j\in[d]\\}$ as the
_extended set_ of $A$.

Whenever we produce a (multi)graph $G$ following the process above, we will
write $G\sim\mathcal{C}_{n,d}$. We will write $M\sim\mathcal{C}^{*}_{n,d}$ for
the perfect matching $M$ such that $G=G(M)$. In order to easily distinguish
both models, we will refer to $M\sim\mathcal{C}^{*}_{n,d}$ as a
_configuration_. By abusing notation, we will also sometimes write
$\mathcal{C}^{*}_{n,d}$ to denote the set of all configurations with
parameters $n$ and $d$. Observe that, in particular, for every $n$-vertex
$d$-regular multigraph $G$, there exists at least one configuration
$M\in\mathcal{C}_{n,d}^{*}$ such that $G=G(M)$.

Given any two configurations $M,M^{\prime}\in\mathcal{C}^{*}_{n,d}$, we write
$M\sim M^{\prime}$ if there exist $u_{1}u_{2},v_{1}v_{2}\in M$ such that
$M^{\prime}=(M\setminus\\{u_{1}u_{2},v_{1}v_{2}\\})\cup\\{u_{1}v_{1},u_{2}v_{2}\\}$.
The following lemma bounds the probability that certain variables on
configurations deviate from their expectation (see, e.g., [14, Lemma 4.3]).

######  Lemma 2.1.

Let $d\in\mathbb{N}$ be fixed. Let $c>0$ and let $X$ be a random variable on
$\mathcal{C}^{*}_{n,d}$ such that, for every pair of configurations $M\sim
M^{\prime}$, we have $|X(M)-X(M^{\prime})|\leq c$. Then, for all
$t\in\mathbb{N}$,

$\mathbb{P}[|X-\mathbb{E}[X]|\geq t]\leq
2\mathrm{e}^{-\frac{t^{2}}{2ndc^{2}}}.$

Whenever sampling $G\sim\mathcal{C}_{n,d}$, the process described above may
yield a multigraph with both loops and parallel edges. (Of course, this does
not apply to the case $d=1$, where we simply generate a uniformly random
perfect matching.) However, upon conditioning on the event that $G$ is a
simple graph, such a graph is a uniformly random $d$-regular graph. The
following is by now a well-established fact (see, e.g., [31, section 2.2]):

######  Lemma 2.2.

Let $d\in\mathbb{N}$ be fixed, and let $G\sim\mathcal{C}_{n,d}$. If $n$ is
sufficiently large, then

$\mathbb{P}[G\text{ is simple}]\geq\mathrm{e}^{-d^{2}/4}.$

##  3\. Properties of random regular graphs of low degree

We will need to have bounds on the number of components of random $2$-factors
(note that every $2$-regular graph is a union of vertex-disjoint cycles), as
well as the number of cycles in the union of a (not necessarily spanning)
matching and a random perfect matching.

######  Lemma 3.1.

The following statements hold.

  1. $(\mathrm{i})$

A.a.s. the number of components of $G_{n,2}$ is at most $\log^{2}n$.

  2. $(\mathrm{ii})$

Let $M$ be any (not necessarily perfect) matching on $[n]$. Then, a.a.s.
$M\cup G_{n,1}$ contains at most $\log^{2}n$ cycles, and its number of
components is at most $n/2-|M|+\log^{2}n$.

###### Proof.

We are going to generate a multigraph $G\sim\mathcal{C}_{n,2}$ according to
the configuration model (for the proof of $(\mathrm{ii})$, this will be
conditioned on certain edges being present). For this, it is important to note
that a uniformly random perfect matching on any set $A$ of $2n$ vertices (that
is, a configuration $M\sim\mathcal{C}_{n,2}^{*}$) can be obtained iteratively
by choosing $n$ edges in $n$ steps. For step $i$, let $B_{i}$ be the set of
all vertices which are covered by the edges of the first $i-1$ steps. Then,
choose any vertex $x_{i}\in A\setminus B_{i}$, and choose a neighbour
$y_{i}\in A\setminus(B_{i}\cup\\{x_{i}\\})$ for $x_{i}$ uniformly at random.
The choice of $x_{i}$ in each step of this process can be made arbitrarily. If
we generate a random perfect matching on $2n$ vertices conditioned on $m$
given pairs being present in this matching, we can follow the process above
starting at step $m+1$, assuming that the given $m$ edges were chosen in the
first $m$ steps of the process. For our proofs, we are going to generate a
uniformly random configuration following this process.

For each $j\in[n]$, let $A_{j}$ be the extended set of $j$, and let
$A\coloneqq\bigcup_{j\in[n]}A_{j}$. Consider first the proof of
$(\mathrm{i})$. In the $i$-th step, the choice of the vertex $x_{i}$ will be
made as follows: if $i\geq 2$ and for the unique $j\in[n]$ such that
$y_{i-1}\in A_{j}$ we have that $|A_{j}\cap B_{i}|=1$, then let $x_{i}$ be the
unique vertex in $A_{j}\setminus\\{y_{i-1}\\}$; otherwise, let $x_{i}\in
A\setminus B_{i}$ be arbitrary. Roughly speaking, this choice of $x_{i}$ at
each step means that we are revealing the edges of $G\sim\mathcal{C}_{n,2}$ in
such a way that we reveal all edges of each connected component of $G$ before
moving on to the next one. In particular, we only start a new component at
step $i+1$ when the randomly chosen vertex $y_{i}$ lies in the unique $A_{j}$
where exactly one vertex had already been picked. Whenever this happens, we
say that the process has _finished_ a component at step $i$.

For each $i\in[n]$, let $X_{i}$ be an indicator random variable which takes
value $1$ whenever the process finishes a component at step $i$, and $0$
otherwise. Observe that, since $y_{i}$ is chosen uniformly at random, for each
$i\in[n]$ we have that

$\mathbb{P}[X_{i}=1]=\frac{1}{2n-2i+1}.$

The total number of components $X$ of $G$ is then given by the sum of these
indicator variables. In particular, for $n$ sufficiently large it follows that

$\mathbb{E}[X]=\sum_{i=1}^{n}\frac{1}{2n-2i+1}\leq 2\log n.$

The claim now follows immediately by Markov’s inequality and Lemma 2.2.

Consider now the proof of $(\mathrm{ii})$. First, extend the given matching
$M$ into a perfect matching $M^{\prime}$ arbitrarily. For each $j\in[n]$, let
$\sigma(j)$ be the unique $k\in[n]$ such that $\\{j,k\\}\in M^{\prime}$. Now,
consider the extended set $A$ and, for each $\\{j,k\\}\in M^{\prime}$, add the
pair $x_{j,1}x_{k,1}$ to a matching $\tilde{M}$ on $A$, so we have that
$G(\tilde{M})=M^{\prime}$. We are going to obtain a configuration
$M^{\prime\prime}\sim\mathcal{C}_{n,2}^{*}$ conditioned on containing this
matching $\tilde{M}$. Observe that, since exactly one point in the extended
set of each vertex has been covered by $\tilde{M}$, a random matching on the
uncovered points corresponds to a random perfect matching on $[n]$. In
particular, $G(M^{\prime\prime})$ may contain some parallel edges (which
correspond to ‘isolated’ edges in $M^{\prime}\cup G_{n,1}$), but it cannot
contain any loops.

For each $i\in[n]\setminus[n/2]$, the choice of the vertex $x_{i}$ will be
made as follows: if $i\geq n/2+2$ and for the unique $j\in[n]$ such that
$y_{i-1}\in A_{j}$ we have that $|A_{\sigma(j)}\cap B_{i}|=1$, let $x_{i}$ be
the unique vertex in $A_{\sigma(j)}\setminus B_{i}$; otherwise, choose $x_{i}$
arbitrarily. Similarly to the proof of $(\mathrm{i})$, this allows us to count
the number of components of $G(M^{\prime\prime})$ (and, thus, of
$M^{\prime}\cup G_{n,1}$). Note that we only start a new component at step
$i+1$ if the randomly chosen $y_{i}$ lies in the unique (not completely
covered) $A_{j}$ such that $A_{\sigma(j)}$ was covered before the choice of
$y_{i}$. Whenever this happens, we say that the process has finished a
component at step $i$.

For each $i\in[n]\setminus[n/2]$, let $Y_{i}$ be a random variable which takes
value $1$ whenever the process finishes a component at step $i$, and $0$
otherwise, and let $Y$ be the number of components of $G(M^{\prime\prime})$.
As before, since $y_{i}$ is chosen uniformly at random, for each
$i\in[n]\setminus[n/2]$ we have that

$\mathbb{P}[Y_{i}=1]=\frac{1}{2n-2i+1},$

and it follows that a.a.s. $Y\leq\log^{2}n$. Each of these components is
either a cycle or an isolated pair of parallel edges. Finally, $M\cup G_{n,1}$
can be obtained by contracting parallel edges into a single edge and then
removing the edges of $M^{\prime}\setminus(M\cup G_{n,1})$ from
$G(M^{\prime\prime})$, and this never creates any new cycles, so the bound on
the number of cycles follows.

In order to bound the number of components of $M\cup G_{n,1}$, note that the
deletion of each edge of $M^{\prime}\setminus(M\cup G_{n,1})$ may create at
most one new component. Thus, a.a.s. the number of components of $M\cup
G_{n,1}$ is at most $\log^{2}n+(n/2-|M|)$. ∎

######  Remark 3.2.

The proof of Lemma 3.1$(\mathrm{ii})$ gives the following simple bound: if $M$
is any (not necessarily perfect) matching on $[n]$, then a.a.s. $|E(M)\cap
E(G_{n,1})|\leq\log^{2}n$.

The following edge-distribution property of $G_{n,1}$ and $G_{n,2}$ will also
be useful for us.

######  Lemma 3.3.

Let $\epsilon>0$ and $k=k(n)\leq n^{3}$. For each $i\in[k]$, let
$\alpha_{i}=\alpha_{i}(n)$ and $\beta_{i}=\beta_{i}(n)$ be such that
$\alpha_{i}\beta_{i}=\omega((\log n/n)^{1/2})$ and let
$A_{i},B_{i}\subseteq[n]$ be two not necessarily disjoint sets of vertices
with $|A_{i}|\geq\alpha_{i}n$ and $|B_{i}|\geq\beta_{i}n$. Let $G=G_{n,1}$ or
$G=G_{n,2}$. Then, a.a.s., for every $i\in[k]$, $A_{i}$ contains at least
$(1-\epsilon)\alpha_{i}\beta_{i}n$ vertices $z$ such that $N_{G}(z)\cap
B_{i}\neq\varnothing$.

###### Proof.

We will show how to prove the statement when $G=G_{n,2}$; the other case can
be shown in exactly the same way, but avoiding the reference to Lemma 2.2.

Let $G^{\prime}\sim\mathcal{C}_{n,2}$. Let $\mathcal{E}$ be the event that the
statement holds for $G^{\prime}$. First, fix some $i\in[k]$, let
$Z\coloneqq\\{z\in A_{i}:N_{G^{\prime}}(z)\cap B_{i}\neq\varnothing\\}$, and
let $X\coloneqq|Z|$. By using the configuration model, for each $z\in A_{i}$
and $n$ sufficiently large we have that

$\mathbb{P}[z\in Z]\geq\frac{2|B_{i}|-1}{2n-1}\geq(1-\epsilon/2)\beta_{i},$

which implies that $\mathbb{E}[X]\geq(1-\epsilon/2)\alpha_{i}\beta_{i}n$.

Now observe that any random variable on $d$-regular multigraphs obtained
according to the configuration model can also be seen as a random variable on
uniformly random configurations. In particular, since any pair of
configurations $M\sim M^{\prime}$ are equal except for their edges at four
vertices, it follows that, given any two configurations $M\sim M^{\prime}$, we
have $|X(M)-X(M^{\prime})|\leq 4$. Thus, by Lemma 2.1 we conclude that
$\mathbb{P}[X<(1-\epsilon)\alpha_{i}\beta_{i}n]\leq\mathrm{e}^{-\Omega(\alpha_{i}^{2}\beta_{i}^{2}n)}$.

By a union bound over all $i\in[k]$ and the bound on $\alpha_{i}\beta_{i}$ in
the statement, we conclude that

$\mathbb{P}[\mathcal{E}]\geq
1-\sum_{i=1}^{k}\mathrm{e}^{-\Omega(\alpha_{i}^{2}\beta_{i}^{2}n)}=1-o(1).$

Finally, by applying Lemma 2.2, we have that the statement holds a.a.s. for
$G=G_{n,2}$. ∎

##  4\. Randomly perturbing graphs by a $2$-factor

We can now prove Theorems 1.1 and 1.3 simultaneously. We note that we believe
the bound on $\delta(H)$ in the statements is far from optimal and, thus, we
make no effort to optimise the constants throughout.

We will let $G=G_{n,2}$ or $G=G_{n,1}$ and want to show that $H\cup G$ is
pancyclic. Our general strategy will be to first construct a special path $P$
which can be used to ‘absorb’ vertices into a given cycle. To be more precise,
we will set aside an arbitrary set of vertices of a suitable size and then
construct a path $P$ which avoids this set of vertices. Furthermore, we will
ensure that each of the vertices set aside forms a triangle with one of the
edges of $P$ (and each of the vertices does this with a different edge). Then,
by replacing the corresponding edge of $P$ by the path of length $2$ that
forms the triangle, we can incorporate each of the vertices set aside into the
path (thus ‘absorbing’ the vertex). This will allow us to have some control
over the length of the cycles which we can produce. Once we have constructed
the special path $P$, we will show that we can find an ‘almost’ spanning cycle
$C$ with $P\subseteq C$ which avoids the vertices that can be absorbed with
$P$. We can then use the cycle $C$, together with the set of vertices that we
can absorb into $P$, to find cycles of all lengths larger than that of $C$. A
similar strategy using $P$ will allow us to find all shorter cycles.

###### Proof of Theorems 1.1 and 1.3.

Let $\alpha=\omega((\log n/n)^{1/4})$, and let $G=G_{n,2}$ or $G=G_{n,1}$,
depending on which of the statements we want to prove. Condition on the event
that the statements of Lemmas 3.1 and 3.3 hold, which occurs a.a.s., where we
apply Lemma 3.3 to the pairs of sets $N_{H}(x)$ and $N_{H}(y)$ for each pair
$(x,y)\in V(H)\times V(H)$ with $\epsilon=1/2$. Thus,

for all $(x,y)\in V(H)\times V(H)$ we have that $N_{H}(x)$ contains at least
$\alpha^{2}n/2$ vertices $z$ such that $N_{G}(z)\cap N_{H}(y)\neq\varnothing$.
(4.1)

Whenever necessary, for our claims we assume that $n$ is sufficiently large.

For each pair of (not necessarily distinct) vertices $(x,y)\in V(H)\times
V(H)$, consider the set

$Z(x,y)\coloneqq\\{zz^{\prime}\in E(G):z\in N_{H}(x),z^{\prime}\in
N_{H}(y)\\}.$

This is a set of ‘available’ edges for $(x,y)$. Throughout the proof, we will
use these edges to make alterations on graphs; every time we do so, we will
update this set of available edges (in particular, we will always restrict the
list to edges of a ‘current’ graph; this will become clear later in the
proof). For simplicity of notation, whenever we consider an edge $zz^{\prime}$
from some set $Z(x,y)$ (or any of their updated versions), we will implicitly
assume that $z\in N_{H}(x)$ and $z^{\prime}\in N_{H}(y)$; note, however, that
these edges are not really ‘oriented’ in the definition, and so
$zz^{\prime}\in Z(y,x)$ too. By (4.1), for all $(x,y)\in V(H)\times V(H)$ we
have

$|Z(x,y)|\geq\alpha^{2}n/4.$ (4.2)

Note further that, since $Z(x,y)\subseteq G$ (by abusing notation and
identifying $Z(x,y)$ with a graph),

$\Delta(Z(x,y))\leq 2.$ (4.3)

Take an arbitrary set $U\subseteq V(H)$ of $m\coloneqq\alpha^{2}n/1000$
vertices and label them as $u_{1},\ldots,u_{m}$. For each $j\in[m]$,
iteratively, choose an edge $e_{j}=z_{j}z_{j}^{\prime}\in Z(u_{j},u_{j})$ such
that $e_{j}\cap U=\varnothing$ and
$e_{j}\cap\bigcup_{k\in[j-1]}e_{k}=\varnothing$ (the existence of such edges
is guaranteed in every step by (4.2) and (4.3)). Let
$W\coloneqq\bigcup_{j\in[m]}e_{j}$. Now, for each $(x,y)\in V(H)\times V(H)$,
we update the list of ‘available’ edges for $(x,y)$ by letting

$Z^{\prime}(x,y)\coloneqq\\{zz^{\prime}\in E(G):z\in N_{H}(x)\setminus(U\cup
W),z^{\prime}\in N_{H}(y)\setminus(U\cup W)\\},$

so it follows from (4.2) and (4.3) and since $|U\cup W|=3m$ that

$|Z^{\prime}(x,y)|\geq\alpha^{2}n/4-3\alpha^{2}n/500\geq\alpha^{2}n/5.$ (4.4)

Now, for each $j\in[m-1]$, iteratively, choose an edge
$f_{j}=w_{j}w_{j}^{\prime}\in Z^{\prime}(z_{j}^{\prime},z_{j+1})$ satisfying
that $f_{j}\cap\bigcup_{k\in[j-1]}f_{k}=\varnothing$. The existence of such
edges in each step follows by (4.4) and (4.3).

Consider the path $P\coloneqq
z_{1}z_{1}^{\prime}w_{1}w_{1}^{\prime}z_{2}\ldots
w_{m-1}^{\prime}z_{m}z_{m}^{\prime}$ (the fact that this is a path follows by
the previous choices of edges). Note $|V(P)|\leq 4m$. Let $W^{\prime}\coloneqq
V(P)\setminus\\{z_{1},z_{m}^{\prime}\\}$. Consider now the graph
$G_{0}\coloneqq(G-(W^{\prime}\cup U))\cup P$ or $G_{0}\coloneqq((M\cup
G)-(W^{\prime}\cup U))\cup P$, depending on the statement we are trying to
prove. By Lemma 3.1, this is a union of at most $\log^{2}n$ cycles and at most
$(1+o(1))\alpha^{2}n/200$ paths, all vertex-disjoint (where we might have
degenerate cases where some paths have length $0$, that is, they are an
isolated vertex). Indeed, note that Lemma 3.1 asserts that the number of
components of $G_{n,2}$ or $M\cup G_{n,1}$ is $o(\alpha^{2}n)$. The removal of
each of the vertices in $W^{\prime}\cup U$ may increase the number of
components by at most one, and $|W^{\prime}\cup U|\leq 5m=\alpha^{2}n/200$, so
the claim follows. Furthermore, after adding the path $P$ again, we have that
$\Delta(G_{0})\leq 2$. Indeed, the fact that the endpoints of $P$ have degree
at most $2$ in $G_{0}$ follows since the first and last edges of $P$ lie in
$E(G)$.

We will now use the edges of $H$ to iteratively combine these paths and cycles
into a single cycle $C\subseteq(H\cup G)-U$ of length $n-m$ with $P\subseteq
C$, which we will later use to obtain a Hamilton cycle (and, indeed, cycles of
all lengths). Let $V\coloneqq V(H)\setminus U$. For each $(x,y)\in V^{2}$, we
update the set of available edges by setting

$Z_{0}(x,y)\coloneqq\\{zz^{\prime}\in E(G):z\in N_{H}(x)\setminus(V(P)\cup
U),z^{\prime}\in N_{H}(y)\setminus(V(P)\cup U)\\}.$

It follows by (4.2) and (4.3) and since $|V(P)\cup U|\leq 5m$ that

$|Z_{0}(x,y)|\geq\alpha^{2}n/4-\alpha^{2}n/100=6\alpha^{2}n/25.$ (4.5)

Throughout the upcoming process, we will define graphs $G_{1},\ldots,G_{t}$,
for some $t\in\mathbb{N}$, where each one is obtained from the previous by
some ‘small’ alteration. All these graphs will be unions of vertex-disjoint
paths and cycles spanning $V$. The process will end when $G_{t}=C$, that is,
when we obtain the desired cycle spanning $V$. For each $i\in[t]$, the
alteration that we perform on $G_{i-1}$ to construct $G_{i}$ will depend on
its structure. We present here a sketch; the full details are given in cases 1
to 3 below. While the current graph $G_{i-1}$ contains at least two paths
(case 1), we create a new graph $G_{i}$ with one fewer path and whose number
of components does not increase by more than one. If $G_{i-1}$ contains
exactly one path (case 2), then we either decrease the number of components or
make sure that $G_{i}$ has no paths (while not increasing the number of
components). Finally, if $G_{i-1}$ contains at least two cycles and no paths
(case 3), then we create a graph $G_{i}$ with one fewer component, but we
possibly create a path in the process. It follows from this description that
the process must really end (assuming it can be carried out, which we prove
later). Indeed, we only apply case 1 while at least two components are paths,
and each time reduce the number of paths and do not increase the number of
components by more than one. Since $G_{0}$ contains at most $\log^{2}n$ cycles
and at most $(1+o(1))\alpha^{2}n/200$ paths, after some number of iterations
we will have a graph containing only one path and at most
$(1+o(1))\alpha^{2}n/100$ cycles. Furthermore, once there is only one path,
there will never be more than one again, so we will never apply case 1 again.
From this point on, we apply cases 2 or 3 intermittently, as needed, and we
always either reduce the number of components of the graph, or make sure that
we will reduce this number in the next iteration (while not increasing the
number of components now). In particular, this guarantees that every two steps
we decrease the number of components. Thus, at some point we will have a
unique component. If it is not a cycle, an application of case 2 will yield
the desired cycle.

The alterations performed throughout the process will use some of the
‘available’ edges. For instance, in some cases we will pick two vertices $x$
and $y$ and an edge $zz^{\prime}\in Z_{0}(x,y)$, and use these to alter the
graph. With this alteration, we will remove $zz^{\prime}$ from $G_{i-1}$ (and
our process is correct only if $zz^{\prime}\in E(G_{i-1})$). Thus, for future
iterations, we need to remove $zz^{\prime}$ from the set of ‘available’ edges
$Z_{0}(x,y)$. For all $i\in[t]$ and all pairs of vertices $x,y$, we will
denote by $Z_{i}(x,y)$ a subset of $Z_{0}(x,y)$ which is ‘available’ for the
next iteration. For all $i\in[t]$, we will always define $G_{i}$ as
$G_{i}\coloneqq(G_{i-1}\setminus E_{1})\cup E_{2}$, where $E_{1}$ and $E_{2}$
are sets of edges of $H\cup G$. Then, for all $(x,y)\in V^{2}$, we will set
$Z_{i}(x,y)\coloneqq Z_{i-1}(x,y)\setminus E_{1}$. Thus, we will not write
this definition explicitly in each case, as it will follow from the definition
of $G_{i}$.

Throughout the process, we will assume that some conditions hold. In
particular, for all $i\in[t]_{0}$ we will have $\Delta(G_{i})\leq 2$ and
$P\subseteq G_{i}\subseteq(H\cup G)\setminus U$ (note that these hold for
$G_{0}$ by definition; for larger values of $i$, they will be a consequence of
the specific process which we follow) and, for all $(x,y)\in V^{2}$, that
$Z_{i}(x,y)\subseteq G_{i}$ and $Z_{i}(x,y)$ and $P$ are vertex-disjoint (both
of which hold by definition). Note that the conditions that
$Z_{i}(x,y)\subseteq G_{i}$ and $\Delta(G_{i})\leq 2$ imply (4.3) holds for
each $Z_{i}(x,y)$ (which also holds simply by the definition of $Z_{i}(x,y)$);
we will keep referring to (4.3) when we wish to use this fact. Furthermore, we
will assume that in each step we have

$|Z_{i-1}(x,y)|\geq\alpha^{2}n/8;$ (4.6)

it will follow from our process that the number of steps $t$ that we perform
and the number of edges that become ‘unavailable’ at each step are small, so
that (4.6) holds.

We now provide the details of the process. Let $i\in\mathbb{N}$ and assume we
have already defined $G_{i-1}$. If $G_{i-1}$ is a cycle of length $n-m$ (which
spans $V$), we are done. Otherwise, we will want to create a new graph
$G_{i}$. For this, we will need to consider several cases.

Case 1. Assume at least two of the components of $G_{i-1}$ are paths. Let
$P^{\prime}$ be one of the path components of $G_{i-1}$, and let its endpoints
be $x$ and $y$. Choose any edge $zz^{\prime}\in Z_{i-1}(x,y)$ such that
$\operatorname{dist}_{G_{i-1}}(zz^{\prime},\\{x,y\\})>1$ and let
$G_{i}\coloneqq(G_{i-1}\setminus\\{zz^{\prime}\\})\cup\\{xz,yz^{\prime}\\}$.
Depending on the relative position of $zz^{\prime}$ with respect to
$P^{\prime}$, the total number of components will either decrease by one,
remain the same, or increase by one.

Case 2. Assume exactly one component of $G_{i-1}$ is a path $P^{\prime}$. Let
its endpoints be $x$ and $y$. Consider the following cases.

  1. 2.1.

Assume that $N_{H}(x)\cup N_{H}(y)\nsubseteq U\cup V(P)\cup V(P^{\prime})$.
Suppose that there exists some $z\in N_{H}(x)\setminus(U\cup V(P)\cup
V(P^{\prime}))$ (the other case is analogous). Then, choose a vertex
$z^{\prime}\in N_{G_{i-1}}(z)$ (so $zz^{\prime}$ is an edge of a cycle of
$G_{i-1}$) and let
$G_{i}\coloneqq(G_{i-1}\setminus\\{zz^{\prime}\\})\cup\\{xz\\}$. This reduces
the number of components and increases the length of the unique path
$P^{\prime}$.

  2. 2.2.

Otherwise, we have that $Z_{i-1}(x,y)\subseteq E(P^{\prime})$. Suppose there
is an edge $zz^{\prime}\in Z_{i-1}(x,y)$ such that
$\operatorname{dist}_{P^{\prime}}(x,z^{\prime})<\operatorname{dist}_{P^{\prime}}(x,z)$.
If so, let
$G_{i}\coloneqq(G_{i-1}\setminus\\{zz^{\prime}\\})\cup\\{xz,yz^{\prime}\\}$.
In this case, we turn $P^{\prime}$ into a cycle.

  3. 2.3.

Otherwise, every $zz^{\prime}\in Z_{i-1}(x,y)$ satisfies $z,z^{\prime}\in
V(P^{\prime})$ and
$\operatorname{dist}_{P^{\prime}}(x,z)<\operatorname{dist}_{P^{\prime}}(x,z^{\prime})$.
By (4.3) and (4.6), we can find a set $Z_{i-1}^{\prime}(x,y)\subseteq
Z_{i-1}(x,y)$ with

$|Z_{i-1}^{\prime}(x,y)|\geq\alpha^{2}n/16$ (4.7)

and such that any two $zz^{\prime},ww^{\prime}\in Z_{i-1}^{\prime}(x,y)$ are
vertex-disjoint. Now choose two edges $zz^{\prime},ww^{\prime}\in
Z_{i-1}^{\prime}(x,y)$ with
$\operatorname{dist}_{P^{\prime}}(x,z)<\operatorname{dist}_{P^{\prime}}(x,w)$
which minimise $\operatorname{dist}_{P^{\prime}}(z,w)$ over all possible such
pairs of edges. We now have two cases.

    1. 2.3.1.

If $\operatorname{dist}_{P^{\prime}}(z^{\prime},w)=1$, let
$G_{i}\coloneqq(G_{i-1}\setminus\\{z^{\prime}w\\})\cup\\{xw,yz^{\prime}\\}$.
This, again, turns $P^{\prime}$ into a cycle.

    2. 2.3.2.

Otherwise, let $z^{\prime\prime},w^{\prime\prime}\in V(P^{\prime})$ be such
that
$\operatorname{dist}_{P^{\prime}}(x,z^{\prime\prime})=\operatorname{dist}_{P^{\prime}}(x,z^{\prime})+1$
and
$\operatorname{dist}_{P^{\prime}}(x,w^{\prime\prime})=\operatorname{dist}_{P^{\prime}}(x,w)-1$.
Let $P^{\prime\prime}$ be the subpath of $P^{\prime}$ whose endpoints are
$z^{\prime\prime}$ and $w^{\prime\prime}$, and let
$\ell\coloneqq\operatorname{dist}_{P^{\prime}}(z^{\prime\prime},w^{\prime\prime})$
be the length of $P^{\prime\prime}$. By an averaging argument using (4.7), it
follows that

$\ell\leq
16|V(P^{\prime})|/(\alpha^{2}n)=\mathcal{O}(\alpha^{-2})=o(\alpha^{2}n).$

By (4.6), this guarantees that we can pick an edge $z^{3}w^{3}\in
Z_{i-1}(z^{\prime\prime},w^{\prime\prime})$ such that
$\operatorname{dist}_{G_{i-1}}(z_{3}w_{3},V(P^{\prime\prime}))\geq 1$. Now,
let

$G_{i}\coloneqq(G_{i-1}\setminus\\{z^{\prime}z^{\prime\prime},ww^{\prime\prime},z^{3}w^{3}\\}))\cup\\{xw,yz^{\prime},z^{\prime\prime}z^{3},w^{\prime\prime}w^{3}\\}.$

In this case, if $z^{3}w^{3}\in E(P^{\prime})$, we turn $P^{\prime}$ into a
cycle; otherwise, we combine the vertices of $P^{\prime}$ and the cycle
containing $z^{3}w^{3}$ into two new cycles.

Case 3. Assume all components of $G_{i-1}$ are cycles. We consider the
following cases.

  1. 3.1.

For each edge $xy\in E(G_{i-1})$, let $C_{xy}$ be the cycle of $G_{i-1}$ which
contains this edge. Assume that there exists some $xy\in E(G_{i-1})\setminus
E(P)$ satisfying that $Z_{i-1}(x,y)\nsubseteq E(C_{xy})$. If so, let
$zz^{\prime}\in Z_{i-1}(x,y)\setminus E(C_{xy})$ and let
$G_{i}\coloneqq(G_{i-1}\setminus\\{xy,zz^{\prime}\\})\cup\\{xz,yz^{\prime}\\}$.
This combines two cycles into one.

  2. 3.2.

Otherwise, from (4.6), it follows that each cycle of $G_{i-1}$ must contain at
least $\alpha^{2}n/8$ vertices. Now let $x,y\in V\setminus V(P)$ be such that
$x$ and $y$ lie in different cycles (note, in particular, that we may pick a
vertex in any of the cycles since $|V(P)|\leq 4m<\alpha^{2}n/8$) and let
$zz^{\prime}\in Z_{i-1}(x,y)$. Assume without loss of generality that
$zz^{\prime}$ lies in a cycle other than the one containing $x$. By the
definition of $Z_{0}(x,y)$, this means that $xz$ is an edge of $H$ joining two
of the cycles of $G_{i-1}$. Now let $w\in N_{G_{i-1}}(x)$and let
$G_{i}\coloneqq(G_{i-1}\setminus\\{wx,zz^{\prime}\\})\cup\\{xz\\}$. This
combines two cycles into a path.

The fact that $\Delta(G_{i})\leq 2$ follows by the construction in each case,
since we only add at most one edge incident to each vertex, and we only do
this for vertices which had degree one in $G_{i-1}$ or for which we first
delete an incident edge. The fact that $P\subseteq G_{i}$ follows since we
have made sure not to delete any of the edges of $P$, and
$G_{i}\subseteq(H\cup G)\setminus U$ since we only add edges of $H$.

Now let $C=G_{t}$ be the graph resulting from the above process. The argument
that we provided when arguing that the process must end shows that
$t\leq(1+o(1))\alpha^{2}n/40$, and this implies that (4.6) holds (indeed,
observe that in all cases the number of edges which are deleted from each
$Z_{i}(x,y)$ is at most $3$, so at most $(3+o(1))\alpha^{2}n/40$ edges are
removed, and the conclusion follows from (4.5)).

By the iterative process above, we have proved the existence of a cycle $C$ of
length $n-m$ such that $P\subseteq C$. We must now prove that there is a cycle
of length $k$, for all $3\leq k\leq n$. Recall that $Z_{t}(x,y)\subseteq
E(C)\setminus E(P)$ for all $(x,y)\in V^{2}$ and (4.6) holds. We split our
analysis into three cases.

Suppose first that $3\leq k\leq\alpha^{2}n/20$. In such a case, consider any
subpath $P^{\prime}\subseteq C$ of length $k-3$, and let its endpoints be $x$
and $y$. Now choose any edge $zz^{\prime}\in Z_{t}(x,y)$ such that
$z,z^{\prime}\notin V(P^{\prime})$ (the existence of such an edge follows by
(4.6) and (4.3)). Then, the union of $P^{\prime}$ and the path $xzz^{\prime}y$
forms a cycle of length $k$.

Assume next that $n-m\leq k\leq n$. Consider a set $J\subseteq[m]$ with
$|J|=k+m-n$. In $C$, for each $j\in J$, replace the edge
$e_{j}=z_{j}z_{j}^{\prime}$ by the path $z_{j}u_{j}z_{j}^{\prime}$. This
yields a cycle of the desired length.

Finally, assume $\alpha^{2}n/20<k<n-m$. Consider a subpath
$P^{\prime}\subseteq C$ of length $k-3$ such that $P\subseteq P^{\prime}$. Let
the endpoints of $P^{\prime}$ be $x$ and $y$, respectively, and consider the
set $Z_{t}(x,y)$. We consider the following three cases.

  1. 1.

Assume that there exists $zz^{\prime}\in Z_{t}(x,y)$ such that
$z,z^{\prime}\notin V(P^{\prime})$. Then, the union of $P^{\prime}$ and the
path $xzz^{\prime}y$ forms a cycle of length $k$.

  2. 2.

Otherwise, let $Z_{t}^{\prime}(x,y)\coloneqq\\{e\in Z_{t}(x,y):e\subseteq
V(P^{\prime})\\}$, so we have $Z_{t}^{\prime}(x,y)\subseteq E(P^{\prime})$ and
$|Z_{t}^{\prime}(x,y)|\geq|Z_{t}(x,y)|-2>\alpha^{2}n/16$ by (4.6). Recall that
$Z_{t}^{\prime}(x,y)$ and $P$ are vertex-disjoint. Suppose there is an edge
$zz^{\prime}\in Z_{t}^{\prime}(x,y)$ such that
$\operatorname{dist}_{P^{\prime}}(x,z^{\prime})<\operatorname{dist}_{P^{\prime}}(x,z)$.
If so, $(P^{\prime}\setminus\\{zz^{\prime}\\})\cup\\{xz,yz^{\prime}\\}$ is a
cycle of length $k-2$ which contains $P$. To obtain a cycle of length $k$,
replace $e_{1}=z_{1}z_{1}^{\prime}$ and $e_{2}=z_{2}z_{2}^{\prime}$ by the
paths $z_{1}u_{1}z_{1}^{\prime}$ and $z_{2}u_{2}z_{2}^{\prime}$, respectively.

  3. 3.

Otherwise, $Z_{t}^{\prime}(x,y)\subseteq E(P^{\prime})$ and all
$zz^{\prime}\in Z_{t}^{\prime}(x,y)$ satisfy that
$\operatorname{dist}_{P^{\prime}}(x,z)<\operatorname{dist}_{P^{\prime}}(x,z^{\prime})$.
Recall, again, that $Z_{t}^{\prime}(x,y)$ and $P$ are vertex-disjoint. We now
proceed similarly to case 2.3. First, by (4.3) and the current bound on
$|Z_{t}^{\prime}(x,y)|$, we may restrict ourselves to a subset of available
edges $Z_{t}^{\prime\prime}(x,y)\subseteq Z_{t}^{\prime}(x,y)$ such that
$|Z_{t}^{\prime\prime}(x,y)|\geq\alpha^{2}n/32$ and any two edges
$zz^{\prime},ww^{\prime}\in Z_{t}^{\prime\prime}(x,y)$ are vertex-disjoint.
Now, choose two edges $zz^{\prime},ww^{\prime}\in Z_{t}^{\prime\prime}(x,y)$
with
$\operatorname{dist}_{P^{\prime}}(x,z)<\operatorname{dist}_{P^{\prime}}(x,w)$
which minimise $\operatorname{dist}_{P^{\prime}}(z,w)$ over all possible
pairs. Let $P^{\prime\prime}$ be the subpath of $P^{\prime}$ whose endpoints
are $z^{\prime}$ and $w$, and let
$\ell\coloneqq\operatorname{dist}_{P^{\prime}}(z,w)$. By an averaging argument
using the fact that $|Z_{t}^{\prime\prime}(x,y)|\geq\alpha^{2}n/32$, it
follows that $\ell\leq 32|V(P^{\prime})|/(\alpha^{2}n)<m$. Then, the graph
$(P^{\prime}\setminus E(P^{\prime\prime}))\cup\\{xw,yz^{\prime}\\}$ is a cycle
of length $k-\ell$ which contains $P$. In order to obtain a cycle of length
$k$, for each $j\in[\ell]$ replace $e_{j}=z_{j}z_{j}^{\prime}$ by the path
$z_{j}u_{j}z_{j}^{\prime}$.∎

##  5\. Randomly perturbing graphs by a perfect matching

Let $\alpha^{*}\coloneqq\sqrt{2}-1$. We first show that, for any constant
$\alpha<\alpha^{*}$, there exist $n$-vertex graphs $H$ with $\delta(H)=\alpha
n$ such that $H\cup G_{n,1}$ does not a.a.s. contain a Hamilton cycle. Indeed,
let $H=(A,B,E)$ be a complete unbalanced bipartite graph, where $|A|=\alpha n$
and $|B|=(1-\alpha)n$ (so $d_{H}(v)=\alpha n$ for all $v\in B$), and let $G$
be a perfect matching on the same vertex set as $H$. It is easy to check that
a necessary condition for $G$ so that $H\cup G$ contains a Hamilton cycle is
that $G[B]$ contains at least $(1-2\alpha)n$ edges. Now, in $G_{n,1}$, each
edge appears with probability $1/(n-1)$, so

$\mathbb{E}[e_{G_{n,1}}(B)]=\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{(1-\alpha)n}{2}\kern-1.00006pt\right)\frac{1}{n-1}\leq\frac{(1-\alpha)^{2}}{2}n<(1-2\alpha)n.$

The conclusion then follows by Markov’s inequality.

In order to prove Theorem 1.2, we first need the following lemma.

######  Lemma 5.1.

Let $1/n\ll\beta<\alpha/2<1/4$. Let $H$ be an $n$-vertex graph with
$\delta(H)\geq\alpha n$ which does not contain a matching of size greater than
$(n-\sqrt{n})/2$. Let $M$ be a maximum matching in $H$. Then, the vertex set
of $H$ can be partitioned into sets
$A\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B_{2}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}C_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}C_{2}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}R$
in such a way that the following hold:

  1. $(\mathrm{H1})$

$|A|\leq 12\beta^{-2}$;

  2. $(\mathrm{H2})$

$n-2|M|-|A|\leq|R|\leq n-2|M|$;

  3. $(\mathrm{H3})$

$|B_{1}|=|B_{2}|$ and $H[B_{1},B_{2}]$ contains a perfect matching;
furthermore, for every $v\in B_{2}\cup R$ we have
$e_{H}(v,B_{1})\geq(\alpha-2\beta)n$, and

  4. $(\mathrm{H4})$

$|C_{1}|=|C_{2}|$ and $H[C_{1},C_{2}]$ contains a perfect matching;
furthermore, for all $v\in C_{2}$ we have $e_{H}(v,B_{2}\cup
R)\leq\beta^{-1}+1$.

###### Proof.

Let $M$ be a maximum matching in $H$. Let $V\coloneqq V(M)$ and
$R^{\prime}\coloneqq V(H)\setminus V$. By the maximality of $M$ and the
condition on $H$ in the statement, we have that $E(H[R^{\prime}])=\varnothing$
and $|R^{\prime}|\geq\sqrt{n}$. For each vertex $v\in V$, let $M(v)$ denote
the unique vertex $w\in V$ such that $vw\in M$. For any set $S\subseteq V$, we
define $M(S)\coloneqq\\{M(v):v\in S\\}$.

To prove the statement we will follow an iterative process. We will
inductively construct two sequences of sets $\\{B_{1}^{i}\\}_{i\geq 1}$ and
$\\{B_{2}^{i}\\}_{i\geq 1}$ with $B_{1}^{i},B_{2}^{i}\subseteq V$ and use
these to construct the vertex partition. First, for notational purposes we let
$B_{2}^{-1}=B_{1}^{0}\coloneqq\varnothing$, and we define $B_{2}^{0}\coloneqq
R^{\prime}$. Then, for each $i\geq 1$, we define

$B_{1}^{i}\coloneqq\left\\{v\in
V\setminus\left(\bigcup_{j=0}^{i-1}(B_{1}^{j}\cup
B_{2}^{j})\right):e_{H}(v,B_{2}^{i-1})\geq 2\right\\}\quad\text{ and }\quad
B_{2}^{i}\coloneqq M(B_{1}^{i}).$ (5.1)

######  Claim 1.

For all $i\in[\beta n/2]_{0}$, the following properties hold.

  1. $(\mathrm{i})$

$B_{1}^{i}$ does not span any edge from $M$.

  2. $(\mathrm{ii})$

$B_{2}^{i}$ is an independent set.

  3. $(\mathrm{iii})$

All but at most $4\beta^{-1}$ vertices $v\in B_{2}^{i-1}$ satisfy that

$e_{H}\left(v,\bigcup_{j=1}^{i}B_{1}^{j}\right)\geq(\alpha-\beta)n.$

###### Proof.

We proceed by induction on $i$. As a base case, note that $(\mathrm{i})$ holds
trivially for $B_{1}^{0}$, we have already established that
$B_{2}^{0}=R^{\prime}$ is an independent set, and $(\mathrm{iii})$ is
vacuously true. Now, for some $i\in[\beta n/2-1]_{0}$, assume that the
properties in the statement hold for all $j\in[i]_{0}$ and that we want to
show the properties also hold for $i+1$. Note that (5.1) and property
$(\mathrm{i})$ imply that

for all $(j,\ell),(j^{\prime},\ell^{\prime})\in([i]_{0})\times[2]$ with
$(j,\ell)\neq(j^{\prime},\ell^{\prime})$ we have $B_{\ell}^{j}\cap
B_{\ell^{\prime}}^{j^{\prime}}=\varnothing$. (5.2)

Observe that, if $|B_{1}^{i+1}|\leq 1$, then $(\mathrm{i})$ and
$(\mathrm{ii})$ hold trivially, and $B_{1}^{i+j}=\varnothing$ for all $j\geq
2$. Therefore, for the proof of these two properties we may assume that
$|B_{1}^{i+1}|\geq 2$ and, thus, $|B_{1}^{j}|\geq 2$ for all $j\in[i]$.

In order to prove $(\mathrm{i})$, suppose for a contradiction that
$B_{1}^{i+1}$ spans some edge $e=xy\in M$. Our aim is to construct a matching
larger than $M$. To do so, first note that, by the definition of $B_{1}^{i+1}$
in (5.1), we may find two distinct vertices $x_{2}^{i},y_{2}^{i}\in B_{2}^{i}$
such that $xx_{2}^{i},yy_{2}^{i}\in E(H)$. We now proceed recursively for
$j\in[i]$, starting with $j=i$ and decreasing its value, as follows:

  * •

Let $x_{1}^{j}\coloneqq M(x_{2}^{j})$ and $y_{1}^{j}\coloneqq M(y_{2}^{j})$,
so $x_{1}^{j},y_{1}^{j}\in B_{1}^{j}$.

  * •

Choose two distinct vertices $x_{2}^{j-1},y_{2}^{j-1}\in B_{2}^{j-1}$ such
that $x_{1}^{j}x_{2}^{j-1},y_{1}^{j}y_{2}^{j-1}\in E(H)$ (which can be done by
the definition of $B_{1}^{j}$).

Now consider the path $P\coloneqq x_{2}^{0}x_{1}^{1}x_{2}^{1}\ldots
x_{1}^{i}x_{2}^{i}xyy_{2}^{i}y_{1}^{i}\ldots y_{2}^{1}y_{1}^{1}y_{2}^{0}$
(where (5.2) guarantees that this is indeed a path). We may then take
$M_{1}\coloneqq M\triangle E(P)$. It is easy to verify that $|M_{1}|=|M|+1$,
which contradicts the maximality of $M$.

In order to prove $(\mathrm{ii})$, we proceed similarly. Suppose for a
contradiction that $B_{2}^{i+1}$ is not an independent set and let
$e=v_{2}^{i+1}w_{2}^{i+1}\in E(H[B_{2}^{i+1}])$. We now proceed recursively
for $j\in[i+1]$, starting with $j=i+1$ and decreasing its value, as follows:

  * •

Let $v_{1}^{j}\coloneqq M(v_{2}^{j})$ and $w_{1}^{j}\coloneqq M(w_{2}^{j})$,
so $v_{1}^{j},w_{1}^{j}\in B_{1}^{j}$.

  * •

Choose two distinct vertices $v_{2}^{j-1},w_{2}^{j-1}\in B_{2}^{j-1}$ such
that $v_{1}^{j}v_{2}^{j-1},w_{1}^{j}w_{2}^{j-1}\in E(H)$ (which can be done by
the definition of $B_{1}^{j}$).

Consider the path $P^{\prime}\coloneqq v_{2}^{0}v_{1}^{1}v_{2}^{1}\ldots
v_{1}^{i}v_{2}^{i}v_{1}^{i+1}v_{2}^{i+1}w_{2}^{i+1}w_{1}^{i+1}w_{2}^{i}w_{1}^{i}\ldots
w_{2}^{1}w_{1}^{1}w_{2}^{0}$ (in order to guarantee that this is indeed a
path, we are using the fact that we have now proved that (5.2) also holds for
$i+1$). We may now take $M_{1}^{\prime}\coloneqq M\triangle E(P^{\prime})$
and, again, verify that $|M_{1}^{\prime}|=|M|+1$.

Finally, suppose there are $k\coloneqq\lceil 4\beta^{-1}\rceil$ distinct
vertices $v_{1},\ldots,v_{k}\in B_{2}^{i}$ such that for all $\ell\in[k]$ we
have

$e_{H}\left(v_{\ell},\bigcup_{j=1}^{i+1}B_{1}^{j}\right)<(\alpha-\beta)n.$
(5.3)

By (5.1), for each $j\in[i-1]_{0}$ and $\ell\in[k]$ we have that
$e_{H}(v_{\ell},B_{2}^{j})\leq 1$. It follows from this, the fact that
$E(H[B_{2}^{i}])=\varnothing$ (by $(\mathrm{ii})$), the assumption on the
minimum degree of $H$ and (5.3) that for each $\ell\in[k]$ we have

$e_{H}\left(v_{\ell},V\setminus\left(B_{1}^{i+1}\cup\bigcup_{j=1}^{i}(B_{1}^{j}\cup
B_{2}^{j})\right)\right)>\beta n-i\geq\beta n/2.$

Furthermore, again by (5.1), we must have $e_{H}(B_{2}^{i},B_{2}^{i+1})\leq
n$. Combining this with the previous bound, it follows that

$e_{H}\left(B_{2}^{i},V\setminus\bigcup_{j=1}^{i+1}(B_{1}^{j}\cup
B_{2}^{j})\right)>k\beta n/2-n\geq n,$

so there must exist some vertex $y\in
V\setminus\bigcup_{j=1}^{i+1}(B_{1}^{j}\cup B_{2}^{j})$ with
$e_{H}(y,B_{2}^{i})\geq 2$, which contradicts the definition of $B_{1}^{i+1}$,
so $(\mathrm{iii})$ holds. ∎

Consider the smallest $j\geq 1$ such that $|B_{1}^{j}|<\beta n/2$ and let
$i^{*}\coloneqq j-1$. Note that $i^{*}\leq\beta^{-1}<\beta n/2$ and that
1$(\mathrm{iii})$ for $i=1$ guarantees that $i^{*}\geq 1$.

######  Claim 2.

All but at most $4\beta^{-1}$ vertices $v\in B_{2}^{i^{*}}$ satisfy that

$e_{H}\left(v,\bigcup_{j=1}^{i^{*}}B_{1}^{j}\right)\geq(\alpha-\beta)n.$

###### Proof.

Similarly to the proof of property $(\mathrm{iii})$ in 1, suppose there is a
set $S\subseteq B_{2}^{i^{*}}$ of size $k\coloneqq\lceil 4\beta^{-1}\rceil$
such that for every $v\in S$ we have
$e_{H}(v,\bigcup_{j=1}^{i^{*}}B_{1}^{j})<(\alpha-\beta)n$. By (5.1), for each
$j\in[i^{*}-1]_{0}$ and $v\in S$ we have that $e_{H}(v,B_{2}^{j})\leq 1$.
Combining these two bounds with the fact that
$E(H[B_{2}^{i^{*}}])=\varnothing$ (by 1$(\mathrm{ii})$) and the assumption on
the minimum degree of $H$, it follows that for each $v\in S$ we have

$e_{H}\left(v,V\setminus\bigcup_{j=1}^{i^{*}}(B_{1}^{j}\cup
B_{2}^{j})\right)>\beta n-i^{*},$

so we conclude that

$e_{H}\left(S,V\setminus\bigcup_{j=1}^{i^{*}}(B_{1}^{j}\cup
B_{2}^{j})\right)>k(\beta n-i^{*}).$

On the other hand, by the definition in (5.1), we have that

$e_{H}\left(S,V\setminus\bigcup_{j=1}^{i^{*}}(B_{1}^{j}\cup
B_{2}^{j})\right)\leq n+k|B_{1}^{i^{*}+1}|.$

It follows that $|B_{1}^{i^{*}+1}|>\beta n-i^{*}-n/k\geq\beta n/2$, which
contradicts the definition of $i^{*}$. ∎

Now, a partition of $V(H)$ as described in the statement can be obtained as
follows. Let $W$ be the set of all vertices
$v\in\bigcup_{i=1}^{i^{*}}B_{2}^{i}$ for which
$e_{H}(v,\bigcup_{i=1}^{i^{*}}B_{1}^{i})<(\alpha-\beta)n$, and let
$W^{\prime}$ be the set of all vertices $v\in B_{2}^{0}$ for which
$e_{H}(v,B_{1}^{1})<(\alpha-\beta)n$. Let $A\coloneqq W^{\prime}\cup W\cup
M(W)$. It follows by 1$(\mathrm{iii})$ together with 2 that $|A|\leq
4\beta^{-1}(2i^{*}+1)\leq 12\beta^{-2}$, so $(\mathrm{H1})$ holds. Then, for
each $\ell\in[2]$, let
$B_{\ell}\coloneqq\bigcup_{i=1}^{i^{*}}B_{\ell}^{i}\setminus A$, and let
$R\coloneqq R^{\prime}\setminus A$ (so $(\mathrm{H2})$ holds). It follows
that, for every $v\in R\cup B_{2}$, we have
$e_{H}(v,B_{1})\geq(\alpha-\beta)n-|A|\geq(\alpha-2\beta)n$, so
$(\mathrm{H3})$ holds. Finally, let $C\coloneqq V\setminus(A\cup B_{1}\cup
B_{2})$. Note that, if $C$ is not empty, then it contains a perfect matching
by construction. Consider a bipartition of $C$ into sets $C_{1}$ and $C_{2}$
such that $C_{2}=M(C_{1})$ and $B_{1}^{i^{*}+1}\subseteq C_{1}$. Then,
$(\mathrm{H4})$ follows by (5.1) and the fact that $i^{*}\leq\beta^{-1}$. ∎

We will also use the following observations repeatedly. Remark 5.2 is a
trivial observation, while Remarks 5.3 and 5.4 follow from elementary case
analyses.

######  Remark 5.2.

Let $G$ be a graph and consider a bipartition
$V(G)=A\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B$.
Let $P\subseteq G$ be a path of length at least $5$ which does not contain two
consecutive edges in $A$ or in $B$. Then, for each $X\in\\{A,B\\}$, the path
$P$ contains two distinct vertices $x,y\in X$ with
$\operatorname{dist}_{P}(x,y)\leq 3$.

######  Remark 5.3.

Let $G$ be a union of vertex-disjoint paths and cycles, where there are $p$
paths and $c$ cycles. Let $P_{1},P_{2}\subseteq G$ be two non-degenerate
vertex-disjoint subpaths of $G$. Let $x$ be an endpoint of $P_{1}$ and $y$ be
an endpoint of $P_{2}$, and assume $e\coloneqq\\{x,y\\}\notin E(G)$. Then,
$(G\setminus(P_{1}\cup P_{2}))\cup\\{e\\}$ is a union of vertex-disjoint paths
and cycles, with at most $p+1$ non-degenerate paths and at most $c+1$ cycles.

######  Remark 5.4.

Let $G$ be a union of vertex-disjoint paths and cycles. Let
$x,y,z,z^{\prime}\in V(G)$ such that
$e_{1}\coloneqq\\{x,z\\},e_{2}\coloneqq\\{y,z^{\prime}\\}\notin E(G)$ and $x$
and $y$ lie in the same cycle $\mathcal{C}$ of $G$. Let
$P_{1},P_{2},P_{3}\subseteq G$ be three non-degenerate vertex-disjoint
subpaths of $G$ such that $P_{1}$ has $z$ as an endpoint, $P_{2}$ has
$z^{\prime}$ as an endpoint, and $P_{3}$ is an $(x,y)$-path. Then,
$(G\setminus(P_{1}\cup P_{2}\cup P_{3}))\cup\\{e_{1},e_{2}\\}$ may contain a
cycle $\mathcal{C}^{\prime}\nsubseteq G$ only if at least one of the following
holds: in $G\setminus(P_{1}\cup P_{2}\cup P_{3})$, $x$ and $z$ lie in the same
component, or $y$ and $z^{\prime}$ lie in the same component, or $z$ and
$z^{\prime}$ lie in the same component.

We are finally ready to prove Theorem 1.2. The general idea is similar to the
proof of Theorems 1.1 and 1.3, though the details are more involved. We will
use Lemma 5.1 to show that $H$ satisfies certain properties and combine these
with the properties given by Lemmas 3.1 and 3.3. We will then consider the
graph given by the union of $G_{n,1}$ and a large matching of $H$, given by
Lemma 5.1, and iteratively modify this graph to obtain cycles of all lengths.
To achieve this, we will construct a special path $P$ which will be used to
absorb other vertices, in a similar fashion to the proof of Theorems 1.1 and
1.3, and then find an almost spanning cycle $C$ containing $P$. A key
difference with respect to that proof is that the iterative process by which
we construct $C$ is more involved, since the graph we start with is more
structured. Another key difference is that, while creating $C$, we will
isolate some vertices which cannot be absorbed with $P$; we need to make sure
that these can be absorbed by the cycle itself at a later stage, so that we
may find a Hamilton cycle (but these vertices play no role when constructing
cycles shorter than $C$). The properties given by Lemma 5.1 are crucial in
proving that our construction works.

###### Proof of Theorem 1.2.

By Theorem 1.3, if $H$ contains a matching covering all but $o(n)$ vertices,
we are done, so we may assume that the largest matching in $H$ covers at most
$n-\sqrt{n}$ vertices.

Let $0<\eta\ll\epsilon\ll 1$. Throughout, we always assume $n$ is sufficiently
large. Apply Lemma 5.1 with $\alpha\coloneqq(1+\epsilon)(\sqrt{2}-1)$ and
$\beta=\eta$. (Note, in particular, that we may assume $\alpha<1/2$.) This
yields a partition of $V(H)$ into
$A\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}B_{2}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}C_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}C_{2}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}R$
satisfying properties $(\mathrm{H1})$–$(\mathrm{H4})$ of the statement of the
lemma. We define $\gamma_{1}\coloneqq|C_{1}|/n$ and
$\gamma_{2}\coloneqq|B_{1}|/n$, so by $(\mathrm{H1})$ and $(\mathrm{H2})$ it
follows that

$|R|=(1-2\gamma_{1}-2\gamma_{2})n\pm 12\eta^{-2}\geq\sqrt{n}/2$ (5.4)

(where the lower bound follows from the bound on the size of a maximum
matching in $H$). Note that by $(\mathrm{H3})$ and since $\alpha>\sqrt{2}-1$
we have

$\gamma_{2}\geq(1-6\eta)\alpha.$ (5.5)

Observe that $\gamma_{1}\leq 1/2-\gamma_{2}$. It follows from this, (5.5), the
bound on $\alpha$, and by taking $\eta$ sufficiently small that

$\gamma_{1}\leq 86/1000.$ (5.6)

It follows from (5.5), $(\mathrm{H1})$, $(\mathrm{H4})$, the fact that
$e_{H}(v,C_{1}\cup C_{2})\leq|C_{1}\cup C_{2}|\leq(1-2\gamma_{2})n$, and the
bounds on $\delta(H)$ and $\alpha$ that

for all $v\in C_{2}$ we have $e_{H}(v,B_{1})\geq n/5$. (5.7)

Indeed, for each $v\in C_{2}$ we have that

$\displaystyle e_{H}(v,B_{1})$ $\displaystyle=e_{H}(v,V(H))-e_{H}(v,B_{2}\cup
R)-e_{H}(v,C_{1}\cup C_{2})-e_{H}(v,A)$ $\displaystyle\geq\alpha
n-\eta^{-1}-1-(1-2\gamma_{2})n-12\eta^{-2}$
$\displaystyle\geq(3\alpha-12\eta-1)n-12\eta^{-2}-\eta^{-1}-1\geq n/5.$

Furthermore, by $(\mathrm{H3})$, for any $x,y\in B_{2}\cup R$ we have
$|N_{H}(x)\cap N_{H}(y)\cap B_{1}|\geq(2\alpha-\gamma_{2}-4\eta)n$. It then
follows from the fact that $\gamma_{2}\leq 1/2$ and the bound on $\alpha$ that

for all $x,y\in B_{2}\cup R$ we have $|N_{H}(x)\cap N_{H}(y)\cap
B_{1}|\geq(1-20\eta)(2\alpha-\gamma_{2})n$. (5.8)

Let $M$ be the union of a perfect matching in $H[C_{1},C_{2}]$ and a perfect
matching in $H[B_{1},B_{2}]$. For any $v\in V(M)$, we let $M(v)$ be the unique
vertex $w$ such that $vw\in M$. Similarly, for any set $A\subseteq V(M)$, we
let $M(A)\coloneqq\bigcup_{v\in A}M(v)$.

Let $G=G_{n,1}$. Throughout the rest of the proof, we will use the fact that
$d_{G}(x)=1$ for every $x\in V(H)$ repeatedly and without further mention. We
now apply Lemma 3.3, with $\eta$ playing the role of $\epsilon$, to the pairs
of sets $(A_{i},B_{i})=(N_{H}(x),N_{H}(y))$ for all $(x,y)\in V(H)\times V(H)$
(with $\alpha_{i}=\beta_{i}=\alpha$) and the pairs of sets
$(A_{i},B_{i})=(N_{H}(x)\cap N_{H}(y)\cap B_{1},N_{H}(x)\cap N_{H}(y)\cap
B_{1})$ for all pairs $(x,y)\in(B_{2}\cup R)\times(B_{2}\cup R)$ (with
$\alpha_{i}=\beta_{i}=(1-20\eta)(2\alpha-\gamma_{2})$, see (5.8)). Condition
on the event that the statement of Lemma 3.3 holds for these pairs of sets,
and that the statements of Lemma 3.1$(\mathrm{ii})$ and Remark 3.2 hold, which
occurs a.a.s. Let $G_{0}\coloneqq M\cup G$. We claim that the following
properties hold:

  1. (G1)

For every $(x,y)\in V(H)\times V(H)$, we have
$e_{G}(N_{H}(x),N_{H}(y))\geq(1-\eta)\alpha^{2}n/2$.

  2. (G2)

For every $(x,y)\in(B_{2}\cup R)\times(B_{2}\cup R)$, we have

$e_{G}(N_{H}(x)\cap N_{H}(y)\cap
B_{1})\geq(1-50\eta)(2\alpha-\gamma_{2})^{2}n/2.$

  3. (G3)

$G_{0}$ is the union of at most $\log^{2}n$ cycles and $(1+o(1))|R|/2$ paths,
all vertex-disjoint.

  4. (G4)

Each of the paths of $G_{0}$ either has both endpoints in $A\cup R$ or is
comprised of a single edge in $E(M)\cap E(G)$. Furthermore, every vertex in
$A\cup R$ is the endpoint of some path.

  5. (G5)

All subpaths of $G_{0}$ alternate between edges of $G$ and edges of $M$.

  6. (G6)

$|E(M)\cap E(G)|\leq\log^{2}n$.

Indeed, both (G1) and (G2) follow from Lemma 3.3, (G3) follows from Lemma
3.1$(\mathrm{ii})$ together with $(\mathrm{H2})$ and (5.4), and (G6) holds by
Remark 3.2. Finally, (G4) and (G5) must hold by definition.

A simple algebraic manipulation with (5.4), (5.5) and the definition of
$\alpha$ shows that

$(1-50\eta)(2\alpha-\gamma_{2})^{2}n\geq(1+\eta)|R|.$ (5.9)

Using (5.5) it is also easy to check that
$(1-3\eta)\alpha^{2}n\geq(1-50\eta)(2\alpha-\gamma_{2})^{2}n$, hence

$(1-3\eta)\alpha^{2}n\geq(1+\eta)|R|.$ (5.10)

The bounds in (5.9) and (5.10) are crucial for our proof.

Our goal is to show that we can find cycles of all possible lengths in $H\cup
G_{0}=H\cup G$; to achieve this, we will need to modify $G_{0}$ through an
algorithm, where we will delete some edges of $G_{0}$ and add some edges of
$H$ for each subsequent alteration. The outcome of this process will be an
‘almost’ spanning cycle $C$, and we will make sure to satisfy certain
properties which will allow us to obtain all the desired cycles.

We begin with a high-level sketch of the process. At each step of the
algorithm, we always think of the graph as a union of vertex-disjoint paths
and cycles; the vertex set can become smaller at each step, though, as we
sometimes ‘delete’ some vertices (which we will need to ‘absorb’ at the end of
the process). We split the process into six steps (see Steps 1–6 below). In
Step 1, we simply remove all ‘isolated’ edges of $G_{0}$, since these will not
be useful for us. In Step 2 we create an absorbing path $P\subseteq H\cup
G_{0}$ that will allow us to incorporate a suitable number of vertices into a
cycle; this choice will be used at the end of the process to guarantee that we
can construct cycles of all lengths. Crucially, we must make sure that $P$ is
not modified through the remaining steps of the process. At this point all
paths in the graph will have their endpoints in $A\cup B_{2}\cup R$ (when
constructing $P$ we may produce new paths, but we make sure that the new
endpoints lie in $B_{2}$). We would like to have all their endpoints in
$B_{2}\cup R$ so that we may use (G2) in the future, so through Step 3 we will
make it so that all endpoints are in $B_{2}\cup R$. Step 4 is used to
guarantee that $P$ does not lie in a cycle; this helps us avoid possible
problems in Step 5, where we turn all cycles into paths (making sure that all
the resulting endpoints lie in $B_{2}\cup R$). At this point, the graph we are
considering is a union of vertex-disjoint paths with all their endpoints in
$B_{2}\cup R$. Then, using the aforementioned (G2), in Step 6 we can
iteratively combine all the paths into a single, ‘almost’ spanning path
containing $P$, which we later turn into an almost spanning cycle $C$
containing $P$. The bound given in (5.9) is crucial to prove that the almost
spanning path can be constructed. For simplicity of notation, we will always
refer to the graph by the same name throughout each of the steps, but the
graph is continuously updated in each step of the process.

As already mentioned above, throughout the process we sometimes ‘delete’ some
vertices from the graph. What this means is that they no longer play a role in
this process and will not be vertices of the resulting cycle $C$. We will need
to ensure that these vertices can later be ‘absorbed’ into the cycle (some via
$P$, and the rest without help from $P$). We will denote this set of ‘deleted’
vertices by $S$. We think of these vertices simply as being isolated. Note,
however, that not all vertices of $G_{0}$ that become isolated through the
process are added to $S$, as we will still allow some degenerate paths of
length $0$ to be part of the graph. Thus, we will always explicitly say which
vertices are added to $S$ (whenever we do this, we mean that these vertices
are removed from (the current version of) $G_{0}$, so we may keep thinking of
$G_{0}$ as a union of paths and cycles with the desired properties). In
particular, we will always think of the graph at any point throughout the
process as a graph on vertex set $V(H)\setminus S$ (and, when choosing
vertices for any purpose before the end of Step 6, we will always avoid $S$,
even if not explicitly stated).

When altering the graph throughout the process, we will often need to use some
edges of $G$ which are ‘available’ to us. To keep track of these, we define a
set $D$ of ‘unavailable’ edges. In particular, all edges deleted from $G_{0}$
are automatically added to $D$ (so we will not add them explicitly), but some
other edges are added to $D$ to ensure that our process will work (in
particular, to ‘protect’ $P$ throughout the process). Whenever we add edges to
$D$ without removing them from the graph, we say so explicitly.

Finally, for some of the alterations, given some vertex $v$, we will want to
find a neighbour $b_{1}\in N_{H}(v)\cap B_{1}$. When using these neighbours,
we will want to delete the edge of $M$ containing them (this will help us to
guarantee that the resulting graph remains a union of disjoint paths and
cycles). However, we cannot always delete this edge of $M$ (in particular, if
it has already been deleted). Therefore, it will be important for us to keep
track of those vertices $b_{1}\in B_{1}$ which we cannot choose at any given
step (they are also ‘unavailable’). We will denote the set of these vertices
by $K$. As happens for $D$, we will often update $K$ implicitly; in
particular, whenever an edge $b_{1}b_{2}\in E(M)$ with $b_{1}\in B_{1}$ is
added to $D$, implicitly or explicitly, $b_{1}$ is added to $K$. However, we
will sometimes explicitly add extra vertices to this set (in particular, to
‘protect’ $P$). We remark that $K$ and $S$ need not be disjoint.

Let us now describe the steps of our process. The fact that the sets $S$, $D$
and $K$ are updated immediately throughout the iterations in each of the steps
is crucial in some of the choices we make below. We also remark that we
continually use the fact that the graph we consider is a union of vertex-
disjoint paths and cycles, often implicitly.

Step 1. For each edge $e=xy\in E(M)\cap E(G)$, delete $e$ from $G_{0}$ and add
$x$ and $y$ to $S$.

Let the resulting graph be denoted by $G_{1}$. We claim that the following
properties hold:

  1. (A1)

$|S|,|D|,|K|\leq 2\log^{2}n$.

  2. (A2)

$G_{1}$ is the union of at most $\log^{2}n$ cycles and $(1+o(1))|R|/2$ paths,
all vertex-disjoint.

  3. (A3)

Each of the paths of $G_{1}$ has both endpoints in $A\cup R$. Furthermore,
$d_{G_{1}}(x)=1$ for every $x\in A\cup R$.

  4. (A4)

All subpaths of $G_{1}$ alternate between edges of $G$ and edges of $M$.

Indeed, (A1) follows immediately by (G6), (A3) follows by (G4) and the
deletions in Step 1, and (A2) and (A4) follow from (G3) and (G5),
respectively.

In particular, note that (A4) and the fact that all edges of $M$ are contained
in $B_{1}\cup B_{2}\cup C_{1}\cup C_{2}$ implies the following:

  1. (A5)

If $e\in E(G_{1}[A\cup R])$, then $e$ is an isolated edge in $G_{1}$.

Step 2. Let $G_{1}^{\prime}\coloneqq G_{1}$; this is a copy of the ‘original’
$G_{1}$ which we will not update. We now wish to construct an absorbing path
$P$. Let $U\subseteq R$ be an arbitrary set of $t\coloneqq\lceil
3\eta^{-1}\alpha^{-2}\rceil$ vertices (such a set must exist by (5.4) and
(A1)). Fix a labelling of the vertices in $U$ as $u_{1},\ldots,u_{t}$. For
each $i\in[t]$,

  1. 1.

choose an edge $x_{i}y_{i}\in E_{G}(N_{H}(u_{i})\cap B_{1})\setminus D$ and
add it to $D$ (but do not remove it from $G_{1}$).

These edges $x_{i}y_{i}$ will later be part of $P$, and they are added to $D$
in order to ‘protect’ $P$. Their existence, for each $i\in[t]$, follows from
(G2), (5.9), (5.4), (A1), and the value of $t$.

Let $U_{E}\coloneqq\\{x_{i},y_{i}:i\in[t]\\}$ and $U_{M}\coloneqq
M(U_{E})\subseteq B_{2}$. Remove all the edges of $M$ incident to
$U_{E}\setminus\\{x_{1},y_{t}\\}$ from $G_{1}$ (in particular, by (A4), now
each edge $x_{i}y_{i}$ becomes an isolated edge, and the endpoints of the
deleted edges in $U_{M}$ become endpoints of some paths in the resulting
graph) and, in order to ‘protect’ $P$, add $x_{1}$ and $y_{t}$ to $K$, even if
their respective edges in $M$ are not removed from the graph.

Next we are going to connect the edges $x_{i}y_{i}$ we just chose into a path
$P$. We will achieve this by using a $(y_{i},x_{i+1})$-path of length $3$ for
each $i\in[t-1]$. We are going to follow a process to choose a new set of
edges in $G$, which will be the central edges of the aforementioned paths. By
the end of the process, we will have constructed a path $P$ satisfying the
following properties:

  1. (B1)

$V(P)\cap U=\varnothing$.

  2. (B2)

$M(x_{1}),M(y_{t})\in B_{2}$ are the endpoints of $P$.

  3. (B3)

$P$ and $E(G)\setminus D$ are vertex-disjoint.

Together with $P$, we will have a graph $G_{2}$ which satisfies the following
properties:

  1. (B4)

$P\subseteq G_{2}$.

  2. (B5)

$G_{2}$ is the union of at most $2\log^{2}n$ cycles and $(1+o(1))|R|/2$ paths,
all vertex-disjoint.

  3. (B6)

Each of the paths of $G_{2}$ has both endpoints in $A\cup B_{2}\cup R$.

  4. (B7)

All subpaths of $G_{2}\setminus P$ have at most two consecutive vertices in
$A\cup R\cup B_{2}\cup C_{2}$ or in $B_{1}\cup C_{1}$.

  5. (B8)

If $e\in E(G_{1}^{\prime}[A\cup R])$, then either $e\in E(P)$ or $e$ is an
isolated edge in $G_{2}$.

Let us now describe the process. We note that (A4) is crucial and will be used
implicitly throughout. Let $W_{1}\coloneqq U_{E}\cup M(\\{x_{1},y_{t}\\})$.
For each $i\in[t]$, we will have a set $W_{i}$ which will consist of all
vertices of $P$ which have already been chosen. We claim that, at the start of
each iteration of the process (that is, for each $i\in[t-1]$), we may assume
that the following properties hold:

  1. (B9)

$|S|,|D|,|K|\leq 3\log^{2}n$.

  2. (B10)

$W_{1}\subseteq W_{i}$.

  3. (B11)

$|W_{i}|=2t+2i$.

  4. (B12)

$W_{i}\cap B_{1}\subseteq K$.

  5. (B13)

$M(W_{i}\cap B_{2})\subseteq K$.

  6. (B14)

$G_{1}$ is a union of vertex-disjoint paths and cycles.

  7. (B15)

All of the paths of $G_{1}$ have both endpoints in $A\cup B_{2}\cup R$, or
have one endpoint in $A\cup B_{2}\cup R$ and the other is $y_{i}$, or have one
endpoint in $A\cup B_{2}\cup R$ and the other is $x_{t}$, or consist of a
unique edge $x_{j}y_{j}$ for some $j\in[t-1]\setminus[i]$.

  8. (B16)

For any vertex $v\in B_{2}$ which is an endpoint of some path in $G_{1}$ we
have $M(v)\in K$.

  9. (B17)

All edges in $G_{1}\setminus G_{1}^{\prime}$ are contained in $W_{i}$ or have
one endpoint in $B_{1}$ and the other in $C_{2}$.

  10. (B18)

All edges $e\in E(G_{1}^{\prime}\setminus G_{1})$ with $e\in M$ contained in
$C_{1}\cup C_{2}$ are incident to $W_{i}$, or contained in $S$, or satisfy
that $\operatorname{dist}_{G_{1}^{\prime}}(e,K)\leq 1$.

  11. (B19)

$N_{G_{1}}(A\cup U)\cap K\subseteq W_{i}$.

Before starting the process (that is, for $i=1$), (B9) holds by (A1), the
value of $t$ and the fact that, so far in this step, we have increased the
sizes of $S$, $D$ and $K$ by at most $3t$; (B10) is trivial; (B11) and (B12)
follow by the definition of $W_{1}$ and $K$; (B13) holds trivially since
$W_{1}\cap B_{2}=M(\\{x_{1},y_{t}\\})\subseteq K$ by definition; (B14) holds
by (A2), since so far in this step we have only deleted edges; (B15) and (B16)
follow from (A3) and the fact that, so far, throughout this step we have only
deleted edges of $M$ with one endpoint in $B_{2}$ (which then becomes an
endpoint of some path) and the other endpoint in one of the edges $x_{i}y_{i}$
(but not the edges containing $x_{1}$ or $y_{t}$); (B17) is vacuously true
since $E(G_{1}\setminus G_{1}^{\prime})=\varnothing$; (B18) is vacuously true
since all edges of $G_{1}^{\prime}$ which have been deleted so far are
contained in $B_{1}\cup B_{2}$, and (B19) holds by construction, since at this
point we have $K\subseteq W_{1}\cup S$ and $N_{G_{1}}(A\cup U)\cap
S=\varnothing$ by the definition of $S$. We will later show that these
properties must indeed hold throughout.

For each $i\in[t-1]$, we proceed as follows:

  1. 2.

Choose an edge $w_{i}z_{i}\in E_{G}(N_{H}(y_{i})\setminus
U,N_{H}(x_{i+1})\setminus U)\setminus D$ such that

    1. (B20)

$\operatorname{dist}_{G_{1}}(\\{w_{i},z_{i}\\},W_{i})\geq 5$,

    2. (B21)

$\operatorname{dist}_{G_{1}^{\prime}}(\\{w_{i},z_{i}\\},W_{i})\geq 2$, and

    3. (B22)

$\operatorname{dist}_{G_{1}^{\prime}}(\\{w_{i},z_{i}\\},K)\geq 5$.

Note that such an edge must exist by (G1), (B9), (B11), (B14), and the value
of $t$. In order to ‘protect’ $P$, add $w_{i}z_{i}$ to $D$ (but do not remove
it from $G_{1}$).

  2. 3.

Now we make some modifications to ensure $G_{1}$ will remain a union of
vertex-disjoint paths and cycles after adding $y_{i}w_{i}$ and $z_{i}x_{i+1}$.
If the component of $G_{1}$ containing $w_{i}z_{i}$ is a cycle of length at
most $8$, we remove all edges of this cycle (except $w_{i}z_{i}$) from $G_{1}$
and add all its vertices (except $w_{i}$ and $z_{i}$) to $S$. Otherwise, for
each $x\in\\{w_{i},z_{i}\\}$, we consider several cases:

    1. 3.1.

If $x\in A\cup R$, do nothing.

    2. 3.2.

If $x\in B_{1}$, remove the edge of $M$ containing $x$ from $G_{1}$ (which
must have belonged to $G_{1}$ by the definition of $K$ and 2.(B22)). Note that
$M(x)\in B_{2}$ becomes an endpoint of a path in the resulting graph.

    3. 3.3.

If $x\in C_{1}$, consider the edge $xy\in E(M)$ (which must lie in $G_{1}$ by
(B18), 2.(B20), 2.(B21) and 2.(B22)) and let $z^{*}$ be the other neighbour of
$y\in C_{2}$ in $G_{1}$ (note that it must exist by (B14) and (B15)). Choose
some vertex $z\in(N_{H}(y)\cap B_{1})\setminus(K\cup N_{G_{1}}(A\cup
U)\cup\\{w_{i},z_{i},z^{*}\\})$, which must exist by (5.7), (B9),
$(\mathrm{H1})$, and the value of $t$. Then, add $yz$ to $G_{1}$ and remove
both $xy$ and the edge of $M$ containing $z$ (which must have belonged to
$G_{1}$ by the definition of $K$). Now $M(z)\in B_{2}$ becomes an endpoint of
a path in the resulting graph.

    4. 3.4.

If $x\in B_{2}\cup C_{2}$, consider the edge $xy\in E(M)$ (which must lie in
$G_{1}$ by (B18), 2.(B20), 2.(B21) and 2.(B22)) and let $z$ be the other
neighbour of $y$ in $G_{1}$ (which must exist by (B10), (B14), (B15) and
2.(B20)). Now consider the following cases:

      1. 3.4.1.

If $z\in A\cup R$, remove $xy$ and $yz$ from $G_{1}$ and add $y$ to $S$. We
now think of $z$ as a degenerate path.

      2. 3.4.2.

If $z\in B_{2}$, let $z^{\prime}$ be the other neighbour of $z$ (which must
exist by (B14), (B16), (B17) and 2.(B22)) and observe that, by (B17) and
2.(B22), we must have $zz^{\prime}\in M$. Remove $xy$ and $yz$ from $G_{1}$
and add $y$ to $S$. Furthermore, add $z^{\prime}$ to $K$ (but do not remove
$zz^{\prime}$ from $G_{1}$). Then, $z\in B_{2}$ becomes the endpoint of a path
in the resulting graph.

      3. 3.4.3.

If $z\in B_{1}$, let $zz^{\prime}\in E(M)$ (which must lie in $G_{1}$ by
(B17), 2.(B22) and the definition of $K$), remove $xy$, $yz$ and $zz^{\prime}$
from $G_{1}$, and add $y$ and $z$ to $S$. Now $z^{\prime}\in B_{2}$ becomes an
endpoint of a path.

      4. 3.4.4.

If $z\in C_{2}$, let $z^{*}$ be the other neighbour of $z$ in $G_{1}$ (which
must exist by (B14) and (B15)), and choose some vertex
$z^{\prime}\in(N_{H}(z)\cap B_{1})\setminus(K\cup N_{G_{1}}(A\cup
U)\cup\\{w_{i},z_{i},z^{*}\\})$ (which must exist by (5.7), (B9),
$(\mathrm{H1})$, and the value of $t$). Then, add $zz^{\prime}$ to $G_{1}$ and
remove $xy$, $yz$ and the edge of $M$ containing $z^{\prime}$ (which must lie
in $G_{1}$ by the definition of $K$) from $G_{1}$, and add $y$ to $S$. Now
$M(z^{\prime})\in B_{2}$ becomes an endpoint of a path.

      5. 3.4.5.

If $z\in C_{1}$, let $zz^{\prime}\in E(M)$ (which must lie in $G_{1}$ by
(B17), (B18), 2.(B20) and 2.(B22)), let $z^{*}$ be the other neighbour of
$z^{\prime}\in C_{2}$ in $G_{1}$ (which must exist by (B14) and (B15)), and
choose some vertex $z^{\prime\prime}\in(N_{H}(z^{\prime})\cap
B_{1})\setminus(K\cup N_{G_{1}}(A\cup U)\cup\\{w_{i},z_{i},z^{*}\\})$ (which
must exist by (5.7), (B9), $(\mathrm{H1})$, and the value of $t$). Then, add
$z^{\prime}z^{\prime\prime}$ to $G_{1}$ and remove $xy$, $yz$, $zz^{\prime}$
and the edge of $M$ containing $z^{\prime\prime}$ (which must lie in $G_{1}$
by the definition of $K$) from $G_{1}$, and add $y$ and $z$ to $S$. The vertex
$M(z^{\prime\prime})\in B_{2}$ becomes an endpoint of a path.

  3. 4.

Add $y_{i}w_{i}$ and $z_{i}x_{i+1}$ to $G_{1}$. Let $W_{i+1}\coloneqq
W_{i}\cup\\{w_{i},z_{i}\\}$ and iterate.

Note now that (B9) follows from (A1) and the fact that $S$, $K$ and $D$
increase their sizes by at most $8$ in each step of the process above. This,
combined with the at most $3t$ increase before the process and the value of
$t$, immediately yields the bound. (B10) holds trivially by definition. (B11)
holds trivially by the definition of $W_{i+1}$, since $w_{i},z_{i}\notin
W_{i}$ by 2.(B20) and are distinct. (B12) and (B13) hold because, throughout
the process, if $x\in B_{1}\cup B_{2}$, we delete the edge of $M$ containing
$x$, which implies the conditions. (B14) follows from the fact that,
throughout, we guarantee that all vertices of the graph $G_{1}$ have degree at
most $2$: indeed, we make sure to delete one edge incident to each of the
vertices that lie in one of the edges which will be added; the only exception
to this is case 3.1, in which there is no need to delete edges by (A3) and the
fact that the different vertices $x$ throughout the process are always
distinct. In order to prove (B15), note that all the newly created endpoints
lie in $B_{2}$, as remarked throughout the process. Furthermore, the edges
which are added to the graph in cases 3.3, 3.4.4 and 3.4.5 have one of their
endpoints in $C_{2}$ and the other in $B_{1}\setminus K$, which by (B12)
cannot belong to any of the vertices in $W_{i}$; this guarantees that the
different paths consisting of a single edge $x_{j}y_{j}$ with
$j\in[t-1]\setminus\\{1\\}$ do not become part of any longer paths or cycles
until the iteration in which $w_{j-1}z_{j-1}$ is considered. Observe that
avoiding the vertex $z^{*}$ in cases 3.3, 3.4.4 and 3.4.5 is crucial, as
otherwise we would create an endpoint in $C_{2}$. (B16) follows directly from
the process, since every time we create a new endpoint $v\in B_{2}$ we do so
by deleting the edge of $M$ containing $v$, except in case 3.4.2, where we
artificially add $M(v)$ to $K$. (B17) holds directly by construction: in the
$i$-th iteration, we add two edges, $y_{i}w_{i}$ and $z_{i}x_{i+1}$, which are
contained in $W_{i+1}$ by definition, and possibly some edges with an endpoint
in $B_{1}$ and the other in $C_{2}$ (this happens in cases 3.3, 3.4.4 and
3.4.5). Now, consider (B18). In case 3.3, the deleted edge is incident to a
vertex which is added to $W_{i+1}$; the same is true for the edge containing
$x$ in all subcases of case 3.4; by (B17), we are guaranteed that the other
edge $e$ deleted in case 3.4.5 now satisfies
$\operatorname{dist}_{G_{1}^{\prime}}(e,K)=1$; the only other case in which
one such edge may be deleted is when $w_{i}z_{i}$ is contained in a cycle $C$
of length at most $8$, but here all deleted edges are either incident to
$W_{i+1}$ or contained in $S$. Finally, (B19) can be checked throughout the
process by (B15), (B17) and the choices in cases 3.3, 3.4.4 and 3.4.5.

Note also that (B9)–(B13) hold after the last iteration of the process (that
is, for $i=t$). Similarly, (B17) and (B19) also hold after the process (that
is, replacing $G_{1}$ by $G_{2}$ and with $i=t$). These will come in useful
later.

Let $G_{2}$ be the graph resulting from the process above. Let

$P\coloneqq M(x_{1})x_{1}y_{1}w_{1}z_{1}x_{2}\ldots
y_{t-1}w_{t-1}z_{t-1}x_{t}y_{t}M(y_{t})$

(recall that all these vertices are distinct, as follows from the choices
throughout the process). Observe that (B1), (B2) and (B3) hold by definition.
In order to prove that (B4) holds, note first that all the edges of $P$ must
belong to $G_{1}$ at some point throughout the process, since $E(P)\cap
E(G)\subseteq E(G_{1}^{\prime})$, $x_{1}M(x_{1}),y_{t}M(y_{t})\in
E(G_{1}^{\prime})$ and all other edges of $P$ are added in the fourth step of
the process throughout the different iterations. The fact that none of these
edges are deleted throughout the process follows from (B12), (B13) and
2.(B20): indeed, throughout the process, all deleted edges either lie at
distance at most $3$ from $w_{i}$ or $z_{i}$, so they cannot be incident to
$W_{i}$ by 2.(B20), or they have an endpoint in $B_{1}\setminus K$ and belong
to $M$ (where we further ensure that said endpoint cannot be either $w_{i}$ or
$z_{i}$), and therefore cannot be incident to $W_{i}$ by (B12) and (B13).
Note, furthermore, that the edges deleted in cases 3.2, 3.3 and 3.4 for
$w_{i}$ cannot ‘interfere’ with those deleted for $z_{i}$, since in these
cases we are guaranteed that
$\operatorname{dist}_{G_{i}\setminus\\{w_{i}z_{i}\\}}(w_{i},z_{i})\geq 9$.
(B5) holds by (A2), (B14) and since, by Remark 5.3, the number of paths and
cycles does not increase too much throughout the process. Indeed, the number
of paths increases by at most $2t$ due to the deletions before the process,
and then by at most $2t$ due to the deletions throughout the process, and at
most $2t$ new cycles are created overall (see Remark 5.3 for cases 3.3, 3.4.4
and 3.4.5). This, combined with the bounds in (A2), (5.4) and the value of
$t$, guarantees that (B5) holds. (B6) is a direct consequence of (B15)
together with the final iteration of the process. Now, by (A4) we know that
all subpaths of $G_{1}^{\prime}$ have at most two consecutive vertices in
$A\cup R\cup B_{2}\cup C_{2}$ or in $B_{1}\cup C_{1}$. By (B17), all edges
added throughout the process are either contained in $W_{t}=V(P)$ or have one
endpoint in $B_{1}$ and the other in $C_{2}$. This guarantees that all
subpaths of $G_{2}$ (except possibly those that intersect $P$) must also have
at most two consecutive vertices in $A\cup R\cup B_{2}\cup C_{2}$ or in
$B_{1}\cup C_{1}$. That is, (B7) holds. Finally, (B8) follows directly from
(A5) and (B17).

Step 3. Our next goal is to obtain a graph $G_{3}$ which satisfies the
following properties:

  1. (C1)

$P\subseteq G_{3}$.

  2. (C2)

$G_{3}$ is the union of at most $3\log^{2}n$ cycles and $(1+o(1))|R|/2$ paths,
all vertex-disjoint.

  3. (C3)

Each of the paths of $G_{3}$ has both endpoints in $B_{2}\cup R$.

  4. (C4)

All subpaths of $G_{3}\setminus P$ have at most two consecutive vertices in
$R\cup B_{2}\cup C_{2}$ or in $B_{1}\cup C_{1}$.

  5. (C5)

$U\cap V(G_{3})=\varnothing$.

The goal of (C5) is to have all vertices in $U$ isolated, so that they can
later be absorbed by $P$.

In order to achieve this, roughly speaking, we are going to remove all edges
incident to $(A\cup U)\setminus V(P)$ from $G_{2}$ and then perform a few more
alterations on the graph to guarantee that (C3) holds. For these alterations,
we are are going to follow a process. We claim that, throughout, we may assume
that the following properties hold:

  1. (C6)

$|S|,|D|,|K|\leq 4\log^{2}n$.

  2. (C7)

$G_{2}$ is a union of vertex-disjoint paths and cycles.

  3. (C8)

Each of the paths of $G_{2}$ has both endpoints in $A\cup B_{2}\cup R$.

  4. (C9)

All edges in $G_{2}\setminus G_{1}^{\prime}$ are contained in $V(P)$ or have
one endpoint in $B_{1}$ and the other in $C_{2}$.

Note that, before we start the process, (C6), (C7), (C8) and (C9) are
guaranteed by (B9), (B5), (B6) and (B17), respectively.

We proceed as follows. For each edge $e=xy\in E(G_{2})$ with $x\in(A\cup
U)\setminus V(P)$, we proceed as follows depending on the position of $y$.
Note that, by (B5), we are guaranteed that $y\notin V(P)\setminus
M(\\{x_{1},y_{t}\\})$.

  1. 1.

If $y\in A\cup U\cup B_{2}$, remove $xy$ from $G_{2}$.

  2. 2.

If $y\in R\setminus U$, remove $xy$ from $G_{2}$ and add $y$ to $S$. Note
that, by (B8), this does not delete any other edges of $G_{2}$.

  3. 3.

If $y\in B_{1}$, remove $xy$ and the edge of $M$ containing $y$ from $G_{2}$
(note that this edge must have been in $G_{2}$ by (B19) and the definition of
$K$, since $y\notin V(P)$; see (B2)) and add $y$ to $S$. Observe that $M(y)\in
B_{2}$ becomes and endpoint in the resulting graph.

  4. 4.

If $y\in C_{2}$, let $z^{*}$ be the other neighbour of $y$ in $G_{2}$ (which
must exist by (C7) and (C8)) and choose a vertex $z\in(N_{H}(y)\cap
B_{1})\setminus(K\cup\\{z^{*}\\})$ (its existence follows from (5.7) and
(C6)), add $yz$ to $G_{2}$, and remove $xy$ and the edge of $M$ containing $z$
from $G_{2}$. (C8) guarantees that $z$ does not become an endpoint in the
resulting graph. Instead, $M(z)\in B_{2}$ becomes an endpoint.

  5. 5.

If $y\in C_{1}$, let $z$ be the other neighbour of $y$ in $G_{2}$ (which
exists by (C7) and (C8)), and note that $yz\in E(M)$ (which follows from
(C9)), so $z\in C_{2}$. Let $z^{*}$ be the other neighbour of $z$ in $G_{2}$
(which must exist, again, by (C7) and (C8)). Then, choose a vertex
$z^{\prime}\in(N_{H}(z)\cap B_{1})\setminus(K\cup\\{z^{*}\\})$ (recall that
its existence is guaranteed by (5.7) and (C6)), add $zz^{\prime}$ to $G_{2}$,
remove $xy$, $yz$ and the edge of $M$ containing $z^{\prime}$ from $G_{2}$,
and add $y$ to $S$. Again, by (C8), $z^{\prime}$ does not become an endpoint,
and $M(z^{\prime})\in B_{2}$ does.

Once this is done for all the desired edges, add $A\cup U$ to $S$.

Note that, by construction, the sizes of $S$, $D$ and $K$ increase by at most
$3$ for each edge $xy$ deleted following the previous process. It then follows
by $(\mathrm{H1})$, the definition of $U$ in Step 2 and (B9) that (C6) holds
throughout, and even after the last step of the process. The remaining
properties follow similarly as in Step 2. (C7) follows from the fact that,
throughout, we guarantee that all vertices of $G_{2}$ have degree at most $2$,
since we delete one edge incident to each of the vertices that lie in one of
the edges which will be added. (C8) holds since all the newly created
endpoints lie in $B_{2}$, as remarked throughout the process. Observe that
avoiding $z^{*}$ in cases 4 and 5 ensures that we do not create a new endpoint
in $C_{2}$. Finally, (C9) holds since the edges added to the graph in cases 4
and 5 have one endpoint in $B_{1}$ and the other in $C_{2}$ by construction.
Note that (C9) also holds after the process, that is, replacing $G_{2}$ by
$G_{3}$.

Let $G_{3}$ be the graph resulting from the process. (C1) must hold by (B4)
and since no edges incident to the internal vertices of $P$ are added nor
deleted throughout the process (which follows from (B12), (B13) and the fact
that $y\notin V(P)\setminus M(\\{x_{1},y_{t}\\})$ throughout). Furthermore,
the process above may again increase the number of paths and cycles, but, by
Remark 5.3, it creates at most one new cycle or path for each vertex $y$
above. This, combined with $(\mathrm{H1})$, the definition of $U$ in Step 2,
(5.4) and (B5), ensures that (C2) holds. (C3) follows by (C8) since, at the
end of the process, we have $A\cap V(G_{3})=\varnothing$; similarly, we have
that (C5) holds too. Finally, as happened in Step 2, all edges added in cases
4 and 5 above have one endpoint in $B_{1}$ and the other in $C_{2}$ (see
(C9)), so by (B7) we must have that (C4) holds.

Step 4. We now want to make sure that $P$ does not lie in a cycle. If $P$ is
not contained in a cycle, we are done, so assume it is contained in some cycle
$\mathcal{C}$. If $|E(\mathcal{C})|\leq|E(P)|+14$, simply delete
$E(\mathcal{C})\setminus E(P)$, and add $V(\mathcal{C})\setminus V(P)$ to $S$.
Otherwise, for each $x\in\\{M(x_{1}),M(y_{t})\\}$ (recall these are the
endpoints of $P$ and that they lie in $B_{2}$, see (B2)), we proceed as
follows. Let $y$ be the first vertex of $\mathcal{C}$ which lies in $B_{2}\cup
C_{2}$ when moving along $\mathcal{C}$ away from $P$ starting at $x$
(disregarding $x$ itself). Note that, by (C4) and Remark 5.2, we have that
$\operatorname{dist}_{\mathcal{C}}(x,y)\leq 3$. Now, delete all edges of the
shortest $(x,y)$-path of $\mathcal{C}$, and add all its internal vertices to
$S$. If $y\in B_{2}$, it becomes an endpoint and we are done; otherwise,
choose a vertex $z\in(N_{H}(y)\cap B_{1})\setminus(K\cup N_{G_{3}}(y))$ (which
must exist by (5.7) and (C6)), add $yz$ to $G_{1}$, and delete the edge of $M$
containing $z$. Note that, in this last case, $M(z)\in B_{2}$ becomes an
endpoint in the resulting graph.

Let $G_{4}$ be the resulting graph. We claim that the following properties are
satisfied:

  1. (D1)

$|S|,|D|,|K|\leq 5\log^{2}n$.

  2. (D2)

$P\subseteq G_{4}$. Furthermore, the component of $G_{4}$ containing $P$ is a
path.

  3. (D3)

$G_{4}$ is the union of at most $4\log^{2}n$ cycles and $(1+o(1))|R|/2$ paths,
all vertex-disjoint.

  4. (D4)

For each cycle $\mathcal{C}\subseteq G_{4}$ we have that $|V(\mathcal{C})\cap
B_{1}|=|V(\mathcal{C})\cap B_{2}|\pm 5\log^{2}n$.

  5. (D5)

Each of the paths of $G_{4}$ has both endpoints in $B_{2}\cup R$.

  6. (D6)

All edges in $G_{4}\setminus G_{1}^{\prime}$ are contained in $V(P)$ or have
one endpoint in $B_{1}$ and the other in $C_{2}$.

  7. (D7)

All subpaths of $G_{4}\setminus P$ have at most two consecutive vertices in
$R\cup B_{2}\cup C_{2}$ or in $B_{1}\cup C_{1}$.

Indeed, the sizes of $S$, $D$ and $K$ may increase by at most $14$ in this
step, so (D1) follows from (C6). (D2) follows from the construction, since no
edges incident to any vertex of $P$ have been removed (this follows by the
choice of the vertices $z$, (B12) and (B13)). Note that $G_{4}$ is a union of
paths and cycles since, again, we have made sure that every vertex has degree
at most $2$. Furthermore, even though the number of paths and cycles may have
increased with respect to $G_{3}$, by Remark 5.3 we have that they increase by
at most $2$. Therefore, (D3) follows from (C2) and (5.4). (D4) follows by
combining the bound on $|K|$ in (D1) with (A4). (D5) holds by construction and
(C3). Note, in particular, that the choices of the vertices $z$ together with
(C2) guarantee that we do not create any new endpoints in $C_{2}$. (D6)
follows from (C9) and the fact that the only edges we may have added in this
step have one endpoint in $B_{1}$ and the other in $C_{2}$. This in turn,
together with (C4), implies that (D7) holds.

Step 5. Now we want to obtain a graph $G_{5}$ which satisfies the following
properties:

  1. (E1)

$P\subseteq G_{5}$.

  2. (E2)

$G_{5}$ is the union of at most $(1+o(1))|R|/2$ paths, all vertex-disjoint.

  3. (E3)

Each of the paths of $G_{5}$ has both endpoints in $B_{2}\cup R$.

In order to achieve this, we must alter each cycle in $G_{4}$. Crucially, we
will show that, with these alterations, we do not create any new cycles. We
claim that, throughout the coming process, we may assume that the following
properties hold:

  1. (E4)

$|S|,|D|,|K|\leq 105\log^{2}n$.

  2. (E5)

$P\subseteq G_{4}$. Furthermore, the component of $G_{4}$ containing $P$ is a
path.

  3. (E6)

All subpaths of $G_{4}\setminus P$ have at most two consecutive vertices in
$R\cup B_{2}\cup C_{2}$ or in $B_{1}\cup C_{1}$.

Note that, before the process starts, (E4), (E5) and (E6) hold by (D1), (D2)
and (D7), respectively.

We proceed by iteratively choosing a cycle $\mathcal{C}\subseteq G_{4}$ and
considering the following cases.

  1. 1.

If $\mathcal{C}$ has length at most $25$, we delete all its edges and add all
its vertices to $S$.

  2. 2.

Otherwise, assume $\mathcal{C}$ contains two vertices $x,y\in B_{2}$ with
$\operatorname{dist}_{\mathcal{C}}(x,y)\leq 11$ and let
$Q\subseteq\mathcal{C}$ be an $(x,y)$-path of length
$\operatorname{dist}_{\mathcal{C}}(x,y)$. Then, remove all edges of $Q$ from
$G_{4}$ and add all its internal vertices to $S$.

  3. 3.

Otherwise, since all cycles in $G_{4}$ are disjoint from $R$ (as follows from
(A3), (D2), (D6) and the fact that no new cycles are created throughout this
step), by (E6), we may apply Remark 5.2 to conclude that $\mathcal{C}$ must
contain three vertices $x,y,z\in C_{2}$ such that
$\operatorname{dist}_{\mathcal{C}}(x,y)\leq 3$ and
$\operatorname{dist}_{\mathcal{C}}(y,z)\leq 3$.

######  Claim 3.

There exist distinct $v_{1},v_{2}\in\\{x,y,z\\}$ such that the following
holds.

Let $Q$ be the shortest $(v_{1},v_{2})$-path in $G_{4}$. For each $i\in[2]$,
there exists $w_{i}\in(N_{H}(v_{i})\cap B_{1})\setminus(K\cup
N_{\mathcal{C}}(v_{i}))$ (with $w_{1}\neq w_{2}$) such that, if we let $e_{i}$
be the edge of $M$ containing $w_{i}$, then $w_{1}$, $w_{2}$ and $v_{1}$ each
lie in a different component of $G_{4}\setminus(Q\cup\\{e_{1},e_{2}\\})$.

###### Proof.

Recall that any two vertices $x^{\prime},y^{\prime}\in V(\mathcal{C})\cap
B_{2}$ satisfy that
$\operatorname{dist}_{\mathcal{C}}(x^{\prime},y^{\prime})\geq 12$. By (E6) and
Remark 5.2, this means that $|V(\mathcal{C})\cap B_{2}|\leq|V(\mathcal{C})\cap
C_{2}|/3$. Therefore, by (5.6) we have that $|V(\mathcal{C})\cap
B_{2}|\leq\gamma_{1}n/3\leq 29n/1000$. Then, by (D4), we conclude that

$|V(\mathcal{C})\cap B_{1}|\leq 3n/100.$ (5.11)

Aiming for a contradiction, let us assume that the statement does not hold,
that is, for each pair $v_{1},v_{2}\in\\{x,y,z\\}$ we have that, for every
$w_{1}\in(N_{H}(v_{1})\cap B_{1})\setminus(K\cup N_{\mathcal{C}}(v_{1}))$ and
every $w_{2}\in(N_{H}(v_{2})\cap B_{1})\setminus(K\cup
N_{\mathcal{C}}(v_{2}))$ with $w_{2}\neq w_{1}$, if for each $i\in[2]$ we let
$e_{i}$ be the edge of $M$ containing $w_{i}$ (which, recall, must lie in
$G_{4}$ by the definition of $K$), then at least two of the vertices $w_{1}$,
$w_{2}$ and $v_{1}$ lie in the same component of
$G_{4}\setminus(Q\cup\\{e_{1},e_{2}\\})$. Let $X\coloneqq(N_{H}(x)\cap
B_{1})\setminus(K\cup V(\mathcal{C}))$, $Y\coloneqq(N_{H}(y)\cap
B_{1})\setminus(K\cup V(\mathcal{C}))$ and $Z\coloneqq(N_{H}(z)\cap
B_{1})\setminus(K\cup V(\mathcal{C}))$. In particular, every vertex in $X\cup
Y\cup Z$ lies in an edge of $M$ in $G_{4}$.

Consider $x$ and $y$, and let $x_{1}\in X$ and $y_{1}\in Y$ be distinct (such
vertices exist by (5.7), (E4), and (5.11)). Let $Q_{xy}$ be the shortest
$(x,y)$-path in $\mathcal{C}$, and let $e_{x}$ and $e_{y}$ be the edges of $M$
which contain $x_{1}$ and $y_{1}$, respectively. Our choice of $x_{1}$ and
$y_{1}$ guarantees that, in $G_{4}\setminus(Q_{xy}\cup\\{e_{x},e_{y}\\})$,
they lie in a different component than $x$ (and $y$), so $x_{1}$ and $y_{1}$
must lie in the same component. Let $F$ be the component of $G_{4}$ containing
$x_{1}$ and $y_{1}$. By fixing $x_{1}$, if any choice of $y_{2}\in
Y\setminus\\{x_{1}\\}$ lies in a component of $G_{4}$ different from $F$, we
would reach a contradiction, so we must have that $Y\subseteq V(F)$, and
similarly we have $X\subseteq V(F)$.

Assume first that $F$ is a path, and let $u_{F}$ and $v_{F}$ be its endpoints.
Given any pair of vertices $a,b\in V(F)$, we write that $a<_{F}b$ if a
traversal of $F$ starting at $u_{F}$ reaches $a$ before $b$. Now assume that
$x_{1},x_{2}\in X$ and $y_{1}\in Y$ satisfy that $x_{1}<_{F}y_{1}<_{F}x_{2}$.
Then, upon deleting the edge of $M$ containing $y_{1}$, it cannot be in the
same component as both $x_{1}$ and $x_{2}$, so we would reach a contradiction.
Thus, we must have that $x_{1}<_{F}y_{1}$ for all $x_{1}\in X$ and $y_{1}\in
Y\setminus\\{x_{1}\\}$, or $y_{1}<_{F}x_{1}$ for all $x_{1}\in X$ and
$y_{1}\in Y\setminus\\{x_{1}\\}$. In particular, this implies that $|X\cap
Y|\leq 1$. One can similarly show that, if $F$ is a cycle, then $|X\cap Y|\leq
2$.

By following the same arguments as above when considering $y$ and $z$, and $x$
and $z$, we conclude that $Z\subseteq V(F)$ and that $|Y\cap Z|\leq 2$ and
$|X\cap Z|\leq 2$. Combining this with (5.7), (E4), and (5.11), we have that
$|X\cup Y\cup Z|\geq 101n/200$. But $X\cup Y\cup Z\subseteq B_{1}$ and
$|B_{1}|\leq n/2$, the final contradiction. ∎

Let $v_{1},v_{2},w_{1},w_{2},e_{1},e_{2}$ be given by 3. Delete $E(Q)$,
$e_{1}$ and $e_{2}$ from $G_{4}$, add $v_{1}w_{1}$ and $v_{2}w_{2}$ to
$G_{4}$, and add all internal vertices of $Q$ to $S$.

Observe that, in cases 1 and 2, we trivially cannot create any new cycles,
since no edges are added to the graph. By Remark 5.4, we are also guaranteed
that we do not create a new cycle in case 3. This, together with (D3), means
that the process described above is repeated at most $4\log^{2}n$ times. Since
in each iteration we delete at most $25$ edges (with the bound coming from
case 1), (E4) follows from (D1). The fact that $P\subseteq G_{4}$ holds since,
by (B12), (B13), the fact that $P$ is not contained in a cycle and the choices
throughout the process, no edges incident to $P$ are added nor deleted. The
fact that no new cycles are created then implies that (E5) must hold
throughout. Finally, (E6) follows from the fact that all added edges have one
endpoint in $B_{1}$ and the other in $C_{2}$. All three properties must also
hold after the process is finished.

Let $G_{5}$ be the graph resulting from the process above. (E1) follows
directly from (E5). (E2) follows from (D3), (5.4), (E4) and since the increase
in the number of paths in each iteration of the above process is clearly
bounded by $3$. Finally, (E3) holds by (D5) and the construction (in
particular, note that the choice of $w_{1}$ and $w_{2}$ guarantees that no
endpoint is created in $C_{2}$).

Step 6. Recall that, together, the paths described in (E3) cover all vertices
of $V(H)\setminus S$. We are now going to iteratively combine the paths which
conform $G_{5}$ into a single path with the same vertex set. We will later
turn this path into a cycle and absorb all vertices of $S$ into it. For
simplicity of notation, from now on we update $G_{5}$ as well as $D$ in each
step; $S$ and $K$, however, are no longer updated.

To be more precise, our aim is to obtain a graph $G_{6}$ which satisfies the
following properties:

  1. (F1)

$P\subseteq G_{6}$.

  2. (F2)

$G_{6}$ consists of a unique path on vertex set $V(H)\setminus S$.

  3. (F3)

The endpoints of the path of $G_{6}$ lie in $B_{2}\cup R$.

To achieve this, we will follow a process, each iteration of which reduces the
number of components of $G_{5}$ by one. We claim that the following properties
hold throughout:

  1. (F4)

$|D|\leq(1+o(1))|R|/2$.

  2. (F5)

$G_{5}$ is a union of vertex-disjoint paths.

  3. (F6)

The endpoints of all paths of $G_{5}$ lie in $B_{2}\cup R$.

Observe that, before the process starts, (F4) follows from (E4) and (5.4),
(F5) holds by (E2), and (F6) follows from (E3).

We proceed as follows. While $G_{5}$ contains at least two paths, choose any
such two paths $P_{1}$ and $P_{2}$, and let $x$ be an endpoint of $P_{1}$, and
$y$ be an endpoint of $P_{2}$. In particular, by (F6), $x,y\in B_{2}\cup R$.
Choose some edge $e=zz^{\prime}\in E_{G}(N_{H}(x)\cap N_{H}(y)\cap
B_{1})\setminus D$ (which must exist by (G2), (5.9) and (F4)).

  * •

If $e\notin E(P_{1})\cup E(P_{2})$, add the edges $xz$ and $yz^{\prime}$ to
$G_{5}$ and remove $zz^{\prime}$.

  * •

Otherwise, suppose $e\in E(P_{1})$ and that
$\operatorname{dist}_{P_{1}}(x,z)<\operatorname{dist}_{P_{1}}(x,z^{\prime})$
(the other cases are similar). Then, remove $zz^{\prime}$ from $G_{5}$ and add
$xz^{\prime}$ and $yz$.

In both cases, we clearly reduce the number of paths by one. Furthermore, in
each step we delete exactly one edge from $G_{5}$. This, together with (E2)
and (E4), guarantees that (F4) holds throughout (and, in particular, this
implies the process can indeed be carried out). (F5) follows by construction,
as does (F6), since no new endpoints are created throughout.

Let $G_{6}$ be the graph resulting from the process so far. As the process
ends, (F2) and (F3) follow by construction. Finally, (F1) holds since, in all
cases above, no edges incident to $V(P)$ are removed or added to the graph, as
guaranteed by (B3).

We can now complete the proof. Let the endpoints of the unique component of
$G_{6}$ (see (F2)) be $x$ and $y$. By (F3) we have $x,y\in B_{2}\cup R$, so by
(G2), (5.9) and (F4) we can take some edge $e=zz^{\prime}\in
E_{G}(N_{H}(x)\cap N_{H}(y)\cap B_{1})\setminus D$. Assume without loss of
generality that
$\operatorname{dist}_{P^{\prime}}(x,z)<\operatorname{dist}_{P^{\prime}}(x,z^{\prime})$.
Then, by (B3) and (F1), removing $zz^{\prime}$ from $G_{3}$ and adding
$xz^{\prime}$ and $yz$ results in a cycle $\mathcal{C}$ with the same vertex
set and such that $P\subseteq\mathcal{C}$. Let $m\coloneqq|S|$, so
$\mathcal{C}$ has length $n-m$. We must now prove that there is a cycle of
length $k$, for all $3\leq k\leq n$. We split our analysis into three cases.

Assume first that $n-m\leq k\leq n$. Consider a set $J\subseteq S$ with
$|J|=k+m-n$. For each $w\in J\setminus U$, choose a distinct edge
$e_{w}=x_{w}y_{w}\in E_{G}(N_{H}(w))\setminus D$ (recall that for each $w\in
U$ we have $w=u_{i}$ for some $i\in[t]$ and we already defined an edge
$e_{w}\coloneqq x_{i}y_{i}$ in Step 2). Note that (G1), (5.10), (E4) and (F4)
guarantee that there is a choice of edges as desired. Then, for each $w\in J$,
replace $e_{w}$ by the path $x_{w}wy_{w}$. This clearly results in a cycle of
the desired length.

Suppose next that $3\leq k\leq\alpha^{2}n/10$. In such a case, consider any
subpath $P^{\prime}\subseteq\mathcal{C}$ of length $k-3$, and let its
endpoints be $x$ and $y$. Now choose any edge $zz^{\prime}\in
E_{G}(N_{H}(x),N_{H}(y))$ such that $z,z^{\prime}\notin V(P^{\prime})$ (the
existence of such an edge follows by (G1) and (E4)). Then, the union of
$P^{\prime}$ and the path $xzz^{\prime}y$ forms a cycle of length $k$.

Finally, assume $\alpha^{2}n/10<k<n-m$. Consider a subpath
$P^{\prime}\subseteq\mathcal{C}$ of length $k-3$ such that $P\subseteq
P^{\prime}$. Let the endpoints of $P^{\prime}$ be $x$ and $y$, respectively,
and let $Z\coloneqq E_{G}(N_{H}(x),N_{H}(y))\setminus D$ (for notational
purposes, when we write $zz^{\prime}\in Z$ we assume that $z\in N_{H}(x)$ and
$z^{\prime}\in N_{H}(y)$). Note that (G1), (5.10) and (F4) imply that

$|Z|\geq\eta\alpha^{2}n.$ (5.12)

Recall that, by (B3), $Z$ and $P$ are vertex-disjoint. We consider the
following three cases.

  1. 1.

Assume that there exists $zz^{\prime}\in Z$ such that $z,z^{\prime}\notin
V(P^{\prime})$. Then, the union of $P^{\prime}$ and the path $xzz^{\prime}y$
forms a cycle of length $k$.

  2. 2.

Otherwise, let $Z^{\prime}\coloneqq\\{e\in Z:e\subseteq V(P^{\prime})\\}$, so
we have that $Z^{\prime}\subseteq E(P^{\prime})$ and

$|Z^{\prime}|\geq|Z|-2\geq\eta\alpha^{2}n/2$ (5.13)

by (5.12). Suppose there is an edge $zz^{\prime}\in Z^{\prime}$ such that
$\operatorname{dist}_{P^{\prime}}(x,z^{\prime})<\operatorname{dist}_{P^{\prime}}(x,z)$.
If so, then $(P^{\prime}\setminus\\{zz^{\prime}\\})\cup\\{xz,yz^{\prime}\\}$
is a cycle of length $k-2$ which contains $P$. To obtain a cycle of length
$k$, replace $x_{1}y_{1}$ and $x_{2}y_{2}$ by the paths $x_{1}u_{1}y_{1}$ and
$x_{2}v_{2}y_{2}$, respectively.

  3. 3.

Otherwise, $Z^{\prime}\subseteq E(P^{\prime})$ and all $zz^{\prime}\in
Z^{\prime}$ satisfy that
$\operatorname{dist}_{P^{\prime}}(x,z)<\operatorname{dist}_{P^{\prime}}(x,z^{\prime})$.
Note that all edges in $Z^{\prime}$ are pairwise vertex-disjoint by
definition. Choose two edges $zz^{\prime},ww^{\prime}\in Z^{\prime}$ with
$\operatorname{dist}_{P^{\prime}}(x,z)<\operatorname{dist}_{P^{\prime}}(x,w)$
which minimise $\operatorname{dist}_{P^{\prime}}(z,w)$ over all possible pairs
of edges. Let $P^{\prime\prime}$ be the $(z^{\prime},w)$-subpath of
$P^{\prime}$, and let $\ell\coloneqq\operatorname{dist}_{P^{\prime}}(z,w)$. By
an averaging argument using (5.13), it follows that $1\leq\ell\leq
2|V(P^{\prime})|/(\eta\alpha^{2}n)<2\eta^{-1}\alpha^{-2}<t$. In particular,
this shows that $P\nsubseteq P^{\prime\prime}$, so we must have $P\subseteq
P^{\prime}\setminus P^{\prime\prime}$. Then, the graph $(P^{\prime}\setminus
E(P^{\prime\prime}))\cup\\{xw,yz^{\prime}\\}$ is a cycle of length $k-\ell$
which contains $P$. In order to obtain a cycle of length $k$, replace
$u_{1},\ldots,u_{\ell}$ by $x_{1}u_{1}y_{1},\ldots,x_{\ell}u_{\ell}y_{\ell}$.∎

##  6\. Concluding remarks and open problems

Binomial random graphs and random regular graphs are perhaps the two most
studied random graph models. As we have mentioned in the introduction, many
results about randomly perturbed graphs have been obtained for the binomial
random graph; it thus seems natural to study analogous problems in random
regular graphs. We believe it would be interesting to study graphs perturbed
by a random graph with a fixed degree sequence as well. Very recently, the
first author has also considered Hamiltonicity of graphs perturbed by a random
geometric graph [18]. Of course, this study should also be extended to other
graph properties.

As we have observed, the behaviour of the graph $H$ perturbed by $G_{n,d}$
when $d=1$ and $d=2$ is quite different. When $d=1$, we have shown that, if
$\delta(H)\geq\alpha n$ with $\alpha>\sqrt{2}-1$, then a.a.s. $H\cup G_{n,1}$
is Hamiltonian, but the same is not necessarily true if $\alpha<\sqrt{2}-1$.
On the other hand, for $d=2$, we have shown that $H\cup G_{n,2}$ is a.a.s.
Hamiltonian for far sparser graphs $H$ ($\delta(H)=\omega(n^{3/4}(\log
n)^{1/4})$ suffices). We believe this is far from optimal and should be true
for even sparser graphs $H$. We thus propose the following question.

######  Question 6.1.

What is the minimum $f=f(n)$ such that, for every $n$-vertex graph $H$ with
$\delta(H)\geq f$, a.a.s. $H\cup G_{n,2}$ is Hamiltonian?

The only lower bound we can provide for this question is of order $\log{n}$,
which is very far from the upper bound given by Theorem 1.1. Indeed, consider
an $n$-vertex complete unbalanced bipartite graph $H=(A,B,E)$ where
$|A|=\log{n}/5$. It follows by a standard concentration argument (in the proof
of Lemma 3.1$(\mathrm{i})$, one can see that the variables $X_{i}$ are
actually independent, hence standard Chernoff bounds are applicable) that
a.a.s. $G_{n,2}[B]$ contains at least $\log{n}/2$ cycles. Upon conditioning on
this event, it is easy to check that $H\cup G_{n,2}$ does not contain a
Hamilton cycle.

From an algorithmic perspective, by retracing our proofs of Theorems 1.1,
LABEL:, 1.2, LABEL: and 1.3 as well as Lemma 5.1, it easily follows that,
given an $n$-vertex graph $H$ with $\delta(H)\geq\alpha n$ and any $d$-regular
graph $G$ which satisfies the statements of Lemmas 3.1 and 3.3 (the latter
with respect to the sets defined in each of the proofs, which can be checked
in polynomial time), there is a polynomial-time algorithm that finds cycles of
any given length in $H\cup G$.

One could consider a generalisation of the results we have obtained for random
perfect matchings by considering random $F$-factors (where an $F$-factor is a
union of vertex-disjoint copies of $F$ which together cover the vertex set),
for some fixed graph $F$, assuming the necessary divisibility conditions. In
general, we believe the behaviour here will be similar to that of random
perfect matchings: if $G$ is a uniformly random $n$-vertex $F$-factor, there
will exist a specific value $\alpha^{*}=\alpha^{*}(F)\in(0,1/2)$, independent
of $n$, such that, for every $\epsilon>0$, the following hold:

  * •

for every $n$-vertex graph $H$ with $\delta(H)\geq(1+\epsilon)\alpha^{*}n$,
a.a.s. $H\cup G$ is Hamiltonian, and

  * •

there exists some $n$-vertex graph $H$ with
$\delta(H)\geq(1-\epsilon)\alpha^{*}n$ such that $H\cup G$ is not a.a.s.
Hamiltonian.

Theorem 1.2 asserts that $\alpha^{*}(K_{2})=\sqrt{2}-1$. We propose the
following conjecture.

######  Conjecture 6.2.

For all $r\geq 2$, we have that $\alpha^{*}(K_{r})$ is the unique real
positive solution to the equation $x^{r}+rx-1=0$.

The lower bound for the conjectured value of $\alpha^{*}(K_{r})$ is given by
the same extremal example as for perfect matchings, that is, a complete
unbalanced bipartite graph. Indeed, consider a complete bipartite graph with
parts $A$ and $B$, where $|A|=\alpha n$ and $|B|=(1-\alpha)n$, and let $G$ be
a uniformly random $n$-vertex $K_{r}$-factor. We are going to estimate the
number of cliques of each size in $G[B]$. For each $s\in[r]$, let $X_{s}$ be
the number of components of $G[B]$ which are isomorphic to $K_{s}$. Fix a
vertex $v\in B$. For each $s\in[r]$, the probability that the component
containing $v$ in $G[B]$ is isomorphic to $K_{s}$ is (roughly) given by

$\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{(1-\alpha)n}{s-1}\kern-1.00006pt\right)\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{\alpha
n}{r-s}\kern-1.00006pt\right)\frac{1}{\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{r-1}\kern-1.00006pt\right)}.$

Thus, we have that

$\mathbb{E}[X_{s}]\approx(1-\alpha)n\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{(1-\alpha)n}{s-1}\kern-1.00006pt\right)\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{\alpha
n}{r-s}\kern-1.00006pt\right)\frac{1}{\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{r-1}\kern-1.00006pt\right)}\frac{1}{s}\approx\frac{n}{r}\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{r}{s}\kern-1.00006pt\right)(1-\alpha)^{s}\alpha^{r-s}.$

Now observe that, since $H$ is a complete bipartite graph, in building a
longest cycle, each vertex of $A$ can ‘absorb’ each of the components of
$G[B]$. The conclusion is that, if the number of such components is larger
than the number of vertices in $A$, then a Hamilton cycle is impossible. That
is, a necessary condition for a Hamilton cycle would be that

$\sum_{s=1}^{r}X_{s}\leq\alpha n.$

If we consider the expectations (for the lower bound, Markov’s inequality
provides sufficient concentration), we have that

$\sum_{s=1}^{r}\mathbb{E}[X_{s}]\approx\frac{n}{r}\sum_{s=1}^{r}\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{r}{s}\kern-1.00006pt\right)(1-\alpha)^{s}\alpha^{r-s}=\frac{n}{r}(1-\alpha^{r}),$

so our necessary condition becomes

$\frac{n}{r}(1-\alpha^{r})\leq\alpha n\iff\alpha^{r}+r\alpha-1\geq 0.$

We think the problem might be interesting for other instances of $F$ as well.

In a different direction, we also believe the problem could be interesting for
hypergraphs. In particular, following work of Altman, Greenhill, Isaev and
Ramadurai [1], it is known that for every integer $r\geq 2$ there exists an
(explicit) constant $\rho(r)$ such that a random $d$-regular $r$-uniform
hypergraph $G_{n,d}^{(r)}$ a.a.s. contains a loose Hamilton cycle if
$d>\rho(r)$, and a.a.s. does not contain such a cycle if $d\leq\rho(r)$. We
propose the following question.

######  Question 6.3.

Let $r\geq 3$ be an integer. For each $d\leq\rho(r)$, for which values of
$\alpha$ (possibly as a function of $n$) is it true that for any $n$-vertex
$r$-uniform hypergraph $H$ with $\delta(H)\geq\alpha n^{r-1}$ we have that
a.a.s. $H\cup G_{n,d}^{(r)}$ contains a loose Hamilton cycle?

## Acknowledgement

We would like to thank Padraig Condon for nice discussions at an early stage
of this project. We are also indebted to the anonymous referees for their
helpful comments and suggestions.

## References

  * Altman, Greenhill, Isaev and Ramadurai [2020] D. Altman, C. Greenhill, M. Isaev and R. Ramadurai, ‘A threshold result for loose Hamiltonicity in random regular uniform hypergraphs’. _J. Combin. Theory Ser. B_ 142 (2020), 307–373, doi: 10.1016/j.jctb.2019.11.001.
  * Antoniuk, Dudek, Reiher, Ruciński and Schacht [2021] S. Antoniuk, A. Dudek, C. Reiher, A. Ruciński and M. Schacht, ‘High powers of Hamiltonian cycles in randomly augmented graphs’. _Journal of Graph Theory_ 98.2 (2021), 255–284, doi: 10.1002/jgt.22691.
  * Balogh, Treglown and Wagner [2019] J. Balogh, A. Treglown and A. Z. Wagner, ‘Tilings in randomly perturbed dense graphs’. _Combin. Probab. Comput._ 28 (2019), 159–176, doi: 10.1017/S0963548318000366.
  * Bedenknecht, Han, Kohayakawa and Mota [2019] W. Bedenknecht, J. Han, Y. Kohayakawa and G. O. Mota, ‘Powers of tight Hamilton cycles in randomly perturbed hypergraphs’. _Random Structures Algorithms_ 55 (2019), 795–807, doi: 10.1002/rsa.20885.
  * Bohman, Frieze and Martin [2003] T. Bohman, A. Frieze and R. Martin, ‘How many random edges make a dense graph Hamiltonian?’ _Random Structures Algorithms_ 22 (2003), 33–42, doi: 10.1002/rsa.10070.
  * Bollobás [1980] B. Bollobás, ‘A probabilistic proof of an asymptotic formula for the number of labelled regular graphs’. _European J. Combin._ 1 (1980), 311–316, doi: 10.1016/S0195-6698(80)80030-8.
  * Böttcher, Han, Kohayakawa, Montgomery, Parczyk and Person [2019] J. Böttcher, J. Han, Y. Kohayakawa, R. Montgomery, O. Parczyk and Y. Person, ‘Universality for bounded degree spanning trees in randomly perturbed graphs’. _Random Structures Algorithms_ 55 (2019), 854–864, doi: 10.1002/rsa.20850.
  * Böttcher, Montgomery, Parczyk and Person [2020] J. Böttcher, R. Montgomery, O. Parczyk and Y. Person, ‘Embedding spanning bounded degree graphs in randomly perturbed graphs’. _Mathematika_ 66 (2020), 422–447, doi: 10.1112/mtk.12005.
  * Böttcher, Parczyk, Sgueglia and Skokan [2020] J. Böttcher, O. Parczyk, A. Sgueglia and J. Skokan, ‘Triangles in randomly perturbed graphs’. _arXiv e-prints_ (2020). arXiv: 2011.07612.
  * Böttcher, Parczyk, Sgueglia and Skokan [2021] ———, ‘Cycle factors in randomly perturbed graphs’. _arXiv e-prints_ (2021). arXiv: 2103.06136.
  * Böttcher, Parczyk, Sgueglia and Skokan [2022] ———, ‘The square of a Hamilton cycle in randomly perturbed graphs’. _arXiv e-prints_ (2022). arXiv: 2202.05215.
  * Chang, Han and Thoma [2020] Y. Chang, J. Han and L. Thoma, ‘On powers of tight Hamilton cycles in randomly perturbed hypergraphs’. _arXiv e-prints_ (2020). arXiv: 2007.11775.
  * Condon, Espuny Díaz, Girão, Kühn and Osthus [2020] P. Condon, A. Espuny Díaz, A. Girão, D. Kühn and D. Osthus, ‘Hamiltonicity of random subgraphs of the hypercube’. _arXiv e-prints_ (2020). arXiv: 2007.02891.
  * Condon, Espuny Díaz, Girão, Kühn and Osthus [2021] ———, ‘Dirac’s theorem for random regular graphs’. _Combin. Probab. Comput._ 30 (2021), 17–36, doi: 10.1017/S0963548320000346.
  * Cooper, Frieze and Reed [2002] C. Cooper, A. Frieze and B. Reed, ‘Random regular graphs of non-constant degree: connectivity and Hamiltonicity’. _Combin. Probab. Comput._ 11 (2002), 249–261, doi: 10.1017/S0963548301005090.
  * Dirac [1952] G. A. Dirac, ‘Some theorems on abstract graphs’. _Proc. London Math. Soc._ 2 (1952), 69–81, doi: 10.1112/plms/s3-2.1.69.
  * Dudek, Reiher, Ruciński and Schacht [2020] A. Dudek, C. Reiher, A. Ruciński and M. Schacht, ‘Powers of Hamiltonian cycles in randomly augmented graphs’. _Random Structures Algorithms_ 56 (2020), 122–141, doi: 10.1002/rsa.20870.
  * Espuny Díaz [2021] A. Espuny Díaz, ‘Hamiltonicity of graphs perturbed by a random geometric graph’. _arXiv e-prints_ (2021). arXiv: 2102.02321.
  * Hahn-Klimroth, Maesaka, Mogge, Mohr and Parczyk [2021] M. Hahn-Klimroth, G. S. Maesaka, Y. Mogge, S. Mohr and O. Parczyk, ‘Random perturbation of sparse graphs’. _Electron. J. Comb._ 28.2 (2021), research paper p2.26, 12, doi: 10.37236/9510.
  * Han, Morris and Treglown [2020] J. Han, P. Morris and A. Treglown, ‘Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu’. _Random Structures Algorithms_ (2020), 1–37, doi: 10.1002/rsa.20981.
  * Han and Zhao [2020] J. Han and Y. Zhao, ‘Hamiltonicity in randomly perturbed hypergraphs’. _J. Combin. Theory Ser. B_ 144 (2020), 14–31, doi: 10.1016/j.jctb.2019.12.005.
  * Joos and Kim [2020] F. Joos and J. Kim, ‘Spanning trees in randomly perturbed graphs’. _Random Structures Algorithms_ 56 (2020), 169–219, doi: 10.1002/rsa.20886.
  * Koršunov [1977] A. D. Koršunov, ‘Solution of a problem of P. Erdős and A. Rényi on Hamiltonian cycles in undirected graphs’. _Metody Diskretn. Anal._ 31 (1977), 17–56.
  * Krivelevich, Kwan and Sudakov [2016] M. Krivelevich, M. Kwan and B. Sudakov, ‘Cycles and matchings in randomly perturbed digraphs and hypergraphs’. _Combin. Probab. Comput._ 25 (2016), 909–927, doi: 10.1017/S0963548316000079.
  * Krivelevich, Kwan and Sudakov [2017] ———, ‘Bounded-degree spanning trees in randomly perturbed graphs’. _SIAM J. Discrete Math._ 31 (2017), 155–171, doi: 10.1137/15M1032910.
  * Krivelevich, Sudakov, Vu and Wormald [2001] M. Krivelevich, B. Sudakov, V. H. Vu and N. C. Wormald, ‘Random regular graphs of high degree’. _Random Structures Algorithms_ 18 (2001), 346–363, doi: 10.1002/rsa.1013.
  * McDowell and Mycroft [2018] A. McDowell and R. Mycroft, ‘Hamilton $\ell$-cycles in randomly perturbed hypergraphs’. _Electron. J. Combin._ 25 (2018), Paper No. 4.36, 30, doi: 10.37236/7671.
  * Nenadov and Trujić [2021] R. Nenadov and M. Trujić, ‘Sprinkling a few random edges doubles the power’. _SIAM J. Discrete Math._ 35.2 (2021), 988–1004, doi: 10.1137/19M125412X.
  * Robinson and Wormald [1992] R. W. Robinson and N. C. Wormald, ‘Almost all cubic graphs are Hamiltonian’. _Random Structures Algorithms_ 3 (1992), 117–125, doi: 10.1002/rsa.3240030202.
  * Robinson and Wormald [1994] ———, ‘Almost all regular graphs are Hamiltonian’. _Random Structures Algorithms_ 5 (1994), 363–374, doi: 10.1002/rsa.3240050209.
  * Wormald [1999] N. C. Wormald, ‘Models of random regular graphs’. _Surveys in combinatorics, 1999 (Canterbury)_ , _London Math. Soc. Lecture Note Ser._ , vol. 267, 239–298, Cambridge Univ. Press, Cambridge (1999).