# Ramsey numbers of bounded degree trees versus general graphs

Richard Montgomery Mathematics Institute, University of Warwick, Coventry CV4
7AL, UK<EMAIL_ADDRESS>Matías Pavez-Signé Centro de
Modelamiento Matemático (CNRS IRL2807), Universidad de Chile, Santiago, Chile.
<EMAIL_ADDRESS>Jun Yan  Mathematics Institute, University of Warwick,
Coventry CV4 7AL, UK<EMAIL_ADDRESS>

RM and MPS supported by the European Research Council (ERC) under the European
Union Horizon 2020 research and innovation programme (grant agreement No.
947978) and the Leverhulme Trust.

JY supported by the Warwick Mathematics Institute Centre for Doctoral
Training, and by funding from the UK EPSRC (Grant number: EP/W523793/1)

###### Abstract

For every $k\geq 2$ and $\Delta$, we prove that there exists a constant
$C_{\Delta,k}$ such that the following holds. For every graph $H$ with
$\chi(H)=k$ and every tree with at least $C_{\Delta,k}|H|$ vertices and
maximum degree at most $\Delta$, the Ramsey number $R(T,H)$ is
$(k-1)(|T|-1)+\sigma(H)$, where $\sigma(H)$ is the size of a smallest colour
class across all proper $k$-colourings of $H$. This is tight up to the value
of $C_{\Delta,k}$, and confirms a conjecture of Balla, Pokrovskiy, and
Sudakov.

##  1 Introduction

Given two graphs $G$ and $H$, the Ramsey number $R(G,H)$ is defined as the
smallest integer $N$ such that every red/blue colouring of the edges of the
complete graph $K_{N}$ contains either a red copy of $G$ or a blue copy of
$H$. The fundamental result of Ramsey [25] implies that $R(G,H)$ is well-
defined for any pair of graphs $G$ and $H$. The exact value of $R(G,H)$ is
known for very few pairs of graphs $(G,H)$, and in general it is difficult
even to give good bounds on $R(G,H)$. Of the few exact Ramsey numbers known,
many share the same general extremal lower bound construction given below. The
area of _Ramsey goodness_ studies the graphs $G$ and $H$ for which this lower
bound is tight.

Erdős showed in 1947 that the Ramsey number of an $n$-vertex path $P_{n}$ and
a complete $m$-vertex graph $K_{m}$ is $R(P_{n},K_{m})=(m-1)(n-1)+1$. Here,
the lower bound construction is the disjoint union of $m-1$ red $(n-1)$-vertex
cliques with all possible edges in blue added between them. As Chvátal and
Harary [9] observed, this construction contains no connected red $n$-vertex
subgraph and no blue subgraph with chromatic number at least $m$; if $G$ is
connected, we therefore have $R(G,H)\geq(\chi(H)-1)(|G|-1)+1$. Let $\sigma(H)$
denote the size of a smallest colour class across all proper
$\chi(H)$-colourings of $H$. If $2\leq\sigma(H)\leq|G|$, then this
construction can be improved by adding further a red clique of order
$\sigma(H)-1$ connected to the rest of the construction with blue edges. This
observation, made by Burr [6], implies that for every connected graph $G$ with
$|G|\geq\sigma(H)$ we have

$R(G,H)\geq(|G|-1)(\chi(H)-1)+\sigma(H).$ (1.1)

As coined by Burr and Erdős [7] in 1983, we say that a graph $G$ is _$H$
-good_ if (1.1) holds with equality, that is, if
$R(G,H)=(|G|-1)(\chi(H)-1)+\sigma(H)$. A family of graphs $\mathcal{G}$ is
said to be _$H$ -good_ if there is some $n_{0}$ such that every graph
$G\in\mathcal{G}$ is $H$-good if $|G|\geq n_{0}$. Chvátal [8] had already
shown in 1977 that the family of trees is $K_{r}$-good for all $r$. Inspired
by this, Burr and Erdős sought to determine which families $\mathcal{G}$ are
$K_{r}$-good for all $r$. They showed that, for each fixed $b$, the family of
graphs with bandwith at most $b$ is $K_{r}$-good for all $r$, and raised a
series of questions concerning the $K_{r}$-goodness of various natural
families [7].

In 1985, Erdős, Faudree, Rousseau, and Schelp [11] showed that the family of
bounded degree trees is $H$-good for any graph $H$, where some (possibly much
weaker) restriction on the maximum degree is needed (see [5]). All but one of
the Burr-Erdős questions raised in [7] were solved by Nikiforov and Rousseau
[22] in 2009, mostly as a result of their proof of the $K_{r}$-goodness for
each $r$ of any family of graphs with constant maximum degree which have a
‘small’ set of vertices whose removal divides the graph into small linear-
sized components (see [22] for a more precise statement). The last question in
[7] was solved by Fiz Pontiveros, Griffiths, Morris, Saxton, and Skokan [12]
in 2014, who proved that the $n$-dimensional hypercube $Q_{n}$ is $H$-good if
$n$ is sufficiently large. Beyond these questions, Allen, Brightwell, and
Skokan [1] showed in 2013 that the family of graphs $G$ with constant maximum
degree and bandwith $o(|G|)$ is $H$-good for every graph $H$.

More recently, focus has been turned on quantitative considerations of the
Ramsey goodness problem. That is, when $\mathcal{G}$ is an $H$-good family,
how large does $n_{0}$ need to be before every $G\in\mathcal{G}$ is $H$-good
if $|G|\geq n_{0}$. As their result quoted above shows that for any graph $H$,
the path $P_{n}$ and the $n$-vertex cycle $C_{n}$ are $H$-good if $n$ is
sufficiently large depending on $H$, Allen, Brightwell, and Skokan [1]
conjectured that $n\geq\chi(H)|H|$ should be sufficient. In the case of paths,
this was proved in a strong form when $\chi(H)\geq 4$ by Pokrovskiy and
Sudakov [23], who showed that, if $n\geq 4|H|$, then $P_{n}$ is $H$-good. For
cycles, Pokrovskiy and Sudakov [24] later showed that $C_{n}$ is $H$-good as
long as $n\geq 10^{60}|H|$ and $\sigma(H)\geq\chi(H)^{22}$. This result was
recently improved by Haslegrave, Hyde, Kim, and Liu [16], who showed that, for
some universal $C>0$, $n\geq C|H|\log^{4}\chi(H)$ is sufficient for the cycle
$C_{n}$ to be $H$-good, which is optimal up to the logarithmic factor of
$\chi(H)$ and confirms the conjecture of Allen, Brightwell, and Skokan for
graphs with large enough chromatic number.

Though not mentioned explicitly, quantitative bounds can be taken more
generally for the Ramsey goodness of bounded degree trees from the proof of
Erdős, Faudree, Rousseau, and Schelp [11] mentioned above. That is, the proof
can be used to show that, for each $k$ and $\Delta$, there is some
$C_{\Delta,k}$ such that for each graph $H$ with $\chi(H)=k$ and each $n\geq
C_{\Delta,k}|H|^{4}$, every $n$-vertex tree $T$ with maximum degree at most
$\Delta$ is $H$-good. This was improved by Balla, Pokrovskiy, and Sudakov [2]
in 2018, who proved that $n\geq C_{\Delta,k}|H|\log^{4}|H|$ suffices, for some
appropriate $C_{\Delta,k}$. Furthermore, they showed the factor $\log^{4}|H|$
is not needed when $T$ has $\Omega(n)$ leaves, and conjectured this should be
true for every tree, that is, that $n\geq C_{\Delta,k}|H|$ should suffice for
$T$ to be $H$-good. The purpose of this paper is to confirm this conjecture,
as follows.

######  Theorem 1.1.

For all $\Delta$ and $k$, there exists a constant $C_{\Delta,k}$ such that the
following holds. Given a graph $H$ with $\chi(H)=k$ and $n\geq
C_{\Delta,k}|H|$, every $n$-vertex tree $T$ with maximum degree at most
$\Delta$ is $H$-good. In other words, $R(T,H)=(k-1)(n-1)+\sigma(H)$.

Theorem 1.1 is tight up to the value of $C_{\Delta,k}$, as it is easy to see
that $R(G,H)\geq|H|$ for any non-empty graphs $G$ and $H$, so $G$ is not
$H$-good if $|G|<|H|/k$, and hence $C_{\Delta,k}=\Omega(1/k)$. However,
without much more difficulty, it can be seen that we must have
$C_{\Delta,k}\geq\Delta/100k\log\Delta$ for sufficiently large $\Delta$, by
taking $m$ to be sufficiently large, letting $H$ be the $k$-partite complete
graph with $m$ vertices in each class, and letting $T$ be any tree with
maximum degree $\Delta$ on $n=\Delta m/100\log\Delta$ vertices. To see this,
let $N=\Delta m/10\log\Delta$, and take a blue complete $\lfloor
k/3\rfloor$-partite graph with $N$ vertices in each class, and colour the
edges within each class red/blue so that the maximum red degree is at most
$\Delta-1$ and there is no blue copy of $K_{m,m}$. This colouring is possible
using the probabilistic method, more precisely, colouring edges of $K_{2N}$
red independently at random with probability $\Delta/4N$ and removing vertices
with at least $\Delta$ red neighbouring edges. Call the final red/blue
coloured graph $G$. If there is a blue copy of $H$ in $G$, then at least $3m$
vertices from this copy are within one class of $N$ vertices in the original
partition of $G$, and hence the colouring within this class must contain a
blue copy of $K_{m,m}$, a contradiction. As $G$ has maximum red degree at most
$\Delta-1$, it contains no red copy of $T$, and therefore $R(T,H)>\lfloor
k/3\rfloor N>kn$. Thus, $T$ is not $H$-good, so we must have
$C_{\Delta,k}\geq|T|/|H|\geq\Delta/100k\log\Delta$. We have not optimised the
value of $C_{\Delta,k}$ in Theorem 1.1 as our proof would give an upper bound
on $C_{\Delta,k}$ that is very far from this $\Delta/100k\log\Delta$ lower
bound.

##  2 Preliminaries

After covering the basic notation that we use, we will give a detailed sketch
of the proof of Theorem 2.1 in Section 2.2 before outlining the rest of the
paper in Section 2.3.

###  2.1 Notation

A graph $G$ has vertex set $V(G)$ and edge set $E(G)$, and we write
$|G|=|V(G)|$ and $e(G)=|E(G)|$. A vertex $v\in V(G)$ has neighbourhood $N(v)$
and degree $d(v)=|N(v)|$. Given a vertex set $S\subset V(G)$, the set of
neighbours of $S$ (including those in $S$) is $N^{\prime}(S)=\cup_{s\in
S}N(s)$ and its external neighbourhood is $N(S)=\cup_{s\in S}N(s)\setminus S$.
For a vertex $v\in V(G)$ and sets $U,S\subset V(G)$, we write
$d(v,U)=|N(v)\cap U|$ and $N(S,U)=N(S)\cap U$. Given a subset $S\subset V(G)$,
$G[S]$ is the subgraph of $G$ induced on $S$, with vertex set $S$ and every
edge of $G$ contained within $S$. We write $G-S$ for the graph
$G[V(G)\setminus S]$. For a subset $X\subset V(G)$, $I(X)$ denotes the
subgraph of $G$ with vertex set $X$ and no edges. The complement of $G$,
denoted $G^{c}$, is the graph with $V(G^{c})=V(G)$ and such that $xy$ forms an
edge in $G^{c}$ if and only if $xy$ is not an edge in $G$.

Given two subgraphs $H_{1},H_{2}\subset G$, $H_{1}\cup H_{2}$ is the subgraph
with vertex set $V(H_{1})\cup V(H_{2})$ and edge set $E(H_{1})\cup E(H_{2})$.
If $H\subset G$ is a subgraph and $e=xy\in E(G)$, then $H+e$ denotes the
subgraph with vertex set $V(H)\cup\\{x,y\\}$ and edge set $E(H)\cup\\{xy\\}$.
Given $x,y\in V(G)$, an $x,y$-path is a path with endvertices $x$ and $y$. A
path $P$ with $\ell$ vertices has length $\ell-1$. We use $H+P$ to denote
$H\cup P$, and $H-P$ to denote the graph resulting from removing the edges of
$P$ from $H$ and any internal vertex of $P$ which is now isolated. For subsets
$S_{1},S_{2}\subset V(G)$, an $S_{1},S_{2}$-path is a path with one endpoint
in $S_{1}$ and the other endpoint in $S_{2}$.

For a positive integer $n\in\mathbb{N}$, we write $[n]=\\{1,\ldots,n\\}$ and
$[n]_{0}=[n]\cup\\{0\\}$. We will use the standard hierarchy notation, that
is, for $a,b\in(0,1]$, we will write $a\ll b$ to mean that there exists a non-
decreasing function $f:(0,1]\to(0,1]$ such that if $a\leq f(b)$ then the rest
of the proof holds with $a$ and $b$. Hierarchies with more constants are
defined in a similar way and are to be read from the right to the left. For
simplicity we will ignore floor and ceiling signs whenever this does not
affect the argument.

###  2.2 Outline of the proof of Theorem 2.1

Let $H$ have chromatic number $k$ such that $|H|\leq\mu n$. Let $m=\sigma(H)$.
For convenience, if not elegance, sake, we will use $K^{k-1}_{\mu n}\times
K^{c}_{m}$ to denote the complete $k$-partite graph whose first $k-1$ classes
have size $\mu n$ and whose last class has size $m$. Thus, if a graph $G$
contains a copy of $K^{k-1}_{\mu n}\times K^{c}_{m}$, then it contains a copy
of $H$, so that, to prove Theorem 1.1 it is enough to prove the following
(where we also take $\mu_{\Delta,k}=1/C_{\Delta,k}$).

######  Theorem 2.1.

For all $\Delta$ and $k$, there exists a constant $\mu_{\Delta,k}$ such that
the following holds for each $m\leq\mu_{\Delta,k}n$. Every tree $T$ with $n$
vertices and maximum degree at most $\Delta$ satisfies
$R(T,K^{k-1}_{\mu_{\Delta,k}n}\times K_{m}^{c})=(k-1)(n-1)+m$.

We will prove Theorem 2.1 by induction on $k$, and therefore the proof falls
into two parts, the base case ($k=2$) and the inductive step. This follows the
work of Balla, Pokrovskiy, and Sudakov [2], who proved Theorem 2.1 under a
stronger assumption equivalent to replacing $\mu_{\Delta,k}n$ with
$\mu_{\Delta,k}n/\log^{4}n$ throughout. The critical case for making our
improvement is the case $k=2$, and we concentrate on this in this sketch,
before outlining briefly how the case for $k\geq 3$ follows by induction.

For the case $k=2$, it is sufficient to prove the following for some
$\mu=\mu(\Delta)$. That, for every $n$-vertex tree $T$ with maximum degree
$\Delta$ and all $m\leq\mu n$, the following holds.

  1. A

If $G$ has $n+m-1$ vertices, and the complement of $G$ is $K_{m,\mu n}$-free,
then $G$ contains a copy of $T$.

An $(n+m-1)$-vertex graph $G$ whose complement is $K_{m,\mu n}$-free satisfies
the natural expansion condition that, for each set $U$ of $m$ vertices,
$|N_{G}(U)|\geq|G|-|U|-\mu n\geq(1-2\mu)n$. Beginning with work by Friedman
and Pippenger [13], through a key development by Haxell [17], trees can be
embedded into graphs satisfying expansion conditions (see, for example,
Corollary 2.19). A typical such application of these methods would give the
following.

  1. B

If every set $U$ of $m$ vertices in a graph $G$ satisfies $|N(U)|\geq|G|-2\mu
n$, then a tree $T$ with maximum degree $\Delta$ can be embedded in $G$ if $G$
has at least $20\Delta\cdot\max\\{\mu n,m\\}$ more vertices than $T$.

Our trouble, then, is the gulf between A and B: we only have $m-1$ more
vertices in $G$ than $T$ in A, far from the $20\Delta\cdot\mu n$ spare
vertices required to use B, particularly as $m$ can be any value between 1 and
$\mu n$. Critically, we use the following observation for our graph $G$ whose
complement is $K_{m,\mu n}$-free. That, for some large constant $K$, if we
take a set $V\subset V(G)$ of $Km$ vertices at random, then, any set $U\subset
V(G)$ of $m$ vertices has at most $\mu n$ non-neighbours in $G$, so can expect
to have at most $2\mu Km$ non-neighbours in $V$. With a little care, then, we
can show, with high probability, that every set $U\subset V$ with $|U|=m$
satisfies $|N_{G[V]}(U)|\geq(1-3\mu)|V|$. Then, in $G[V]$, we can apply B to
embed a tree with maximum degree $\Delta$ using only
$O(\Delta\cdot\max\\{\mu|V|,m\\})=O(\Delta\cdot\max\\{\mu Km,m\\})$ spare
vertices. When we embed using $m-1$ spare vertices (as at A), this is still
not enough, but for small $m$ we are much closer, needing $O(m)$ spare
vertices instead of $O(n)$ spare vertices. With more analysis, and choosing
the constants involved carefully, we can show that, for some small $\lambda$,
$G[V]$ here is likely to be $K_{\lambda m,\lambda m}$-free, which will allow
us to use B to embed a tree with maximum degree $\Delta$ into $G[V]$ while
using only $m-1$ spare vertices.

This key idea for finishing the embedding leads to the following strategy. We
take a nested sequence of random subsets $V(G)=U_{0}\supset
U_{1}\supset\ldots\supset U_{\ell}$ with geometrically-decreasing size, before
embedding $T$ in $\ell$ stages, at each stage $i\in[\ell]$ using all unused
vertices in $U_{i-1}\setminus U_{i}$ and as few vertices in $U_{i}$ as
possible, until we finish by embedding the last part of $T$ within
$G[U_{\ell}]$. This approach is inspired by the ‘cover down methods’ in the
iterative absorption techniques used by the first author with Glock, Kühn, Lo,
and Osthus [15] (developing earlier work by Barber, Kühn, Lo, and Osthus [3]),
and similarly we also call our nested sequence of sets a _vortex_.

Between this sketch and our implementation, there are several complications.
We cannot take a simple vortex and must run a cleaning process on an initial
random vortex. The ‘vortex’ embedding method also requires $m$ to be at least
some large constant; when it is not we must use a separate (though much
easier) embedding. Finally, before doing anything, we need to efficiently gain
an expansion property for small sets (i.e., those with fewer than $m$
vertices). As in previous work (in particular, [2]), we can remove a small set
of vertices (effectively some small maximal set which does not expand) to gain
this property, but removing these vertices gives us fewer ‘spare vertices’ to
work with than the $m-1$ we need. If we end up with ${m}^{\prime}-1$ spare
vertices, then it will not be hard to show that sets with size ${m}^{\prime}$
expand significantly, but this change in the value of $m$ needs to be dealt
with carefully, which we do in Section 2.4.

Finally, we note that, while some of the tree embeddings we use are quite
intricate, there exist very good methods to carry them out in a flexible
fashion using expansion properties. More specifically, we use an
‘extendability’ method for embedding trees that combines the inductive
embedding of trees in expanding graphs by Haxell [17] (developing work by
Friedman and Pippenger [13]) with a ‘roll-back’ idea by Johannsen (see [10]),
as used by Glebov, Johannsen, and Krivelevich [14], and Draganic, Krivelevich,
and Nenadov [10]. For embedding part of the tree into our vortex while making
sure we cover all of the unused vertices (as discussed above) we use results
of the first author from [21], which we develop into the form we require in
Section 4.

Case $k\geq 3$. Having proved the $k=2$ case, we will then proceed by
induction on $k$. To prove Theorem 2.1 for $k$, we will have a graph $G$ with
$(k-1)(n-1)+m$ vertices and an $n$-vertex tree $T$ with maximum degree
$\Delta$, and $m\leq\mu n$ for some small $\mu>0$, and look to show that
either $G$ contains a copy of $T$ or $G^{c}$ contains a copy of $K^{k-1}_{\mu
n}\times K^{c}_{m}$. We proceed differently according to three cases, a)–c),
the proof of which are carried out in Sections 6.1–6.3 where a more detailed
proof sketch for each case can be found.

a) In this case, $T$ has linearly (in $n$) many leaves, and we follow a method
of Balla, Pokrovskiy, and Sudakov [2].

b) In this case, $G$ is not well connected in the sense that there is a small
set $V_{0}$ such that $G-V_{0}$ has two large disjoint parts. We can assume
(using induction) that the subgraphs of $G$ induced on these large parts both
satisfy an expansion condition. If there is a vertex with $\Delta$ neighbours
in each part then we can embed part of the tree $T$ in each part, connected
together appropriately by this vertex. Where there is no such vertex, we
partition $V(G)$ into two large sets which have few edges between them in $G$.
If $G$ has no copy of $T$, then we can apply induction to both subgraphs
induced by the sets of this partition to find complete partite graphs in their
complement, which we combine before removing some vertices in the larger
classes in order to find our desired complete partite graph in $G^{c}$.

c) In the final case, $G$ is well-connected and $T$ has few leaves. The
embedding we use here is the most complicated one in the inductive step.
Effectively, though, we use expansion conditions to embed $T$ with many bare
paths (i.e., paths which no branching vertices in $T$) removed, which exist as
$T$ has few leaves, before using a results on the Ramsey goodness of paths to
find paths that we then connect into the embedding of $T$ using the
connectivity property. This sketch serves more to motivate our eventual
embedding, which cannot follow this sketch closely, but will be discussed in
full in Section 6.3.

###  2.3 Organisation of the paper

In the rest of this section, we will first show, in Section 2.4 that the case
$k=2$ of Theorem 2.1 can be divided into 2 subcases, covered by Theorem 2.4
and Theorem 2.5, where the latter represents the critical case sketched in
Section 2.2. We then find our tree decompositions (Section 2.5), give some
basic results involving expansion properties (Section 2.6), and cover the tree
embedding tools we will use (in Section 2.7). In Section 3, we prove Theorem
2.4. In Section 4, we show how to embed trees while covering a vertex set, to
be applied at each stage when embedding the tree in the critical case. This
then allows us to prove the result in this critical case, Theorem 2.5, in
Section 5. Finally, in Section 6, we use induction on $k$ to prove Theorem 2.1
from the $k=2$ case.

###  2.4 Subcases when $k=2$

As discussed in Section 2.2, the case when $k=2$ in Theorem 2.1 is equivalent
to the following result, which for convenience we state separately.

######  Theorem 2.2.

Let $\mu\ll 1/\Delta$ and $1\leq m\leq\mu n$, and let $T$ be an $n$-vertex
tree with $\Delta(T)\leq\Delta$. Then, $R(T,K_{m,\mu n})=n+m-1$.

We will separate Theorem 2.2 into two subcases, but first need the following
definition for the main forms of expansion used throughout this paper.

######  Definition 2.3.

Let $m,m^{\prime}\in\mathbb{N}$, $d>0$ and let $G$ be a graph.

  1. i)

We say that $G$ is a $(d,m)$-expander if $|N(U)|\geq d|U|$ for all subsets
$U\subset V(G)$ with $|U|\leq m$.

  2. ii)

We say that $G$ is $(m,m^{\prime})$-joined if every pair of disjoint sets $A$
and $B$, with $|A|=m$ and $|B|=m^{\prime}$, has an edge between them in $G$.
When $m=m^{\prime}$, we simply say the graph is $m$-joined.

Note that a graph is $(m,m^{\prime})$-joined exactly when its complement is
$K_{m,m^{\prime}}$-free. Using these definitions, we can now state two
results, Theorems 2.4 and 2.5, before proving that Theorem 2.2 follows from
them using an additional result, Proposition 2.6. Theorem 2.4 covers Theorem
2.2 when $m$ is at most some constant depending on $\mu$, while Theorem 2.5,
roughly speaking, will cover Theorem 2.2 when $m$ is larger and some stronger
expansion condition holds. For convenience in their proofs, we adjust the
parameters so that they are applied to trees with $n-m+1$ vertices in an
$n$-vertex graph (instead of $n$ and $n+m-1$, respectively).

######  Theorem 2.4.

Let $\mu\ll 1/\Delta,1/m$ with $m\leq\mu n$, and let $G$ be an $n$-vertex
$(m,\mu n)$-joined graph.

Then, $G$ contains a copy of every $(n-m+1)$-vertex tree $T$ with
$\Delta(T)\leq\Delta$.

######  Theorem 2.5.

Let $1/D,1/m,\mu\ll 1/\Delta$ and $m\leq\mu n$, and let $G$ be an $n$-vertex
$(m,\mu n)$-joined graph which is a $(D,m)$-expander.

Then, $G$ contains a copy of every $(n-m+1)$-vertex tree $T$ with
$\Delta(T)\leq\Delta$.

Before showing these two results imply Theorem 2.2, we need to find an
expander in the sense of Definition 2.3i) in our graphs covered by this
theorem, which we do in the following proposition.

######  Proposition 2.6.

Let $n_{0},m\in\mathbb{N}$ and $d>0$, and let $G$ be an $(m,n_{0})$-joined
graph with $|G|\geq n_{0}+(2d+2)m$. Then, there exists some $W\subset V(G)$
such that $|W|<m$ and, setting $m^{\prime}=m-|W|$, $G-W$ is an
$(m^{\prime},n_{0}+dm)$-joined $(d,m)$-expander.

###### Proof.

Let $W\subset V(G)$ be a maximal subset subject to $|W|<2m$ and
$|N_{G}(W)|\leq d|W|$, possible as $W=\emptyset$ satisfies these conditions.
Note that if $|W|\geq m$, then, as $G$ is $(m,n_{0})$-joined,
$|V(G)\setminus(W\cup N_{G}(W)|<n_{0}$, so that
$|N_{G}(W)|\geq|G|-|W|-n_{0}\geq 2dm>d|W|$, a contradiction. Thus, we have
$|W|<m$. Let $m^{\prime}=m-|W|\geq 1$.

Now, if $U\subset V(G)\setminus W$ with $|U|\leq m$ and $U\neq\emptyset$,
then, as $|W|<m$, we must have that $|U\cup W|<2m$ and $|U\cup W|>|W|$. To
avoid contradicting the choice of $W$, we must have $|N_{G}(U\cup W)|\geq
d|U\cup W|$, and hence $|N_{G-W}(U)|\geq d|U\cup W|-d|W|\geq d|U|$. Thus,
$G-W$ is an $(d,m)$-expander.

Furthermore, if $X,Y\subset V(G-W)$ are disjoint sets with $|X|=m^{\prime}$,
$|Y|=n_{0}+dm$, and $e_{G^{\prime}}(X,Y)=0$, then $e_{G}(X\cup W,Y\setminus
N_{G}(W))=0$, $|X\cup W|=m$ and $|Y\setminus N_{G}(W)|\geq n_{0}+dm-d|W|\geq
n_{0}$, which contradicts that $G$ is $(m,n_{0})$-joined. Thus, $G-W$ is
$(m^{\prime},n_{0}+dm)$-joined. ∎

We can now deduce Theorem 2.2 from Theorems 2.4 and 2.5 using Proposition 2.6,
as follows.

###### Proof of Theorem 2.2.

Let $\mu\ll 1/\Delta$ and $1\leq m\leq\mu n$, let $T$ be an $n$-vertex tree
with $\Delta(T)\leq\Delta$, and let $G$ be a graph on $n+m-1$ vertices such
that $G^{c}$ does not contain a copy of $K_{m,\mu n}$. To prove Theorem 2.2,
then, we need to show that $G$ contains a copy of $T$. Using that $\mu\ll
1/\Delta$, let $\bar{\mu}$ and $\bar{m}$ satisfy $\mu\ll\bar{\mu}\ll
1/\bar{m}\ll 1/\Delta$ and let $D=\bar{\mu}n/100m\geq\bar{\mu}/100\mu$ (as
$m\leq\mu n$), so that $1/D\ll 1/\Delta$.

We have $n\geq\bar{\mu}n/2+(2D+2)m$, and that $G$ is $(m,\bar{\mu}n/2)$-joined
as its complement is $K_{m,\mu n}$-free and $\mu\ll\bar{\mu}$. Thus, using
Proposition 2.6 and $Dm\leq\bar{\mu}n/2$, we can find a set $W\subset V(G)$
with $|W|<m$ such that, setting $m^{\prime}=m-|W|$ and $G^{\prime}=G-W$,
$G^{\prime}$ is an $(m^{\prime},\bar{\mu}n)$-joined $(D,m)$-expander. Note
that $|G^{\prime}|=n+m^{\prime}-1$ and $m^{\prime}\leq m\leq\mu
n\leq\bar{\mu}n$.

If we have $m^{\prime}<\bar{m}$, then, as $\bar{\mu}\ll 1/\bar{m},1/\Delta$
and $G^{\prime}$ is an $(m^{\prime},\bar{\mu}n)$-joined graph with
$n+m^{\prime}-1$ vertices, $G^{\prime}$ contains a copy of $T$ by Theorem 2.4.
If $m^{\prime}\geq\bar{m}$, then since $G^{\prime}$ is a $(D,m)$-expander and
$m^{\prime}\leq m$, it is also a $(D,m^{\prime})$-expander. Then, as
$1/\bar{m},1/D,\bar{\mu}\ll 1/\Delta$, $m^{\prime}\geq\bar{m}$, and
$G^{\prime}$ is $(m^{\prime},\bar{\mu}n)$-joined, $G^{\prime}$ contains a copy
of $T$ by Theorem 2.5, as required. ∎

###  2.5 Structural decompositions of trees

To show our cases cover all trees, we will need the following useful result
which states that, if a tree has few leaves, then it has many bare paths in
compensation.

######  Lemma 2.7 ([20, Lemma 2.1]).

Let $k,\ell,n\in\mathbb{N}$ and let $T$ be a tree with $n$ vertices and at
most $\ell$ leaves. Then $T$ contains at least $\frac{n}{k+1}-2\ell+2$ vertex
disjoint bare paths, each of length $k$.

We now give our main tree decomposition, decomposing the edges of a bounded
degree tree $T$ into subtrees $T_{1},\ldots,T_{\ell}$ such that $T_{i}$ and
$T_{i+1}$ intersect only on a leaf of $T_{i}$, as in the following definition.

######  Definition 2.8.

Let $\ell\in\mathbb{N}$ and let
$\mathbf{n}=(n_{1},\ldots,n_{\ell})\in\mathbb{N}^{\ell}$. An
$\mathbf{n}$-decomposition of a tree $T$ is a tuple $(T_{1},\ldots,T_{\ell})$
of edge-disjoint subtrees of $T$ such that

  1. i)

$E(T)=E(T_{1})\cup\ldots\cup E(T_{\ell})$,

  2. ii)

$|T_{1}|=n_{1}$, and $|T_{i}|=n_{i}+1$ for each $2\leq i\leq\ell$, and

  3. iii)

for each $i\in[\ell-1]$, $T_{i}$ contains no vertices in
$T_{i+2}\cup\ldots\cup T_{\ell}$, and $V(T_{i})\cap V(T_{i+1})$ contains
exactly one vertex, which is a leaf of $T_{i}$.

We want to find such a decomposition where the trees $T_{1},\ldots,T_{\ell}$
decrease in size by approximately a constant factor each time. That is, an
$\mathbf{n}$-decomposition where $\mathbf{n}$ is _$(\gamma_{1},\gamma_{2})$
-descending_, as follows.

######  Definition 2.9.

For $0<\gamma_{1}<\gamma_{2}<1$, we say that a tuple
$\mathbf{n}=(n_{1},\ldots,n_{\ell})\in\mathbb{N}^{\ell}$ is
_$(\gamma_{1},\gamma_{2})$ -descending_ if $\gamma_{1}n_{i}\leq
n_{i+1}\leq\gamma_{2}n_{i}$ for every $i\in[\ell-1]$.

We will find descending decompositions of trees, by iteratively using the
following proposition.

######  Proposition 2.10.

Let $\gamma\in(0,1)$ and $n,\Delta\in\mathbb{N}$ satisfy $\gamma n\geq\Delta$
and $n\geq 2$. Let $T$ be a tree with $n$ vertices and $\Delta(T)\leq\Delta$,
and let $t\in V(T)$. Then, there exists two subtrees $T_{1},T_{2}\subseteq T$
such that

  1. i)

$E(T)=E(T_{1})\cup E(T_{2})$,

  2. ii)

$T_{1}$ and $T_{2}$ share exactly one vertex $v$, which is a leaf of $T_{1}$,

  3. iii)

$t\in V(T)\setminus V(T_{2})$, and

  4. iv)

$\gamma n\geq|T_{2}|\geq\gamma n/2\Delta$.

###### Proof.

View $T$ as being rooted at $t$. Let $v$ be a vertex furthest from $t$ subject
to the condition that the subtree $T_{2}$ of $T$ rooted at $v$ has size
$|T_{2}|\geq\gamma n/2\Delta$. Note that this is possible as $t$ has at most
$\Delta(T)\leq\Delta$ neighbours, the subtree rooted at one of these must have
size at least $(n-1)/\Delta\geq n/2\Delta$ and hence is a candidate for $v$ as
$\gamma<1$. Moreover, this shows $v\not=t$. Let $T_{1}$ be subgraph of $T$
induced by the vertex set $(V(T)\setminus V(T_{2}))\cup\\{v\\}$. Note that
$T_{1}$ is a subtree of $T$ and $v$ is leaf in $T_{1}$. It follows that
$T_{1},T_{2}$ satisfies conditions i), ii) and iii). For condition iv), let
$v^{\prime}$ be any neighbour of $v$ in $T_{2}$. To avoid contradicting the
definition of $v$, the subtree rooted at $v^{\prime}$ must have size at most
$\left\lfloor\gamma n/2\Delta\right\rfloor$. Since there are at most $\Delta$
such $v^{\prime}$, we have $|T_{2}|\leq 1+\Delta\cdot\left\lfloor\gamma
n/2\Delta\right\rfloor\leq\gamma n$, as required. ∎

We can now find our desired descending decompositions of large bounded degree
trees, as follows.

######  Lemma 2.11.

Let $0<\gamma<1/2$ and let $n,N,\Delta\in\mathbb{N}$ satisfy
$n-1>N\geq\Delta/\gamma$. Then for any $n$-vertex tree $T$ with maximum degree
at most $\Delta$ and any $t\in V(T)$, there exists a
$(\frac{\gamma}{4\Delta},2\gamma)$-descending tuple
$\mathbf{n}=(n_{1},\ldots,n_{\ell})\in\mathbb{N}^{\ell}$ with
$\frac{\gamma}{3\Delta}N\leq n_{\ell}\leq N$ such that $T$ has an
$\mathbf{n}$-decomposition $(T_{1},\ldots,T_{\ell})$ with $t\in V(T_{1})$.

###### Proof.

We construct the desired decomposition iteratively, beginning with
$T_{1}^{\prime}=T$, and after $i$ iterations obtain a sequence of trees
$(T_{1},T_{2},\ldots,T_{i-1},T_{i}^{\prime})$ forming a
$(|T_{1}|,|T_{2}|-1,\ldots,|T_{i-1}|-1,|T_{i}^{\prime}|-1)$-decomposition of
$T$. For each $i\geq 1$, if $|T_{i}^{\prime}|-1\leq N$, then stop iterating.
Otherwise, let $t_{i}$ be the unique common vertex of $T_{i}^{\prime}$ and
$T_{i-1}$ if $i\geq 2$ and let $t_{1}=t$. Noting that
$|T_{i}^{\prime}|>N\geq\Delta/\gamma$, we can apply Proposition 2.10 to obtain
subtrees $T_{i}$ and $T^{\prime}_{i+1}$ of $T_{i}^{\prime}$ such that
$E(T_{i}^{\prime})=E(T_{i})\cup E(T^{\prime}_{i+1})$, $T_{i}$ and
$T_{i+1}^{\prime}$ share a unique vertex $t_{i+1}$ which is a leaf of $T_{i}$,
$t_{i}\in V(T_{i})\setminus V(T^{\prime}_{i+1})$, and
$\gamma|T_{i}^{\prime}|\geq|T^{\prime}_{i+1}|\geq\gamma|T_{i}^{\prime}|/2\Delta$.
This implies that $(T_{1},T_{2},\ldots,T_{i},T_{i+1}^{\prime})$ is a
$(|T_{1}|,|T_{2}|-1,\ldots,|T_{i}|-1,|T_{i+1}^{\prime}|-1)$-decomposition of
$T$.

As $\gamma<1$, this process must end; suppose it ends with a sequence
$(T_{1},\ldots,T_{\ell-1},T_{\ell}^{\prime})$. Let $n_{1}=|T_{1}|$,
$n_{i}=|T_{i}|-1$ for each $2\leq i\leq\ell-1$,
$n_{\ell}=|T^{\prime}_{\ell}|-1$, and $\mathbf{n}=(n_{1},\ldots,n_{\ell})$, so
that $(T_{1},\ldots,T_{\ell-1},T_{\ell}^{\prime})$ is an
$\mathbf{n}$-decomposition of $T$. Noting that $\ell\geq 2$ as
$|T_{1}^{\prime}|=n>N+1$, and since the process stopped after $\ell$ and not
$\ell-1$ iterations, we have $n_{\ell}\leq N$ and $|T_{\ell-1}^{\prime}|>N$,
the latter of which implies
$n_{\ell}\geq\gamma|T_{\ell-1}^{\prime}|/2\Delta-1>\gamma N/3\Delta$. It is
left then only to show that $\mathbf{n}$ is
$(\frac{\gamma}{4\Delta},2\gamma)$-descending.

For each $i\in[\ell-1]$, we have
$|T_{i+1}^{\prime}|\leq\gamma|T_{i}^{\prime}|$, so that
$|T_{i}^{\prime}|\geq|T_{i}|=1+|T_{i}^{\prime}|-|T_{i+1}^{\prime}|\geq
1+(1-\gamma)|T_{i}^{\prime}|$. Thus, for every $i\in[\ell]$, we have
$(1-\gamma)|T_{i}^{\prime}|\leq n_{i}\leq|T_{i}^{\prime}|$. Then, for each
$i\in[\ell-1]$, we have
$n_{i+1}\leq|T_{i+1}^{\prime}|\leq\gamma|T_{i}^{\prime}|\leq\gamma
n_{i}/(1-\gamma)\leq 2\gamma n_{i}$. Furthermore, for each $i\in[\ell-1]$, we
have
$n_{i+1}\geq(1-\gamma)|T_{i+1}^{\prime}|\geq(1-\gamma)\gamma|T_{i}^{\prime}|/2\Delta\geq(1-\gamma)\gamma
n_{i}/2\Delta\geq\gamma n_{i}/4\Delta$. Thus, $\mathbf{n}$ is
$(\frac{\gamma}{4\Delta},2\gamma)$-descending, as required. ∎

We will use Lemma 2.11 directly, as well as through the following corollary.

######  Corollary 2.12.

Let $0<\gamma<1/4$ and let $n,k,\Delta\in\mathbb{N}$ satisfy
$n>(8\Delta/\gamma)^{k+1}$. Then for any $n$-vertex tree $T$ with maximum
degree at most $\Delta$ and any $t\in V(T)$, there exists a
$(\frac{\gamma}{8\Delta},2\gamma)$-descending tuple
$\mathbf{n}=(n_{1},\ldots,n_{k})\in\mathbb{N}^{k}$ such that $T$ has an
$\mathbf{n}$-decomposition $(T_{1},\ldots,T_{k})$ with $t\in V(T_{1})$.

###### Proof.

Let $N=\frac{1}{2}(\frac{\gamma}{8\Delta})^{k}n$ and note that
$N>\Delta/\gamma$. Then, by Lemma 2.11, there is a
$(\frac{\gamma}{8\Delta},\gamma)$-descending tuple
$\mathbf{n}^{\prime}=(n^{\prime}_{1},\ldots,n^{\prime}_{\ell})\in\mathbb{N}^{\ell}$
with $\frac{\gamma}{4\Delta}N\leq n_{\ell}\leq N$ such that $T$ has an
$\mathbf{n}$-decomposition $(T_{1}^{\prime},\ldots,T_{\ell}^{\prime})$. Now,
as
$N\geq|T_{\ell}^{\prime}|-1\geq(\gamma/8\Delta)^{\ell}|T_{1}^{\prime}|\geq(\gamma/8\Delta)^{\ell}n/2$,
we have that $\ell\geq k$. Let $T_{i}=T_{i}^{\prime}$ for each $i\in[k-1]$ and
$T_{k}=\bigcup_{i=k}^{\ell}T_{i}^{\prime}$. Let $n_{i}=n^{\prime}_{i}$ for
each $i\in[k-1]$, and $n_{k}=\sum_{i=k}^{\ell}n_{i}^{\prime}-(\ell-k)$, and
let $\mathbf{n}=(n_{1},\ldots,n_{k})$. Note that $\mathbf{n}$ is
$(\frac{\gamma}{8\Delta},2\gamma)$-descending, and $(T_{1},\ldots,T_{k})$ is
an $\mathbf{n}$-decomposition of $T$. ∎

###  2.6 Another expansion property

We will use the following variant of Proposition 2.6, which is proved in a
similar manner.

######  Proposition 2.13.

Let $n_{0},m\in\mathbb{N}$ and $d>0$, and let $G$ be an $(m,n_{0})$-joined
graph which contains a set $V\subset V(G)$ with $|V|\geq n_{0}+(2d+2)m$. Then,
there exists some $W\subset V(G)$ such that $|W|<m$ and, for each $U\subset
V(G)\setminus W$ with $|U|\leq m$, $|N_{G}(U,V\setminus W)|\geq d|U|$.

###### Proof.

Let $W\subset V$ be a maximal subset subject to $|W|<2m$ and $|N_{G}(W,V)|\leq
d|W|$, possible as $W=\emptyset$ satisfies these conditions. Note that if
$|W|\geq m$, then, as $G$ is $(m,n_{0})$-joined, $|V\setminus(W\cup
N_{G}(W)|<n_{0}$, so that $|N_{G}(W,V)|\geq|V|-|W|-n_{0}\geq 2dm\geq d|W|$, a
contradiction. Thus, we have $|W|<m$.

Now, if $U\subset V(G)\setminus W$ satisfies $|U|\leq m$ and $U\neq\emptyset$,
then, as $|W|<m$, we have $|U\cup V|<2m$ and $|U\cup W|>|W|$. To avoid
contradicting the choice of $W$, we must have $|N_{G}(U\cup W,V)|\geq d|U\cup
W|$, and hence $|N_{G}(U,V\setminus W)|\geq d|U\cup W|-d|W|\geq d|U|$. Thus,
for each $U\subset V(G)$ with $|U|\leq m$, $|N_{G}(U,V\setminus W)|\geq d|U|$.
∎

###  2.7 Tree embeddings and $(d,m)$-extendability

As noted in Section 2.2, to carry out our tree embedding schemes we use
techniques that come from combining a development by Haxell [17] of a tree
embedding method of Friedman and Pippenger [13] with a ‘roll-back’ idea of
Johannsen (see [10]) as used by Draganic, Krivelevich and Nenadov [10]. We use
the language of extendability (first used by Glebov, Johannsen, and
Krivelevich [14]): in a graph with certain expansion conditions we embed a
tree iteratively, each time adding a leaf so that the embedded subgraph
maintains an ‘extendability condition’. Key to the flexibility of this method
is that removing a leaf (‘rolling-back’) maintains the extendability
condition.

The key definition here is that of a $(d,m)$-extendable subgraph $S$ in a
graph $G$, which is a subgraph with the property that every small subset of
$V(G)$ has many neighbours outside $S$. Note that the following definition
uses the set $N^{\prime}_{G}(U)=\cup_{v\in U}N_{G}(v)$.

######  Definition 2.14.

Let $d,m\in\mathbb{N}$ be such that $d\geq 3$ and $m\geq 1$. Let $G$ be a
graph and let $S\subset G$ be a subgraph. We say that $S$ is _$(d,m)$
-extendable in $G$_ if $S$ has maximum degree at most $d$ and, for all
$U\subset V(G)$ with $1\leq|U|\leq 2m$, we have

$|N_{G}^{\prime}(U)\setminus V(S)|\geq(d-1)|U|-\sum_{u\in U\cap
V(S)}(d_{S}(u)-1).$ (2.1)

The next lemma shows how to verify the extendability condition using only the
external neighbourhood.

######  Proposition 2.15.

Let $d,m\in\mathbb{N}$ be such that $d\geq 3$ and $m\geq 1$. Let $G$ be a
graph and let $S\subset G$ be a subgraph with maximum degree at most $d$. If,
for all $U\subset V(G)$ with $1\leq|U|\leq 2m$ we have $|N(U,V(G)\setminus
V(S))|\geq d|U|$, then $S$ is $(d,m)$-extendable.

###### Proof.

For each $U\subset V(G)$ with $1\leq|U|\leq 2m$, we have

$|N^{\prime}(U)\setminus V(S)|\geq|N(U)\setminus V(S)|=|N(U,V(G)\setminus
V(S))|\geq d|U|\geq(d-1)|U|-\sum_{u\in U\cap V(S)}(d_{S}(u)-1),$

as required. ∎

The next three lemmas are the core of the extendability method, and can be
found as Lemmas 5.2.6, 5.2.7 and 5.2.8 in [14]. They will allow us to
manipulate an extendable graph by adding/removing a vertex or an edge while
remaining extendable. The latter two are simple to verify, while the first
follows the original inductive step in the argument by Haxell [17]. The first
lemma we state in our $(m,m^{\prime})$-joined language, and it follows from
Lemma 5.2.6 in [14] by observing that in such a graph $G$ any set $U$ of $m$
vertices satisfies $|N_{G}(U)|\geq|G|-m^{\prime}-|U|=|G|-m^{\prime}-m$.

######  Lemma 2.16 (Adding a leaf).

Let $d,m,m^{\prime}\in\mathbb{N}$ be such that $d\geq 3$ and $m,m^{\prime}\geq
1$, and let $G$ be an $(m,m^{\prime})$-joined graph. Let $S$ be a
$(d,m)$-extendable subgraph of $G$ such that
$|G|\geq|S|+(2d+2)m+m^{\prime}+1$. Then, for every $s\in V(S)$ with
$d_{S}(s)\leq d-1$, there exists $y\in N_{G}(s)\setminus V(S)$ such that
$S+sy$ is $(d,m)$-extendable.

######  Lemma 2.17 (Removing a leaf).

Let $d,m\in\mathbb{N}$ be such that $d\geq 3$ and $m\geq 1$, let $G$ be a
graph and let $S\subset G$ be a subgraph of $G$. Suppose that there exist
vertices $s\in V(S)$ and $y\in N_{G}(s)\setminus V(S)$ so that $S+sy$ is
$(d,m)$-extendable. Then, $S$ is $(d,m)$-extendable.

######  Lemma 2.18 (Adding an edge).

Let $d,m\in\mathbb{N}$ be such that $d\geq 3$ and $m\geq 1$. Let $G$ be a
graph and let $S$ be a $(d,m)$-extendable subgraph of $G$. If $s,t\in V(S)$
with $d_{S}(s),d_{S}(t)\leq d-1$ and $st\in E(G)$, then $S+st$ is
$(d,m)$-extendable in $G$.

We will use Lemma 2.16 through the follow corollary where a tree is built on
to an extendable subgraph by applying it iteratively (see also Corollary 3.7
in [21]).

######  Corollary 2.19.

Let $d,m,m^{\prime}\in\mathbb{N}$ be such that $d\geq 3$, and let $G$ be an
$(m,m^{\prime})$-joined graph. Let $T$ be a tree with $\Delta(T)\leq d/2$ and
let $R$ be a $(d,m)$-extendable subgraph of $G$ with maximum degree at most
$d/2$. If $|R|+|T|\leq|G|-(2d+2)m-m^{\prime}$, then for every vertex $t\in
V(T)$ and $v\in V(R)$, there is a copy $S$ of $T$ in
$G-(V(R)\setminus\\{v\\})$ in which $t$ is copied to $v$ and $S\cup R$ is a
$(d,m)$-extendable subgraph of $G$.

###  2.8 Concentration results

We will use the following standard version of Chernoff’s bound for binomial or
hypergeometric random variables (see, e.g., [18] for the standard definition
of such variables with parameters $n$ and $p$ and with parameters $N$, $n$ and
$m$, respectively).

######  Lemma 2.20 (see, e.g., Corollary 2.3 and Theorem 2.10 in [18]).

Let $X$ be a hypergeometric random variable with parameters $N$, $n$ and $m$,
or a binomial random variable with parameters $n$ and $p$. Then, for any
$0<\varepsilon\leq 3/2$,

$\mathbb{P}(|X-\mathbb{E}X|\geq\varepsilon\mathbb{E}X)\leq
2\exp\left(-\frac{\varepsilon^{2}}{3}\mathbb{E}X\right).$

A sequence of random variables $(X_{i})_{i\geq 0}$ is a submartingale if
$\mathbb{E}[X_{i+1}\mid X_{0},\ldots,X_{i}]\geq X_{i}$ for each $i\geq 0$. We
will use the following Azuma-type bound for submartingales.

######  Lemma 2.21 (see, e.g., [26]).

Let $(X_{i})_{i\geq 0}$ be a submartingale and let $c_{i}>0$ for each $i\geq
1$. If $|X_{i}-X_{i-1}|<c_{i}$ for each $i\geq 1$, then, for each $n\geq 1$,

$\mathbb{P}(X_{n}-X_{0}\leq t)\leq
2\exp\left(-\frac{t^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right).$

##  3 Proof of Theorem 2.4

We now prove Theorem 2.4, which covers Theorem 2.2 when $m$ is at most some
large constant depending on $\Delta$. As our $n$-vertex graph $G$ here is
$(m,\mu n)$-joined (for some small $\mu$), sets with constant size (i.e., $m$)
already have a neighbourhood covering almost all of the graph, making the
graph very dense, with $\Theta(n^{2}/m)$ edges. Embedding a tree is not so
difficult in this case, and, for example, we could use an approach of Balla,
Pokrovskiy, and Sudakov [2] if $T$ has linearly many leaves and an absorption
approach like that in [21] if $T$ does not have linearly many leaves. To take
a unified approach, however, we will use an embedding inspired by work by the
first author and Kathapurkar [19] and the first author and Böttcher, Parczyk,
and Person [4].

To do this we first embed a small linear portion of the tree randomly, before
extending this greedily vertex by vertex. Where a new leaf cannot be embedded
because some embedded vertex, $w$ say, has no more unused neighbours, we show
that a vertex in the set $U$ of (at least $m$) unused vertices can be swapped
into the embedding to free up a neighbour of $w$, allowing the embedding to
continue. This swapping property will follow from the random embedding of the
first part of the tree, as the $(m,\mu n)$-joined property of $G$ implies that
for some $u\in U$, many _good_ neighbours of $w$ have a large common
neighbourhood with $u$, so that, for many of these good neighbours,
$w^{\prime}$ say, $w^{\prime}$ will have a vertex of $T$ embedded to it with
all of its neighbours in the embedding in $T$ embedded to common neighbours of
$u$ and $w^{\prime}$ (see Claim 3.1) – exactly what we need to swap
$w^{\prime}$ with $u$, and then use $ww^{\prime}$ to extend the embedding.

###### Proof of Theorem 2.4.

To recap our situation, we have $\mu\ll 1/\Delta,1/m$ with $m\leq\mu n$, an
$n$-vertex $(m,\mu n)$-joined graph $G$, and an $(n-m+1)$-vertex tree $T$ with
$\Delta(T)\leq\Delta$ to embed into $G$. Note that, moreover, we can assume
that $1/n\ll\mu$, as we could take some $\mu^{\prime}$ with
$\mu\ll\mu^{\prime}\ll 1/\Delta,1/m$ and prove this with $\mu^{\prime}$ in
place of $\mu$ first, where $m\leq\mu n$ implies that $1/n\leq\mu$ and thus
$1/n\ll\mu^{\prime}$.

Let $\gamma$ and $\beta$ satisfy $\mu\ll\gamma\ll\beta\ll 1/\Delta,1/m$.
Applying Proposition 2.10 with an arbitrary $t\in V(T)$, we find subtrees
$T_{0}$ and $T_{1}$ of $T$ sharing exactly one vertex $t_{1}$, such that
$E(T)=E(T_{1})\cup E(T_{2})$ and $4\beta n\leq|T_{0}|\leq 8\Delta\beta n$.
Label the remaining vertices in $T$ as $t_{2},\ldots,t_{n-m+1}$ such that
$T[\\{t_{1},\ldots,t_{i}\\}]$ is a tree for each $i\in[n-m+1]$, and
$T[t_{1},\ldots,t_{|T_{0}|}]=T_{0}$. Moreover, do this so that, for a set
$J\subset\\{4,\ldots,|T_{0}|\\}$ with $|J|=\gamma n$, for each $j\in J$,
$t_{j-3}t_{j-2}t_{j-1}t_{j}$ is a path in $T$ and the neighbours of $t_{j}$ in
$T$ except for $t_{j-1}$ (if there are any) appear in the labelling directly
after $t_{j}$, and the vertices $t_{j}$, $j\in J$ are all at distance at least
3 apart in $T$ (that this is possible follows easily as $\Delta(T)\leq\Delta$
and $\gamma\ll\beta$).

Now, if $V(G)$ contains a set $U$ of $m$ vertices with degree at most $n/2m$,
then $|N_{G}(U)|\leq m\cdot n/2m=n/2<n-\mu n-m$, and hence $G$ is not $(m,\mu
n)$-joined, a contradiction. Therefore, setting $V_{0}$ to be the set of
vertices in $V(G)$ with degree at least $n/2m$, we have $|V(G)\setminus
V_{0}|<m$.

We now randomly embed $T_{0}$ into $G[V_{0}]$ vertex by vertex, as follows,
creating an embedding $\phi$. Arbitrarily, choose $v_{1}\in V_{0}$ and set
$\phi(t_{1})=v_{1}$. Then, for each $2\leq i\leq|T_{0}|$ in turn, let $w_{i}$
be the image under $\phi$ of the sole neighbour of $t_{i}$ in
$T[\\{t_{1},\ldots,t_{i}\\}]$, choose $v_{i}\in
N_{G}(w_{i},V_{0})\setminus\\{v_{1},\ldots,v_{i-1}\\}$ uniformly at random and
set $\phi(t_{i})=v_{i}$. Note that, for each $2\leq i\leq|T_{0}|$, we have
that $w_{i}\in V_{0}$, and therefore

$|N_{G}(w_{i},V_{0})\setminus\\{v_{1},\ldots,v_{i-1}\\}|\geq\frac{n}{2m}-m-|T_{0}|\geq\frac{n}{2m}-m-8\Delta\beta
n\geq\frac{n}{4m},$

so that this embedding successfully embeds $T_{0}$. We will show the following
claim.

######  Claim 3.1.

For each $U\subset V(G)$ with $|U|=m$ and $v\in V_{0}\setminus U$, with
probability $1-o(n^{-m-1})$, there are at least $4\mu n$ values of $j\in J$
such that $v_{j}v\in E(G)$ and $N_{\phi(T_{0})}(v_{j})\subset N_{G}(u)$ for
some $u\in U$.

###### Proof.

Fix $U\subset V(G)$ with $|U|=m$ and $v\in V_{0}\setminus U$. Now, for each
$y\in V_{0}\setminus U$, as $|N_{G}(y)|\geq n/2m$ and $G$ is $(m,\mu
n)$-joined, we have

$|N_{G}(U)\cap N_{G}(y)\cap V_{0})|\geq\frac{n}{2m}-m-\mu
n-m\geq\frac{n}{4m}.$

Thus, there is some $u\in U$ with $|N_{G}(u)\cap N_{G}(y)\cap V_{0}|\geq
n/4m^{2}$. As this holds for every $y\in V_{0}\setminus U$ and
$|N_{G}(v,V_{0})\setminus U|\geq n/2m-2m\geq n/4m$, there is some $u\in U$
such that, for at least $n/4m^{2}$ vertices $y\in N(v,V_{0})\setminus U$, we
have $|N_{G}(u)\cap N_{G}(y)\cap V_{0}|\geq n/4m^{2}$. Say the set of these
vertices $y$ is $Y_{v,u}$.

We now show that, with probability at least $1-o(n^{-(m+1)})$, for at least
$4\mu n$ values of $j\in J$, we have $v_{j}\in Y_{v,u}$ and
$N_{\phi(T_{0})}(v_{j})\subset N_{G}(u)$. Let $J=\\{j_{1},\ldots,j_{\gamma
n}\\}$, in order, and, for each $i\in[\gamma n]$, let $X_{i}$ be the indicator
function for $v_{j_{i}}\in Y_{v,u}$ and $N_{\phi(T_{0})}(v_{j_{i}})\subset
N_{G}(u)$.

Consider $i\in[\gamma n]$ and suppose we have embedded
$t_{1},\ldots,t_{j_{i}-3}$. As $v_{j_{i}-3}\in V_{0}$, for each $y\in
Y_{v,u}$, note that, as $|N_{G}(u)\cap N_{G}(y)\cap V_{0}|\geq n/4m^{2}$, all
but at most $m$ vertices in $N_{G}(v_{j_{i}-3})$ have at least $n/8m^{3}$
neighbours in $|N_{G}(u)\cap N_{G}(y)\cap V_{0}|$, for otherwise, as before,
we get that $G$ is not $(m,n/8m^{2})$-joined, a contradiction as
$n/8m^{2}\geq\mu n$. Therefore, the probability that $v_{j_{i}-1}\in
N_{G}(u)\cap N_{G}(y)\cap V_{0}$, $v_{j_{i}}=y$ and any subsequent neighbours
of $t_{j_{i}}$ are embedded into $N_{G}(u)\cap N_{G}(y)\cap V_{0}$ is at least

$\frac{|N_{G}(v_{j_{i}-3},V_{0})\setminus\\{v_{1},\ldots,v_{j_{i}-3}\\}|-m}{|N_{G}(v_{j_{i}-3},V_{0})\setminus\\{v_{1},\ldots,v_{j_{i}-3}\\}|}\cdot\frac{n/8m^{3}}{n}\cdot\frac{1}{n}\cdot\left(\frac{n/4m^{2}-|T_{0}|}{n}\right)^{\Delta}\geq\frac{1}{n(8m)^{2\Delta+3}}.$

As these events are distinct for each $y\in Y_{v,u}$, we have that,
conditioned on any possible values of $v_{1},\ldots,v_{j_{i}-3}$,

$\mathbb{P}(X_{i}=1)\geq|Y_{v,u}|\cdot\frac{1}{n(8m)^{2\Delta+3}}\geq\frac{n}{4m^{2}}\cdot\frac{1}{n(8m)^{2\Delta+3}}\geq\frac{1}{(8m)^{2\Delta+5}}.$

Therefore, setting $\alpha=\frac{1}{(8m)^{2\Delta+5}}$ so that $\alpha\gg\mu$,
and letting $Z_{i}=\sum_{i^{\prime}=1}^{i}(X_{i^{\prime}}-\alpha)$ for each
$i\in[\gamma n]$, we have that $(Z_{0},Z_{1},\ldots,Z_{\gamma n})$ is a
submartingale, using that, for all $1\leq i<i^{\prime}\leq\gamma n$,
$t_{j_{i}}$ and $t_{j_{i^{\prime}}}$ have distance at least 3 apart in $T$,
and $t_{j_{i}}$ and its neighbours appear in the sequence
$t_{1},\ldots,t_{|T_{0}|}$ before $t_{j_{i^{\prime}}}$ or any of its
neighbours. Furthermore, for each $i\in[\gamma n]$, we have
$|Z_{i}-Z_{i-1}|\leq 1$. Therefore, by Azuma’s inequality (Lemma 2.21), we
have

$\mathbb{P}\Big{(}\sum_{i\in[\gamma n]}(X_{i}-\alpha)\leq\alpha\gamma
n/2\Big{)}\leq 2\exp\Big{(}-\frac{(\alpha\gamma n/2)^{2}}{2\gamma
n}\Big{)}=2\exp(-\alpha^{2}\gamma n/8),$

so that $\sum_{i\in[\gamma n]}X_{i}\geq\alpha\gamma n/2\geq 4\mu n$ with
probability at least $1-2\exp(-\alpha^{2}\gamma n/8)=1-o(n^{-(m+1)})$, as
required, using $\alpha,\gamma\gg\mu\gg 1/n$. ∎

Therefore, by Claim 3.1 and a union bound, we can assume that $\phi$ has the
property that, for each $U\subset V(G)$ with $|U|=m$ and $v\in V_{0}\setminus
U$, there are at least $4\mu n$ values of $i\in J$ such that $v_{i}v\in E(G)$
and $N_{\phi(T_{0})}(v_{i})\subset N_{G}(u)$ for some $u\in U$. Next, we
greedily extend the embedding of $T_{0}$ to one of $T$, where if we cannot
simply extend the embedding by embedding $t_{i}$ we use the property from
Claim 3.1 to swap a single vertex in the embedding to allow this extension.
That is, we do the following.

Let $\phi_{|T_{0}|}=\phi$. Then, for each $i$ with $|T_{0}|<i\leq n-m+1$ in
turn, we will take $\phi_{i-1}$, an embedding of
$T[\\{t_{1},\ldots,t_{i-1}\\}]$ into $G[\\{v_{1},\ldots,v_{i-1}\\}]$, and find
$v_{i}\in V(G)\setminus\\{v_{1},\ldots,v_{i-1}\\}$ and an embedding $\phi_{i}$
of $T[\\{t_{1},\ldots,t_{i}\\}]$ into $G[\\{v_{1},\ldots,v_{i}\\}]$, as
follows. Let $w_{i}$ be the image under $\phi_{i-1}$ of the sole neighbour of
$t_{i}$ in $T[\\{t_{1},\ldots,t_{i}\\}]$ and,

  1. i)

if possible, choose $v_{i}\in
N_{G}(w_{i},V_{0}\setminus\\{v_{1},\ldots,v_{i-1}\\})$ and set
$\phi_{i}(t_{i})=v_{i}$ and $\phi_{i}(t_{j})=\phi_{i-1}(t_{j})$ for each
$j<i$,

  2. ii)

otherwise, if possible, pick $v_{i}\in
V(G)\setminus\\{v_{1},\ldots,v_{i-1}\\}$ and $j\in J$ such that
$\phi_{i-1}(t_{j})=v_{j}$, $w_{i}v_{j}\in E(G)$ and
$\phi_{i-1}(N_{T_{0}}(t_{j}))\subset N_{G}(v_{i})$, and set
$\phi_{i}(t_{i})=\phi_{i-1}(t_{j})$, $\phi_{i}(t_{j})=v_{i}$ and
$\phi_{i-1}(t_{j^{\prime}})=\phi_{i-1}(t_{j^{\prime}})$ for each
$j^{\prime}\in[i-1]\setminus\\{j\\}$ (noting that this does embed
$T[\\{t_{1},\ldots,t_{i}\\}]$ into $G[\\{v_{1},\ldots,v_{i}\\}]$ as
$N_{T_{0}}(t_{j})=N_{T}(t_{j})$), and,

  3. iii)

otherwise, stop the embedding.

Suppose the process first fails to embed $t_{\ell}$ for some
$|T_{0}|<\ell\leq|T|$, otherwise we have embedded all of $T$ in $G$ and are
done. We first show that step ii) has been carried out at most $3\mu n$ times.
Indeed, suppose otherwise, and let $I$ be the set of the _first_ $\mu n$
values of $i$ with $|T_{0}|<i<\ell$ for which $v_{i}$ was embedded using step
ii), so that $i<\ell-2\mu n$ for each $i\in I$. Now, for each $i$ with
$|T_{0}|<i<\ell$, $\phi_{i-1}$ and $\phi_{i}$ differ on at most one vertex in
$\\{t_{1},\ldots,t_{i-1}\\}$ which (if it exists) must be some vertex $t_{j}$
with $j\in J$ for which we still have $\phi_{i-1}(t_{j})=v_{j}$. Therefore, as
$w_{i}\in\\{v_{1}\\}\cup\phi_{i-1}(V(T)\setminus V(T_{0}))$, once a vertex has
been embedded to $w_{i}$ by some $\phi_{i^{\prime}}$, it is embedded to
$w_{i}$ by any subsequent embedding. Thus, as $\Delta(T)\leq\Delta$, there
must be at most $\Delta$ values of $i^{\prime}>|T_{0}|$ with
$w_{i^{\prime}}=w_{i}$. Therefore, letting $W=\\{w_{i}:i\in I\\}$, we have
$|W|\geq|I|/\Delta$. Let $V_{1}=V_{0}\setminus\\{v_{1},\ldots,v_{\ell-2\mu
n}\\}$, and note that there are no edges in $G$ between $W$ and $V_{1}$, for
otherwise there is an edge from $w_{i}$ to $V_{1}$ for some $i\in I$, which
contradicts that $t_{i}$ was not embedded by a step i). Thus, as $|V_{1}|\geq
2\mu n-m\geq\mu n$ and $|W|\geq\mu n/\Delta\geq m$ (using $m\ll 1/\mu\ll n$),
this contradicts that $G$ is $(m,\mu n)$-joined. Thus, we have that step ii)
has been carried out at most $3\mu n$ times.

Let then $J_{0}=\\{j\in J:\phi_{\ell-1}(v_{j})=\phi(v_{j})\\}$, so that
$|J\setminus J_{0}|\leq 3\mu n$. Now, we have
$w_{\ell}\in\\{v_{1}\\}\cup\phi_{\ell-1}(V(T)\setminus V(T_{0}))$, and from
the process above, we have that $\phi_{\ell-1}(t_{1})=v_{1}$ and, for each
$|T_{0}|<i<\ell$, $t_{i}$ is either embedded into $V_{0}$ at step i) or
embedded to some vertex $\phi_{i-1}(t_{j})=\phi(t_{j})$, which is also in
$V_{0}$. Thus, $w_{\ell}\in V_{0}$. Let $U_{\ell}\subset
V(G)\setminus\\{v_{1},\ldots,v_{\ell-1}\\}$ have size $m$, possible as
$|V(G)\setminus\\{v_{1},\ldots,v_{\ell-1}\\}|\geq n-(|T|-1)\geq m$. Then,
noting $w_{\ell}\in V_{0}\setminus U_{\ell}$ and using the property in Claim
3.1, there is some $j\in J_{0}$ and $v_{\ell}\in U_{\ell}$ with
$w_{\ell}v_{j}\in E(G)$ and $\phi(N_{T_{0}}(t_{j}))\subset N_{G}(v_{\ell})$.
As the vertices in $J$ have distance at least 3 apart in the tree, for each
$j^{\prime}$ with $t_{j^{\prime}}\in N_{T_{0}}(t_{j})$, we have
$j^{\prime}\notin J$, and therefore
$\phi_{\ell-1}(N_{T_{0}}(t_{j}))=\phi(N_{T_{0}}(t_{j}))\subset
N_{G}(v_{\ell})$. Note that $v_{\ell}$ and $j$ show that ii) can be carried
out to embed $t_{\ell}$, contradiction. Therefore, the process runs until all
the vertices of $T$ have been embedding, showing that $G$ contains a copy of
$T$. ∎

##  4 Embedding trees to cover vertex subsets

In this section, we prove the following key embedding result, which we use in
Section 5 to embed each piece of the tree into the vortex while covering a
prescribed set of vertices, represented in Lemma 4.1 by the set $X$.

######  Lemma 4.1.

Let $\Delta\geq 2$, $d\geq 20$, $m\in\mathbb{N}$ and $0<\gamma<1/10$ satisfy
$m\geq d^{8}$, $d\geq\Delta$ and $d\gg\Delta^{3}/\gamma$. Let $G$ be an
$m$-joined graph containing a vertex $v$. Let $T$ be a tree satisfying
$|T|\geq 2d^{2}m$ and $\Delta(T)\leq\Delta$, and let $t\in V(T)$. Suppose
$X\subset V(G)\setminus\\{v\\}$ contains at most $(1-\gamma)|T|$ vertices, and
$I(X\cup\\{v\\})$ is $(d,m)$-extendable in $G$. Let $t^{\prime}$ be a leaf of
$T$ which is not $t$, and suppose $|G|\geq|T|+20dm$.

Then, $G$ contains a copy of $T$ that covers $X$, in which $t$ is copied to
$v$, and $t^{\prime}$ is copied into $V(G)\setminus X$.

In order to prove this, we first show the following result, which embeds a
tree to cover most of a prescribed set of vertices.

######  Lemma 4.2.

Let $d,m,\Delta\in\mathbb{N}$ satisfy $d\geq 3$ and $d\geq\Delta$. Let $G$ be
an $m$-joined graph which contains a set $X\subset V(G)$ and a vertex $v\in
V(G)\setminus X$ such that $I(X\cup\\{v\\})$ is $(d,m)$-extendable in $G$. Let
$T$ be a tree with $\Delta(T)\leq\Delta$ and let $t\in V(T)$. Suppose that

$|T|\geq|X|+\Delta m+2\;\;\text{ and }\;\;|G|\geq|T|+(2d+4)m+1.$ (4.1)

Then, there is a copy $S$ of $T$ such that $t$ is copied to $v$, $S\cup I(X)$
is $(d,m)$-extendable in $G$, and $|X\setminus V(S)|<m$.

###### Proof.

Let $\ell=|T|$. Let $t_{1}=t$, and label the vertices of
$V(T)\setminus\\{t\\}$ as $t_{2},\ldots,t_{\ell}$ so that, for each
$i\in[\ell]$, $T_{i}=T[\\{t_{1},\ldots,t_{i}\\}]$ is a tree. For each $2\leq
i\leq\ell$, let $s_{i}$ be the unique neighbour of $t_{i}$ in
$T[\\{t_{1},\ldots,t_{i}\\}]$. Let $v_{1}=v$ and let $S_{1}$ be the graph
containing just the vertex $v_{1}$, so that $S_{1}$ is a copy of $T_{1}$ with
$t_{1}$ copied to $v_{1}$, and $S_{1}\cup I(X)$ is $(d,m)$-extendable in $G$.
Now, carry out the following process, where for each $j=2,\ldots,\ell$ in
turn, if possible we perform the following Step $\mathbf{C}_{j}$ to embed
$t_{j}$ and produce a copy $S_{j}$ of $T_{j}$ in which $t$ is copied to $v$
and $S_{j}\cup I(X)$ is $(d,m)$-extendable in $G$.

  * $\mathbf{C}_{j}$ $\bullet$

Let $u_{j}$ be the copy of $s_{j}$ in $S_{j-1}$. If there exists a vertex
$v_{j}\in X\setminus V(S_{j-1})$ so that $u_{j}v_{j}\in E(G)$, then let
$S_{j}=S_{j-1}+u_{j}v_{j}$ and note that $S_{j}$ is a copy of $T_{j}$ in $G$.
Moreover, $S_{j}\cup I(X)$ is $(d,m)$-extendable in $G$ by Lemma 2.18. In this
case, we say Step $\mathbf{C}_{j}$ is a good step.

  * $\mathbf{C}_{j}$ $\bullet$

Otherwise, if possible let $v_{j}$ be a neighbour of $u_{j}$ in
$V(G)\setminus(V(S_{j-1})\cup X)$ such that, setting
$S_{j}=S_{j-1}+u_{j}v_{j}$, $S_{j}\cup I(X)$ is $(d,m)$-extendable in $G$.
Note that $S_{j}$ is a copy of $T_{j}$ in $G$. In this case, we say Step
$\mathbf{C}_{j}$ is a neutral step.

We will show that we can successfully perform steps $\mathbf{C}_{j}$ for each
$2\leq j\leq\ell$, and that the resulting tree $S_{\ell}$ will satisfy
$|X\setminus V(S_{\ell})|<m$. Then, as $S_{\ell}$ is a copy of $T_{\ell}=T$
with $t_{1}=t$ copied to $v_{1}=v$, this completes the proof.

######  Claim 4.3.

For each $2\leq j\leq\ell$, if we have reached the start of step
$\mathbf{C}_{j}$ and $|X\setminus V(S_{j-1})|\geq m$, then fewer than $\Delta
m$ neutral steps have been taken so far.

###### Proof of Claim 4.3.

Suppose we have reached the start of step $\mathbf{C}_{j}$ and $|X\setminus
V(S_{j-1})|\geq m$. Let $J\subset[j-1]$ be the set of indices $i$ for which
the step $\mathbf{C}_{i}$ was a neutral step, noting that, for each $i\in J$,
$u_{i}$ has no neighbour in $G$ in $X\setminus V(S_{i-1})$, and hence no
neighbour in $X\setminus V(S_{j-1})$. Thus, as $G$ is $m$-joined, we have
$|\\{u_{i}:i\in J\\}|<m$. As $\Delta(T)\leq\Delta$, $|\\{u_{i}:i\in
J\\}|\geq|J|/\Delta$, so $|J|<\Delta m$, and thus before the start of step
$\mathbf{C}_{j}$ we took fewer than $\Delta m$ neutral steps. ∎

Suppose then, for contradiction, that the process reaches the start of Step
$\mathbf{C}_{j}$ for some $2\leq j\leq\ell$ and fails to take either a good or
neutral step. Note that the number of good steps that have been taken is
$|V(S_{j-1})\cap X|$ and the number of neutral steps that have been taken is
$|V(S_{j-1})\setminus X|-1$, which is at most $|S_{j-1}|-|X|+m-2$ if
$|X\setminus V(S_{j-1})|<m$. Therefore, by Claim 4.3, the number of neutral
steps is at most $\max\\{\Delta m,|S_{j-1}|-|X|+m-2\\}$, so that

$\displaystyle|S_{j-1}\cup I(X)|$ $\displaystyle=(|X|+1)+(|V(S_{j-1})\setminus
X|-1)\leq|X|+1+\max\\{\Delta m,|S_{j-1}|-|X|+m-2\\}$
$\displaystyle\leq\max\\{|X|+\Delta
m+1,|S_{j-1}|+m\\}\overset{\eqref{eqn:TGsize}}{\leq}|T|+m.$

Therefore, by (4.1), $|G|\geq|T|+(2d+4)m+1\geq|S_{j-1}\cup I(X)|+(2d+2)m+m+1$,
so that, by Lemma 2.16, there is some $v_{j}\in V(G)\setminus(V(S_{j-1})\cup
X)$ which is a neighbour of $u_{j}$ in $G$ and such that $S_{j-1}\cup
I(X)+u_{j}v_{j}$ is $(d,m)$-extendable in $G$, contradicting that we did not
take a good or neutral step at Step $\mathbf{C}_{j}$.

Therefore, the process has successfully taken Step $\mathbf{C}_{j}$ for each
$2\leq j\leq\ell$, and produced $S_{\ell}$, a copy of $T_{\ell}$ in $G$ with
$t_{1}=t$ copied to $v_{1}=v$. Finally, note that at the start of Step
$\mathbf{C}_{\ell}$ we will have taken at most $|X|$ good steps, and thus at
least $(\ell-2)-|X|=|T|-|X|-2\geq\Delta m$ neutral steps by (4.1). Therefore,
by Claim 4.3, $|X\setminus V(S_{\ell})|\leq|X\setminus V(S_{\ell-1})|<m$, and
thus $S_{\ell}$ is the required copy of $T$. ∎

Given a graph $G$ and a subset $Q\subset V(G)$, we say that $Q$ is
$k$-separated in $G$ if each pair of vertices in $Q$ is at distance at least
$k$ in $G$. We now need two results from [21], which we state in a slightly
simpler form that follow directly from [21, Corollary 3.16] and [21, Lemma
4.1], respectively.

######  Proposition 4.4.

Let $k\geq 0$ and $\Delta\geq 2$. Let $T$ be a tree with $\Delta(T)\leq\Delta$
and $|T|\geq 3\Delta^{k}$. Then, there is a subset $Q\subset V(T)$ which is
$(2k+2)$-separated in $T$ such that $|Q|\geq|T|/(8k+8)\Delta^{k}$.

######  Lemma 4.5.

Let $k,d,m\in\mathbb{N}$ with $d\geq 20$. Let $G$ be an $m$-joined graph and
let $R\subset G$ be a subgraph with $\Delta(R)\leq d/4$. Suppose $X\subset
V(G)\setminus V(R)$ is such that $R\cup I(X)$ is $(d,m)$-extendable in $G$.
Let $T$ be a tree with $\Delta(T)\leq d/4$ which has a set of $3|X|$ vertices
which is $(4k+4)$-separated in $T$. Let $t\in V(T)$ and $r\in V(R)$, and
suppose $|R|+|X|+|T|\leq|G|-10dm-2k$.

Then, there is a copy $S$ of $T$ in $G-V(R\setminus\\{r\\})$ so that $t$ is
copied to $r$, $R\cup I(X)\cup S$ is $(d,m)$-extendable in $G$ and
$|X\setminus V(S)|\leq 2m/(d-1)^{k}$.

We can now prove Lemma 4.1. The proof takes a tree decomposition using
Corollary 2.12, embed the first piece to cover most of $X$ using Lemma 4.5,
and then repeatedly uses Proposition 4.4 and Lemma 4.5 to embed the remaining
pieces while covering more and more of the uncovered vertices in $X$ until all
the vertices in $X$ are covered.

###### Proof of Lemma 4.1.

Let $\gamma_{2}=\gamma/10$, $\gamma_{1}=\gamma_{2}/16\Delta$ and
$T^{\prime}=T-t^{\prime}$. Let $\ell$ be the smallest integer such that
$2m/(d-1)^{\ell-1}<1$, so that $\ell\geq 9$ as $m\geq d^{8}$. By minimality,
we also have that $2m\geq(d-1)^{\ell-2}$, and thus, using
$d\gg\Delta^{3}/\gamma$, we have

$|T^{\prime}|\geq 2d^{2}m-1\geq
d^{2}(d-1)^{\ell-2}-1>(16\Delta/\gamma_{2})^{\ell+1}.$ (4.2)

Then, by Corollary 2.12, there is a $(\gamma_{1},\gamma_{2})$-descending tuple
$\mathbf{n}=(n_{1},\cdots,n_{\ell})\in\mathbb{N}^{\ell}$ such that
$T^{\prime}$ has an $\mathbf{n}$-decomposition $(T_{1},\ldots,T_{\ell})$ with
$t\in V(T_{1})$. Let $t_{0}=t$ and, for each $i\in[\ell-1]$, let $t_{i}$ be
the unique vertex shared by $T_{i}$ and $T_{i+1}$.

Note that $\sum_{i=2}^{\ell}n_{i}\leq 2\gamma_{2}n_{1}\leq 2\gamma_{2}|T|$, so

$|T_{1}|\geq(1-2\gamma_{2})|T|-1\geq(1-\gamma/2)|T|\geq|X|+\gamma|T|/2\geq|X|+\Delta
m+3.$

As $|G|\geq|T|+20dm$, we may apply Lemma 4.2 to find a copy $S_{1}$ of $T_{1}$
in $G$ in which $t$ is copied to $v$, $S_{1}\cup I(X)$ is $(d,m)$-extendable
in $G$ and $|X\setminus V(S_{1})|<m$. Next, for each $2\leq j\leq\ell$ in
turn, do the following.

  1. Dj

If possible, find a copy $S_{j}$ of $T_{j}$ in
$G-(\cup_{i\in[j-1]}V(S_{i})\setminus\\{v_{j-1}\\})$ such that $t_{j-1}$ is
copied to $v_{j-1}$, $(\cup_{i\in[j]}S_{i})\cup I(X)$ is $(d,m)$-extendable in
$G$, and $|X\setminus(\cup_{i\in[j]}S_{i})|<2m/(d-1)^{j-1}$.

Suppose that for some $2\leq j\leq\ell$ this was not possible. Note that the
set $X_{j}=X\setminus(\cup_{i\in[j-1]}S_{i})$ satisfies
$|X_{j}|<2m/(d-1)^{j-2}$, and
$|T_{j}|=n_{j}+1\geq\gamma_{1}^{j-1}n_{1}\geq\gamma_{1}^{j-1}|T|/2\geq\gamma_{1}^{j-1}d^{2}m$.
Hence, we may apply Proposition 4.4 to obtain a set $Q_{j}$ of vertices in
$T_{j}$ that is $(4j)$-separated, with

$|Q_{j}|\geq\frac{|T_{j}|}{16j\Delta^{2j-1}}\geq\frac{\gamma_{1}^{j-1}d^{2}m}{16j\Delta^{2j-1}}\geq\frac{6m}{(d-1)^{j-2}}\cdot\frac{\gamma_{1}^{j-1}(d-1)^{j}}{96j\Delta^{2j-1}}\geq\frac{6m}{(d-1)^{j-2}}\geq
3|X_{j}|,$

where the second last inequality follows from $d\gg\Delta^{3}/\gamma$.
Furthermore, we have

$|\cup_{i\in[j-1]}S_{i}|+|X_{j}|+|T_{j}|\leq|T|+|X_{j}|\leq|T|+2m\leq|G|-10dm-2(j-1),$

so we may apply Lemma 4.5 with $R=\cup_{i\in[j-1]}S_{i}$, $X=X_{j}$,
$T=T_{j}$, $r=v_{j-1}$ and $t=t_{j-1}$ to find a copy $S_{j}$ of $T_{j}$,
satisfying all the required conditions in Dj, which is a contradiction.

Therefore, we can complete Dj for each $2\leq j\leq\ell$. Taking
$S^{\prime}=\cup_{j\in[\ell]}S_{j}$, we have, then, a copy of $T^{\prime}$ in
which $t$ is copied to $v$ such that $I(X)\cup S^{\prime}$ is
$(d,m)$-extendable and $|X\setminus V(S^{\prime})|<2m/(d-1)^{\ell-1}<1$. In
other words, the copy $S^{\prime}$ of $T^{\prime}$ covers $X$. Let
$s^{\prime}$ be the vertex of $S^{\prime}$ which needs a leaf added to make
$S^{\prime}$ into a copy of $T$. As $|G|\geq|S^{\prime}|+(2d+2)m+m+1$, by
Lemma 2.16 there is some $v^{\prime}\in V(G)\setminus V(S^{\prime})\subset
V(G)\setminus X$ which is a neighbour of $s^{\prime}$. Let
$S=S^{\prime}+s^{\prime}v^{\prime}$, and note that this is a copy of $T$ which
covers $X$, in which $t$ is copied to $v$ and $t^{\prime}$ is copied into
$V(G)\setminus X$, as required. ∎

##  5 Proof of Theorem 2.5

In this section, we prove Theorem 2.5, where we embed a tree $T$ with $n-m+1$
vertices and $\Delta(T)\leq\Delta$ into an $n$-vertex $(m,\mu n)$-joined
$(D,m)$-expander graph $G$, where $m\leq\mu n$ and $\mu,1/D,1/m\ll 1/\Delta$.
We wish to do the following. First, we partition $T$ into trees
$T_{1}\cup\ldots\cup T_{\ell}$ with geometrically-decreasing size. We then use
the sizes of the trees in this partition to inform the sizes of a partition of
all but at most $m/4$ vertices of $G$ as $V_{0}\cup V_{1}\cup\ldots\cup
V_{\ell}$. Then, for each $i\in[\ell]$ in turn, we embed $T_{i}$ into
$G[V_{i-1}\cup V_{i}]$, attached appropriately to the existing embedding, so
that, if $i<\ell$, all the unused vertices in $V_{i-1}$ are covered, and the
sole vertex shared by $T_{i}$ and $T_{i+1}$ is embedded into $V_{i}$. This is
depicted in Figure 1.

$T_{1}$$T_{2}$$T_{3}$$T:$$t_{0}$$t_{1}$$t_{2}$$t_{3}$$\dots$

$V_{0}$$V_{1}$$V_{2}$$V_{3}$$V_{4}$$\cdots$$G:$$\dots$$S_{1}$$S_{2}$$S_{3}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$

Figure 1: To embed $T$ for Theorem 2.5, we divide $T$ into
$T_{1}\cup\ldots\cup T_{\ell}$ using Lemma 2.11, then find an accompanying
vortex partition $V_{0}\cup V_{1}\cup\ldots\cup V_{\ell}$ (of a large subgraph
$G^{\prime}$ of $G$) using Lemma 5.8. We then use Lemma 4.1 to iteratively
embed $T_{i}$ into $G[V_{i-1}\cup V_{i}]$, where, if $i<\ell$, any unused
vertices in $V_{i-1}$ are covered and the common vertex $t_{i}$ of $T_{i}$ and
$T_{i+1}$ is embedded to $v_{i}$ in $V_{i}$.

To embed each $T_{i}$, except for the last piece, $T_{\ell}$, where we have
very few spare vertices, we use Lemma 4.1. In order to do this in the manner
described for the partition $V_{0}\cup V_{1}\cup\ldots\cup V_{\ell}$, we need
several properties, which we record, as follows, as a vortex-partition.
Essentially, we require the sets to have (approximately) the right size (see
E1), and that, for each $i\in[\ell]$, the subgraph we are using to embed
$T_{i}$ (which will be a subgraph of $G[V_{i-1}\cup V_{i}]$) is joined (see
E2) and the set of any remaining vertices in $V_{i-1}$ to be covered is,
considered as a empty graph, extendable (which will follow from E3).

######  Definition 5.1 (Vortex partition).

Let $d\in\mathbb{N}$ and $\lambda>0$, and let
$\mathbf{n}\in\mathbb{N}^{\ell+1}$. For a graph $G$ an
$(\mathbf{n},\lambda,d)$-vortex-partition in $G$ is a partition $V_{0}\cup
V_{1}\cup\ldots\cup V_{\ell}$ of $V(G)$ such that the following hold.

  1. E1

For each $i\in[\ell]_{0}$, $|V_{i}|=(1\pm\lambda)n_{i}$.

  2. E2

For each $i\in[\ell]$, $G[V_{i-1}\cup V_{i}]$ is $(\lambda n_{i-1})$-joined.

  3. E3

For each $i\in[\ell]$, $I(V_{i-1})$ is $(d,\lambda n_{i-1})$-extendable in
$G[V_{i-1}\cup V_{i}]$.

We need the vortex partition that we find to cover all but very few (at most
$m/4$) vertices in the graph $G$. To do this, we first find an initial
‘vortex’ in Section 5.1, before ‘cleaning’ this into a vortex partition in
Section 5.2. We can then carry out our embedding in Section 5.3, completing
the proof of Theorem 2.5.

###  5.1 Vortices

To find our vortex partition, we first find a vortex in our graph $G$, which
is a _nested_ sequence of vertex sets with an increasingly good expansion
property as the sets decrease in size. We define this precisely as follows.

######  Definition 5.2 (Vortex).

Let $\ell$ be a non-negative integer, $\lambda>0$, $m\in\mathbb{N}$, and let
$\mathbf{n}=(n_{0},\dots,n_{\ell})\in\mathbb{N}^{\ell+1}$. For a graph $G$ on
$n_{0}$ vertices, an $(\mathbf{n},m,\lambda)$-vortex in $G$ is a sequence of
subsets $U_{0}\supset U_{1}\supset\ldots\supset U_{\ell}$ such that
$U_{0}=V(G)$ and, for each $i\in[\ell]$,

  1. F1

$|U_{i}|=n_{i}$, and

  2. F2

every subset $U\subset U_{i-1}$ with $|U|=m$ satisfies
$|N(U,U_{i})|\geq(1-\lambda)|U_{i}|$.

For an appropriate descending tuple
$\mathbf{n}=(n_{0},\ldots,n_{\ell})\in\mathbb{N}^{\ell+1}$ and an $n$-vertex
graph $G$ which is $(m,\mu n)$-joined we will find an
$(\mathbf{n},m,2\lambda)$-vortex $U_{0}\supset U_{1}\supset\ldots\supset
U_{\ell}$ in $G$ (with $\mu\ll\lambda$) by randomly choosing such a nested
subsequence subject only to $|U_{i}|=n_{i}$ for all $i\in[\ell]_{0}$, and
showing that it is an $(\mathbf{n},m,2\lambda)$-vortex with high probability
(see Lemma 5.3). In this we are inspired by a similar vortex used by Barber,
Kühn, Lo, and Osthus [3] in a graph with high minimum degree, and we use some
similar calculations in the analysis.

More challengingly though, we want to show that we can ensure that
$G[U_{\ell-1}]$ is also $(\lambda m)$-joined. To this end, we additionally
choose the vortex with two vertex sets $V_{0}\supset V_{1}$ such that, with
high probability, $V_{0}$ and $V_{1}$ fit into the randomly chosen nested
subsequence that will be (with high probability) our vortex so that $V_{1}$
contains $U_{\ell-1}$. Then, we show that with high probability, every $m$-set
in $V_{0}$ has at most $\lambda m$ non-neighbours in $V_{0}$, and, conditioned
on this, that every $(\lambda m)$-set in $V_{1}$ has at most $\lambda m$ non-
neighbours in $V_{0}$. For this, we need the random sets to jump down in size
by more than the standard ratio between the sets in the vortex, which is why
we take the additional sets $V_{0}$ and $V_{1}$. We also use sets $W$ and
$W^{\prime}$ chosen disjointly which will fit within $U_{1}\setminus U_{2}$
with high probability, for a similar ease of analysis for the expansion of
small sets into $U_{1}\setminus U_{2}$. Using all this, we prove the following
lemma finding the vortex that we will need.

######  Lemma 5.3.

Let

$\frac{1}{m}\ll\mu\ll\frac{1}{K},\frac{1}{D}\ll\lambda,\gamma_{1},\gamma_{2}\leq\frac{1}{9},$

with $\gamma_{1}<\gamma_{2}$ and let $n$ be such that $m\leq\mu n$. Let $G$ be
an $n$-vertex $(m,\mu n)$-joined graph which is a $(D,m)$-expander, and let
$\mathbf{n}=(n_{0},n_{1},\dots,n_{\ell})$ be a
$(\gamma_{1},\gamma_{2})$-descending tuple with $n_{0}=n$ and
$\gamma_{1}Km\leq n_{\ell}\leq 2Km$.

Then, $G$ contains an $(\mathbf{n},m,2\lambda)$-vortex $U_{0}\supset
U_{1}\supset\ldots\supset U_{\ell}$ such that $G[U_{\ell-1}]$ is $\lambda
m$-joined and, for every $U\subset V(G)$ with $|U|=\lfloor\frac{m}{4}\rfloor$,
$|N_{G}(U,U_{1}\setminus U_{2})|\geq\gamma_{1}Dm/200$.

###### Proof.

Let $K_{0}$ be such that $\mu\ll\frac{1}{K_{0}}\ll\frac{1}{K}$ and let
$k\in[\ell]$ be some index with $\gamma_{1}K_{0}m\leq n_{k}\leq K_{0}m$. Let
$p_{0}=\frac{2n_{k}}{n_{0}}$ and $q=\frac{n_{1}-n_{2}}{4n_{0}}$, and take
random disjoint sets $V_{0}$, $W$ and $W^{\prime}$ in $V(G)$ so that the
location of each vertex is selected uniformly at random and is in $V_{0}$ with
probability $p_{0}$, in $W$ with probability $q$ and in $W^{\prime}$ with
probability $q$. Let $V_{1}\subset V_{0}$ be formed by including each element
of $V_{0}$ independently at random with probability
$p_{1}:=\frac{2n_{\ell-1}}{n_{k}}$. Let $F$ be the event that
$n_{k}\leq|V_{0}|\leq 3n_{k}$, $n_{\ell-1}\leq|V_{1}|\leq 9n_{\ell-1}$, and
$\frac{n_{1}-n_{2}}{6}\leq|W|,|W^{\prime}|\leq\frac{n_{1}-n_{2}}{3}$. If $F$
holds, then let $U_{0}\supset U_{1}\supset\ldots\supset U_{\ell}$ be a
sequence of sets chosen uniformly at random subject to $U_{k-1}\supset
V_{0}\supset U_{k}$, $U_{\ell-2}\supset V_{1}\supset U_{\ell-1}$,
$U_{1}\setminus U_{2}\supset W\cup W^{\prime}$, and $|U_{i}|=n_{i}$ for each
$i\in[\ell]_{0}$ (where we have used that $|W\cup
W^{\prime}|\leq\frac{2(n_{1}-n_{2})}{3}$, $|V_{1}|\leq 9n_{\ell-1}\leq
n_{\ell-1}/\gamma_{2}\leq n_{\ell-2}$, and, similarly, $|V_{0}|\leq n_{k-1}$).
If $F$ does not hold, then let $U_{0}\supset U_{1}\supset\ldots\supset
U_{\ell}$ be a sequence of sets chosen uniformly at random subject to
$U_{i}=n_{i}$ for each $i\in[\ell]_{0}$.

######  Claim 5.4.

With probability more than $3/4$, $F$ holds.

######  Claim 5.5.

With probability more than $3/4$, $U_{0}\supset U_{1}\supset\ldots\supset
U_{\ell}$ is an $(\mathbf{n},m,2\lambda)$-vortex in $G$.

######  Claim 5.6.

With probability more than $3/4$, for every set $U\subset V(G)$ with
$|U|=\lfloor\frac{m}{4}\rfloor$, we have $|N_{G}(U,W\cup
W^{\prime})|\geq\gamma_{1}Dm/200$.

######  Claim 5.7.

With probability more than $3/4$, $G[V_{1}]$ is $(\lambda m)$-joined.

These claims easily imply the lemma. Indeed, by them, we have that, with
positive probability, $F$ holds, $U_{0}\supset U_{1}\supset\ldots\supset
U_{\ell}$ is an $(\mathbf{n},m,2\lambda)$-vortex in $G$, every subset
$U\subset V$ with $|U|=\lfloor\frac{m}{4}\rfloor$ satisfies $|N(U,W\cup
W^{\prime})|\geq\gamma_{1}Dm/200$, and $G[V_{1}]$ is $(\lambda m)$-joined.
Moreover, as $F$ holds, we have $U_{\ell-1}\subset V_{1}$ and thus
$G[U_{\ell-1}]$ is $(\lambda m)$-joined, and, as $W\cup W^{\prime}\subset
U_{1}\setminus U_{2}$, we have that every subset $U\subset V(G)$ with
$|U|=\lfloor\frac{m}{4}\rfloor$ satisfies $|N(U,U_{1}\setminus
U_{2})|\geq\gamma_{1}Dm/200$, as required. Thus, it is left only to prove the
four claims.

###### Proof of Claim 5.4.

Now, by Lemma 2.20, using $p_{0}=2n_{k}/n_{0}$ and
$n_{k}\geq\gamma_{1}K_{0}m$, we have

$\mathbb{P}\left(\big{|}|V_{0}|-2n_{k}\big{|}>n_{k}\right)\leq
2\exp(-2n_{k}/12)=2\exp(-n_{k}/6)<1/16.$

Conditioning on $n_{k}\leq|V_{0}|\leq 3n_{k}$ and again by Lemma 2.20, using
$p_{1}=2n_{\ell}/n_{k}$ and $n_{\ell}\geq\gamma_{1}Km$, we have

$\mathbb{P}(|V_{1}|\leq n_{\ell}\text{ or }|V_{1}|\geq
9n_{\ell})\leq\mathbb{P}(||V_{1}|-p_{1}|V_{0}||\geq p_{1}|V_{0}|/2)\leq
2\exp(-n_{\ell}/6)<1/16.$

Similarly, by Lemma 2.20, using $q=\frac{n_{1}-n_{2}}{4n_{0}}$ and
$n_{2}\leq\gamma_{2}n_{1}$, we have for each $i\in[2]$,

$\mathbb{P}\left(\big{|}|W_{i}|-\tfrac{n_{1}-n_{2}}{4}\big{|}>\tfrac{n_{1}-n_{2}}{12}\right)\leq
2\exp(-(n_{1}-n_{2})/108)<\frac{1}{16}.$ (5.1)

Thus, with probability more than $1-4/16=3/4$, we have $n_{k}\leq|V_{0}|\leq
3n_{k}$, $n_{\ell}\leq|V_{1}|\leq 9n_{\ell}$, and
$\frac{n_{1}-n_{2}}{6}\leq|W|,|W^{\prime}|\leq\frac{n_{1}-n_{2}}{3}$, and
hence $F$ holds. ∎

###### Proof of Claim 5.5.

Note that, as $V_{0},V_{1},W,W^{\prime}$ are themselves random sets, the sets
$U_{0}\supset U_{1}\supset\ldots\supset U_{\ell}$ have the same distribution
as a nested sequence of sets chosen uniformly at random subject to
$|U_{i}|=n_{i}$ for each $i\in[\ell]_{0}$, whether $F$ holds or not. Now, for
each $i\in[\ell]_{0}$, let $\varepsilon_{i}=\left({m}/{n_{i}}\right)^{1/4}$
and $\mathbf{n}_{i}=(n_{0},n_{1},\dots,n_{i})$. For each $i\in[\ell]$, let
$E_{i}$ be the event that $U_{0}\supset U_{1}\supset\ldots\supset U_{i-1}$ is
an $(\mathbf{n}_{i},m,\lambda+\varepsilon_{i-1})$-vortex, but $U_{0}\supset
U_{1}\supset\ldots\supset U_{i}$ is not an
$(\mathbf{n}_{i},m,\lambda+\varepsilon_{i})$-vortex. As $\varepsilon_{0}\geq
0$ and $\lambda\geq\mu$, $U_{0}=V(G)$ is an
$(\mathbf{n}_{0},m,\lambda+\varepsilon_{0})$-vortex. If no event $E_{i}$,
$i\in[\ell]$, holds, then $U_{0}\supset U_{1}\supset\ldots\supset U_{\ell}$ is
an $(\mathbf{n}_{0},m,\lambda+\varepsilon_{\ell})$-vortex, and hence an
$(\mathbf{n}_{0},m,2\lambda)$-vortex as
$\varepsilon_{\ell}=(m/n_{\ell})^{1/4}\leq(\gamma_{1}K)^{-1/4}\leq\lambda$.
Therefore, to prove the claim it is sufficient to show that

$\sum_{i\in[\ell]}\mathbb{P}(E_{i})<\frac{1}{4}.$

Let $i\in[\ell]$, and suppose that $U_{0}\supset U_{1}\supset\ldots\supset
U_{i-1}$ is an $(\mathbf{n}_{i-1},m,\lambda+\varepsilon_{i-1})$-vortex. For
each $U\subset U_{i-1}$ with $|U|=m$, as
$|N(U,U_{i-1})|\geq(1-\lambda-\varepsilon_{i-1})n_{i-1}$, we have
$\mathbb{E}|N(U,U_{i})|\geq(1-\lambda-\varepsilon_{i-1})n_{i}\geq n_{i}/2$
and, by Lemma 2.20 with $\varepsilon=(m/n_{i})^{1/3}$, that

$\mathbb{P}\left(|N(U,U_{i})|<\Big{(}1-\lambda-\varepsilon_{i-1}-\left(\frac{m}{n_{i}}\right)^{1/3}\Big{)}n_{i}\right)\leq
2\exp\left(-\left(\frac{m}{n_{i}}\right)^{2/3}\cdot\frac{n_{i}}{6}\right)=2\exp\left(-\frac{m}{6}\cdot\left(\frac{n_{i}}{m}\right)^{1/3}\right).$
(5.2)

Now, as $n_{i}\leq\gamma_{2}n_{i-1}$, we have

$\varepsilon_{i}-\varepsilon_{i-1}=\left(\frac{m}{n_{i}}\right)^{1/4}-\left(\frac{m}{n_{i-1}}\right)^{1/4}=\left(\frac{m}{n_{i}}\right)^{1/4}\left(1-\left(\frac{n_{i}}{n_{i-1}}\right)^{1/4}\right)\geq\left(\frac{m}{n_{i}}\right)^{1/4}(1-\gamma_{2}^{1/4})\geq\left(\frac{m}{n_{i}}\right)^{1/3},$
(5.3)

as $n_{i}\geq n_{\ell}\geq\gamma_{1}Km$ and $1/K\ll\gamma_{1},\gamma_{2}$, so
that $(1-\gamma_{2}^{1/4})\geq(1/\gamma_{1}K)^{1/12}\geq(m/n_{i})^{1/12}$.
Furthermore, in preparation for taking a union bound over all sets $U\subset
U_{i-1}$ with size $m$, as $\gamma_{1}n_{i-1}\leq n_{i}$, we have

$\displaystyle\binom{n_{i-1}}{m}\cdot
2\exp\left(-\frac{m}{6}\cdot\left(\frac{n_{i}}{m}\right)^{1/3}\right)$
$\displaystyle\leq\left(\frac{en_{i-1}}{m}\right)^{m}\cdot
2\exp\left(-\frac{m}{6}\cdot\left(\frac{n_{i}}{m}\right)^{1/3}\right)$
$\displaystyle\leq
2\exp\left(\frac{m}{6}\cdot\left(6\log\left(\frac{en_{i}}{\gamma_{1}m}\right)-\left(\frac{n_{i}}{m}\right)^{1/3}\right)\right)$
$\displaystyle\leq
2\exp\left(-\frac{m}{12}\cdot\left(\frac{n_{i}}{m}\right)^{1/3}\right)\leq\frac{m}{n_{i}},$
(5.4)

where the last line of inequalities holds as $1/K\ll\gamma_{1},\gamma_{2}$ and
$n_{i}/m\geq n_{\ell}/m\geq\gamma_{1}K$. Therefore, by (5.2), (5.3) and (5.4),
and by taking a union bound, we have that, with probability more than
$1-(m/n_{i})$, for each $U\subset U_{i-1}$ with $|U|=m$ we have
$|N(U,U_{i})|\geq(1-\lambda-\varepsilon_{i})n_{i}$.

Hence, we have

$\sum_{i\in[\ell]}\mathbb{P}(E_{i})\leq\sum_{i\in[\ell]}\frac{m}{n_{i}}\leq\sum_{i\in[\ell]}\frac{m}{n_{\ell}}\cdot\gamma_{2}^{\ell-i}\leq\frac{1}{1-\gamma_{2}}\cdot\frac{m}{n_{\ell}}\leq\frac{2m}{n_{\ell}}\leq\frac{2}{\gamma_{1}K}<\frac{1}{4},$

as required. ∎

###### Proof of Claim 5.6.

Let $E$ be the event that $|W|\geq\frac{n_{1}-n_{2}}{6}$. By (5.1),
$\mathbb{P}(E)\geq 7/8$. Note that, if $E$ holds, then
$|W|\geq{\gamma_{1}n}/{8}\geq\mu n+(2\gamma_{1}D+2)m$, as
$n_{1}-n_{2}\geq(1-\gamma_{2})\gamma_{1}n\geq 7\gamma_{1}n/8$ and $\mu\ll
1/D\ll\gamma_{1}$. Thus, for every choice of $W$ for which $E$ holds, we can
apply Proposition 2.13 to find $B_{W}\subset V(G)$ such that $|B_{W}|<m$ and,
for each $U\subset V(G)\setminus B_{W}$ with $|U|\leq m$, we have
$|N_{G}(U,W)|\geq\gamma_{1}D|U|$.

Let $E^{\prime}$ be the event that $E$ holds and
$|N_{G}(U,W^{\prime})|\geq\gamma_{1}Dm/100$ for every $U\subset B_{W}$ with
$|U|=\lfloor m/8\rfloor$ and $|N_{G}(U,W)|<\gamma_{1}Dm/100$. Note that,
conditioned on any choice of $W$ for which $E$ holds, as $G$ is a
$(D,m)$-expander, for every set $U\subset B_{W}$ with $|U|=\lfloor m/8\rfloor$
and $|N_{G}(U,W)|<\gamma_{1}Dm/100$, we have $|N_{G}(U,V(G)\setminus W)|\geq
D|U|-\gamma_{1}Dm/100\geq D|U|/2$. Thus, by Lemma 2.20 with
$\varepsilon=1/1000$ and a union bound,

$\mathbb{P}(E^{\prime}\text{ does not hold}|E\text{
holds})\leq\binom{m}{\lfloor{m/8}\rfloor}\cdot
2\exp\left(\frac{-\gamma_{1}Dm}{6\cdot 10^{8}}\right)<\frac{1}{8},$

as $1/m,1/D\ll\gamma_{1}$. Therefore, $\mathbb{P}(E^{\prime}\text{
holds})\geq\mathbb{P}(E)-\mathbb{P}(E^{\prime}\text{ does not hold}|E\text{
holds})>3/4$.

We claim that if $E^{\prime}$ holds, then, for every subset $U\subset V(G)$
with $|U|=\lfloor{m}/{4}\rfloor$, $|N_{G}(U,W\cup
W^{\prime})|\geq\gamma_{1}Dm/200$. Indeed, for a set $U\subset V(G)$ with
$|U|=\lfloor m/4\rfloor$, if $|U\cap B_{W}|\geq\lfloor m/8\rfloor$, then
either $|N_{G}(U,W)|\geq\gamma_{1}Dm/100-|U|\geq{\gamma_{1}Dm}/{200}$, or, as
$E^{\prime}$ holds,
$|N_{G}(U,W^{\prime})|\geq\gamma_{1}Dm/100-|U|\geq{\gamma_{1}Dm}/{200}$. On
the other hand, if $|U\cap B_{W}|<\lfloor m/8\rfloor$, then $|U\setminus
B_{W}|\geq\lfloor m/8\rfloor$, and so by the choice of $B_{W}$, $|N_{G}(U)\cap
W|\geq\gamma_{1}Dm/8-|U|\geq{\gamma_{1}Dm}/{200}$, as required. Since
$E^{\prime}$ holds with probability in excess of $3/4$, the claim follows. ∎

###### Proof of Claim 5.7.

We first show that $G[V_{0}]$ is not $(m,\lambda m)$-joined with probability
less than $1/12$. Note that, for each $U\subset V(G)$ with $|U|=m$ we have
$|V(G)\setminus(U\cup N(U))|\leq\mu n$, and therefore

$\mathbb{P}(U\subset V_{0}\text{ and }|V_{0}\setminus(U\cup N(U))|>\lambda
m)\leq p_{0}^{m}\cdot\binom{\mu n}{\lambda m}p_{0}^{\lambda m}.$ (5.5)

Thus, the probability that $G[V_{0}]$ is not $(m,\lambda m)$-joined is, as
$p_{0}=2n_{k}/n_{0}=2n_{k}/n$, at most

$\displaystyle\binom{n}{m}p_{0}^{m}\cdot\binom{\mu n}{\lambda m}p_{0}^{\lambda
m}$
$\displaystyle\leq\left(\frac{ep_{0}n}{m}\right)^{m}\cdot\left(\frac{ep_{0}\mu
n}{\lambda m}\right)^{\lambda
m}=\left(\frac{2en_{k}}{m}\right)^{m}\cdot\left(\frac{2e\mu n_{k}}{\lambda
m}\right)^{\lambda m}\leq\left(2eK_{0}\right)^{m}\cdot\left(\frac{2e\mu
K_{0}}{\lambda}\right)^{\lambda m}$
$\displaystyle=\left(2eK_{0}\right)^{(1+\lambda)m}\cdot\left(\frac{\mu}{\lambda}\right)^{\lambda
m}\leq K_{0}^{3m}\cdot\left(\frac{\mu}{\lambda}\right)^{\lambda
m}\leq\frac{1}{12},$ (5.6)

where the last inequality follows as $\mu\ll 1/K_{0}\ll\lambda$.

From the proof of Claim 5.4, we have $\mathbb{P}(|V_{0}|>4n_{k})<1/12$.
Furthermore, if $G[V_{0}]$ is $(m,\lambda m)$-joined and $|V_{0}|\leq 4n_{k}$,
then, by similar calculations to those in (5.5) and (5.6) and as
$p_{1}=2n_{\ell-1}/n_{k}$, $n_{\ell-1}\leq 2Km/\gamma_{1}$ and
$n_{k}\geq\gamma_{1}K_{0}m$, we have that $G[V_{1}]$ is not $(\lambda
m)$-joined with probability at most

$\displaystyle\binom{4n_{k}}{\lambda m}p_{1}^{\lambda m}\cdot\binom{m}{\lambda
m}p_{1}^{\lambda m}$ $\displaystyle\leq\left(\frac{4ep_{1}n_{k}}{\lambda
m}\right)^{\lambda m}\cdot\left(\frac{ep_{1}m}{\lambda m}\right)^{\lambda
m}=\left(\frac{16e^{2}n_{\ell-1}^{2}}{\lambda^{2}mn_{k}}\right)^{\lambda
m}\leq\left(\frac{64e^{2}K^{2}}{\lambda^{2}\gamma_{1}^{3}K_{0}}\right)^{\lambda
m}<\frac{1}{12},$

where the last inequality holds as $1/K_{0}\ll 1/K\ll\lambda,\gamma_{1}$ and
$1/m\ll\lambda$.

Altogether then, with probability in excess of $3/4$, $G[V_{1}]$ is $(\lambda
m)$-joined. ∎ $\square$

∎

###  5.2 Vortex partition

We now use Lemma 5.3 to find a vortex $U_{0}\supset U_{1}\supset\ldots\supset
U_{\ell}$ and then run a simple ‘cleaning procedure’ to find disjoint sets
$V_{1},V_{2},\ldots,V_{\ell}$ for a vortex partition (see Definition 5.1) such
that $V_{i}$ is a subset of $U_{i}\setminus U_{i+1}$ which contains almost all
those vertices for each $i\in[\ell]$, before then completing the vortex
partition by using all but at most $m/4$ of the remaining vertices not in
$\cup_{i\in[\ell]}V_{i}$ to form $V_{0}$. This will give us the following
result.

######  Lemma 5.8.

Let

$\frac{1}{m}\ll\mu\ll\frac{1}{K},\frac{1}{D}\ll\lambda\ll\frac{1}{d}\ll\gamma_{1},\gamma_{2}\leq\frac{1}{16},$

with $\gamma_{1}<\gamma_{2}$ and let $n$ be such that $m\leq\mu n$. Let $G$ be
an $n$-vertex $(m,\mu n)$-joined graph which is a $(D,m)$-expander. Let
$\ell\in\mathbb{N}$ and let $\mathbf{n}=(n_{0},n_{1},\dots,n_{\ell})$ be a
$(\gamma_{1},\gamma_{2})$-descending tuple with $n=\sum_{i\in[\ell]_{0}}n_{i}$
and $\gamma_{1}Km\leq n_{\ell}\leq 2Km$.

Then, $G$ contains a subgraph $G^{\prime}$ with at least
$n-\lfloor{m/4}\rfloor$ vertices that has an $(\mathbf{n},2\lambda,d)$-vortex
partition $V_{0}\cup V_{1}\cup\ldots\cup V_{\ell}$ such that $G[V_{\ell-1}\cup
V_{\ell}]$ is $(\lambda m)$-joined.

###### Proof.

Let
$\mathbf{n}^{\prime}=(n_{0}^{\prime},n_{1}^{\prime},\ldots,n_{\ell}^{\prime})$
with $n_{i}^{\prime}=\sum_{j=i}^{\ell}n_{i}$ for each $i\in[\ell]_{0}$. Note
that $\mathbf{n}^{\prime}$ is $(\gamma_{1}/2,\gamma_{2})$-descending,
$n^{\prime}_{j}/2\leq n_{j}\leq n^{\prime}_{j}$ for all $j\in[\ell]_{0}$, and
$\gamma_{1}Km\leq n^{\prime}_{\ell}\leq 2Km$. Therefore, by Lemma 5.3, $G$
contains an $(\mathbf{n}^{\prime},m,2\lambda)$-vortex $U_{0}\supset
U_{1}\supset\ldots\supset U_{\ell}$ such that $G[U_{\ell-1}]$ is $(\lambda
m)$-joined and, for every set $U\subset V(G)$ with
$|U|=\lfloor\frac{m}{4}\rfloor$, $|N_{G}(U,U_{1}\setminus
U_{2})|\geq\gamma_{1}Dm/200$. For each $i\in[\ell-1]_{0}$, let
$V^{\prime}_{i}=U_{i}\setminus U_{i+1}$, and let $V^{\prime}_{\ell}=U_{\ell}$.
Note that, for each $i\in[\ell]_{0}$, $|V^{\prime}_{i}|=n_{i}$.

Let $W_{\ell+1}=\emptyset$. Now, for each $j=\ell,\ell-1,\ldots,1$ in turn, do
the following, where $W_{j+1}$ is a set chosen (if $j<\ell$) in the previous
iteration such that $|W_{j+1}|<m$.

  1. G1

Note that, as $\lambda\ll\gamma_{1}$ and $d\ll K$, we have
$|V_{j}^{\prime}\setminus W_{j+1}|\geq n_{j}-m\geq 2\lambda n_{j-1}+(2d+2)m$.

  2. G2

Note that, by F2 and $V^{\prime}_{j-1}\cup V^{\prime}_{j}\subset U_{j-1}$, we
have that $G[V^{\prime}_{j-1}\cup(V_{j}^{\prime}\setminus W_{j+1})]$ is
$(m,\lambda n^{\prime}_{j-1})$-joined, and hence $(m,2\lambda
n_{j-1})$-joined.

  3. G3

Using Proposition 2.13, take $W_{j}\subset
V^{\prime}_{j-1}\cup(V_{j}^{\prime}\setminus W_{j+1})$ such that $|W_{j}|<m$
and, for each $U\subset(V^{\prime}_{j-1}\cup
V_{j}^{\prime})\setminus(W_{j}\cup W_{j+1})$ with $|U|\leq m$,
$|N_{G}(U,V_{j}^{\prime}\setminus(W_{j}\cup W_{j+1}))|\geq d|U|$.

  4. G4

Let $V_{j}=V_{j}^{\prime}\setminus(W_{j}\cup W_{j+1})$.

Now, for every set $U\subset V(G)$ with $|U|=\lfloor{m/4}\rfloor$, we have

$|N_{G}(U,V_{1})|\geq|N_{G}(U,V^{\prime}_{1})|-|W_{1}\cup
W_{2}|\geq\gamma_{1}Dm/200-2m\geq\gamma_{1}Dm/500,$

as $1/D\ll\gamma_{1}$. Let $W_{0}\subset V(G)$ be a maximal subset subject to
$|W_{0}|<m/2$ and $|N_{G}(W_{0},V_{1})|\leq 10d|W_{0}|$. Similarly to the
proof of Proposition 2.13 and using $d\ll\gamma_{1}D$, we have $|W_{0}|<m/4$,
and, for each $U\subset V(G)\setminus W_{0}$ with $|U|\leq m/4$,
$|N_{G}(U,V_{1})|\geq 10d|U|$. Let $V_{0}=V(G)\setminus(W_{0}\cup
V_{1}\cup\ldots\cup V_{\ell})$ and $G^{\prime}=G[V_{0}\cup V_{1}\cup\ldots\cup
V_{\ell}]$.

Note that $|G^{\prime}|\geq n-m/4$, and that, as $V_{\ell-1}\cup
V_{\ell}\subset V_{\ell-1}^{\prime}\cup V_{\ell}^{\prime}=U_{\ell-1}$,
$G[V_{\ell-1}\cup V_{\ell}]$ is $(\lambda m)$-joined. Therefore, to complete
the proof it is left only to show that $V_{0}\cup V_{1}\cup\dots\cup V_{\ell}$
is an $(\mathbf{n},2\lambda,d)$-vortex partition of $G^{\prime}$.

Since $V^{\prime}_{0}\setminus W_{0}\subset V_{0}\subset V_{0}^{\prime}\cup
W_{1}\cup\ldots\cup W_{\ell}$, $|W_{0}|\leq\left\lfloor m/4\right\rfloor$ and
$|W_{1}\cup\ldots\cup W_{\ell}|\leq\ell m$, we have
$(1-2\lambda)n_{0}\leq|V_{0}|\leq(1+2\lambda)n_{0}$, proving the $j=0$ case of
E1. For all $j\in[\ell]$, $|V^{\prime}_{j}|=n_{j}$,
$V_{j}=V^{\prime}_{j}\setminus(W_{j}\cup W_{j+1})$ and
$|W_{j}|,|W_{j+1}|<m\leq\lambda n_{j}$, so we have $|V_{j}|\geq
n_{j}-2m\geq(1-2\lambda)n_{j}$ and E1 holds. Now let $2\leq j\leq\ell$. Since
$V_{j-1}\subset V^{\prime}_{j-1}$ and $V_{j}\subset V_{j}^{\prime}\setminus
W_{j+1}$, $G[V_{j-1}\cup V_{j}]$ is $(m,2\lambda n_{j-1})$-joined by G2, hence
$(2\lambda n_{j-1})$-joined, and thus E2 holds. For E3, let $U\subset
V_{j-1}\cup V_{j}\subset(V^{\prime}_{j-1}\cup
V^{\prime}_{j})\setminus(W_{j}\cup W_{j+1})$ satisfy $|U|\leq 4\lambda
n_{j-1}$. If $|U|\leq m$, we have $|N(U,V_{j})|\geq d|U|$ by G3. If $|U|>m$,
then since $G[V_{j-1}\cup V_{j}]$ is $(m,2\lambda n_{j-1})$-joined and
$d\lambda\ll\gamma_{1}$, we have

$|N(U,V_{j})|\geq|V_{j}|-|U|-2\lambda n_{j-1}\geq(n_{j}-2m)-4\lambda
n_{j-1}-2\lambda n_{j-1}\geq 4d\lambda n_{j-1}\geq d|U|.$

Hence, $I(V_{j-1})$ is $(d,2\lambda n_{j-1})$-extendable in $G[V_{j-1}\cup
V_{j}]$ by Proposition 2.15, and so E3 holds.

For the $j=1$ case, E2 holds as $G\supset G[V_{0}\cup V_{1}]$ is $(m,\mu
n)$-joined, thus $(m,2\lambda n_{0})$-joined and $(2\lambda n_{0})$-joined.
Let $U\subset V_{0}\cup V_{1}$ satisfy $|U|\leq 4\lambda n_{0}$. If
$|U|\leq\left\lfloor m/4\right\rfloor$, then $|N(U,V_{1})|\geq 10d|U|\geq
d|U|$. If $\left\lfloor m/4\right\rfloor<|U|\leq m$, then let
$U^{\prime}\subset U$ have size $\left\lfloor m/4\right\rfloor$, and thus

$|N(U,V_{1})|\geq|N(U^{\prime},V_{1})|-|U\setminus U^{\prime}|\geq
10d|U^{\prime}|-|U|\geq 2dm-m\geq dm\geq d|U|.$

If $|U|>m$, then, since $G[V_{0}\cup V_{1}]$ is $(m,2\lambda n_{0})$-joined,
we have

$|N(U,V_{1})|\geq|V_{1}|-|U|-2\lambda n_{0}\geq n_{1}-2m-6\lambda n_{0}\geq
4d\lambda n_{0}\geq d|U|.$

Thus, we have that $I(V_{0})$ is $(d,2\lambda n_{0})$-extendable in
$G[V_{0}\cup V_{1}]$, proving the $j=1$ case of E3. This completes the proof
that $V_{0}\cup V_{1}\cup\ldots\cup V_{\ell}$ is an
$(\mathbf{n},d,2\lambda)$-vortex partition of $G^{\prime}$. ∎

###  5.3 Proof of Theorem 2.5

Using Lemma 5.8, we can now prove Theorem 2.5 following the outline at the
start of this section.

###### Proof of Theorem 2.5.

Let $d=10^{4}\Delta^{5}$, $\gamma=1/10\Delta$ and note that
$d\gg\Delta^{3}/\gamma$. Let

$\frac{1}{m}\ll\mu\ll\frac{1}{K},\frac{1}{D}\ll\lambda\ll\frac{1}{d}.$

Let $\gamma_{1}=\gamma/4\Delta$ and $\gamma_{2}=2\gamma$, and let $T$ be a
tree with $n-m+1$ vertices and $\Delta(T)\leq\Delta$. Using Lemma 2.11, we can
find some $\ell\in\mathbb{N}$, some
$\mathbf{n^{\prime}}=(n^{\prime}_{1},\ldots,n^{\prime}_{\ell})\in\mathbb{N}^{\ell}$
that is $(\gamma_{1},\gamma_{2})$-descending with $\gamma Km/3\Delta\leq
n^{\prime}_{\ell}\leq Km$, and an $\mathbf{n}^{\prime}$-decomposition
$(T_{1},\ldots,T_{\ell})$ of $T$. For $1\leq i\leq\ell-1$, let $t_{i}$ be the
leaf of $T_{i}$ in $T_{i+1}$, and let $t_{\ell}$ be an arbitrary leaf of
$T_{\ell}$ which is not $t_{\ell-1}$. As every tree with at least 2 vertices
has at least 2 leaves, we may also take a leaf $t_{0}$ of $T_{1}$ which is not
$t_{1}$.

Let $n_{0}=\left\lceil(1-\gamma_{2})n^{\prime}_{1}\right\rceil$, let
$n_{j}=\left\lfloor\gamma_{2}n_{j}^{\prime}\right\rfloor+\left\lceil(1-\gamma_{2})n^{\prime}_{j+1}\right\rceil$
for each $j\in[\ell-1]$, and let
$n_{\ell}=\left\lfloor\gamma_{2}n^{\prime}_{\ell}\right\rfloor+m-1$. Note
that, for each $j\in[\ell]$, $n_{j}\leq n_{j}^{\prime}$ and

$\sum_{i=j}^{\ell}n_{i}=\left\lfloor\gamma_{2}n_{j}^{\prime}\right\rfloor+\sum_{i=j+1}^{\ell}n^{\prime}_{i}+(m-1),$
(5.7)

and

$\sum_{i=0}^{\ell}n_{i}=\sum_{i=1}^{\ell}n^{\prime}_{i}+(m-1)=|T|+(m-1)=n.$
(5.8)

Moreover, using $\mathbf{n}^{\prime}$ is $(\gamma_{1},\gamma_{2})$-descending,
we can verify that $\textbf{n}=(n_{0},n_{1},\ldots,n_{\ell})$ is
$(\gamma_{1}/2,3\gamma_{2})$-descending. Let $K^{\prime}=K/5\Delta$ and note
that $n_{\ell}=\left\lfloor\gamma_{2}n^{\prime}_{\ell}\right\rfloor+m-1\leq
2\gamma_{2}n^{\prime}_{\ell}\leq 2K\gamma_{2}m=2Km/5\Delta=2K^{\prime}m$ as
$\gamma_{2}=1/5\Delta$, while
$n_{\ell}\geq\left\lfloor\gamma_{2}n^{\prime}_{\ell}\right\rfloor\geq\gamma_{2}\cdot\gamma
Km/6\Delta\geq\gamma_{2}\cdot 5\gamma K^{\prime}m/6=\gamma
K^{\prime}m/6\Delta\geq\gamma_{1}K^{\prime}m/2$ as
$\gamma_{1}=\gamma/4\Delta$. Since $\mu\ll 1/K^{\prime}\ll\lambda$, using
Lemma 5.8, we can take a subgraph $G^{\prime}$ of $G$ with at least $n-\lfloor
m/4\rfloor$ vertices which has an $(\mathbf{n},2\lambda,d)$-vortex partition,
$V_{0}\cup V_{1}\cup\ldots\cup V_{\ell}$ say, such that $G[V_{\ell-1}\cup
V_{\ell}]$ is $(\lambda m)$-joined.

For each $j\in[\ell]_{0}$, say that we have a stage j situation if we have
distinct vertices $v_{0},v_{1},\ldots,v_{j}$ and copies $S_{1},\ldots,S_{j}$
of the trees $T_{1},\ldots,T_{j}$, respectively, so that the following hold.

  1. H1

If $i\in[j]_{0}$, then $v_{i}\in V_{i}$.

  2. H2

If $i\in[j]$, then
$\cup_{i^{\prime}=0}^{i-1}V_{i^{\prime}}\subset\cup_{i^{\prime}=1}^{i}V(S_{i^{\prime}})\subset\cup_{i^{\prime}=0}^{i}V_{i^{\prime}}$.

  3. H3

For each $i\in[j]$, $t_{i-1}$ is copied to $v_{i-1}$ in $S_{i}$ and $t_{i}$ is
copied to $v_{i}$ in $S_{i}$.

  4. H4

For each $1\leq i<i^{\prime}\leq j$, $V(S_{i})\cap
V(S_{i^{\prime}})=\\{v_{i}\\}\cap\\{v_{i^{\prime}-1}\\}$.

Arbitrarily, pick $v_{0}\in V_{0}$, and note that this gives us a stage $0$
situation as H1 holds and H2–H4 are vacuous. Furthermore, if we have a stage
$\ell$ situation, with vertices $v_{0},v_{1},\ldots,v_{\ell}$ and copies
$S_{1},\ldots,S_{\ell}$ of the trees $T_{1},\ldots,T_{\ell}$, respectively,
then H3 and H4 imply that $\cup_{i\in[\ell]}S_{i}$ is a copy of
$T=\cup_{i\in[\ell]}T_{i}$ in $G^{\prime}$, and hence $G$ has a copy of $T$,
as required. Thus, the lemma is implied by the following claim and induction.

######  Claim 5.9.

For each $j\in[\ell]$, if we have a stage $j-1$ situation, then we can create
a stage $j$ situation.

###### Proof of Claim 5.9.

Set $S_{0}$ to be the tree containing only the vertex $v_{0}$. Fix
$j\in[\ell]$ and let $X_{j}=V_{j-1}\setminus V(S_{j-1})$. Now, as
$X_{j}\cup\\{v_{j-1}\\}\subset V_{j-1}$, and $V_{0}\cup V_{1}\cup\ldots\cup
V_{\ell}$ is an $(\mathbf{n},2\lambda,d)$-vortex partition, we have the
following by E3.

  1. I

$I(X_{j}\cup\\{v_{j-1}\\})$ is $(d,\lambda n_{j-1})$-extendable in
$G[X_{j}\cup\\{v_{j-1}\\}\cup V_{j}]$.

Then, if $j\leq\ell-1$,

$\displaystyle|X_{j}\cup$ $\displaystyle\\{v_{j-1}\\}\cup
V_{j}|=1+|(V_{j-1}\cup V_{j})\setminus
V(S_{j-1})|\overset{\ref{prop:stagejsit2}}{=}1+\left|\left(\cup_{i=0}^{j}V_{i}\right)\setminus\left(\cup_{i=0}^{j-1}V(S_{i})\right)\right|$
$\displaystyle=1+|G^{\prime}|-|\cup_{i=j+1}^{\ell}V_{i}|-\Big{(}|T|-\sum_{i=j}^{\ell}n^{\prime}_{i}\Big{)}$
$\displaystyle\overset{\ref{prop:vorpart1}}{\geq}1+\left(n-\left\lfloor\frac{m}{4}\right\rfloor\right)-\sum_{i=j+1}^{\ell}(1+\lambda)n_{i}-|T|+\sum_{i=j}^{\ell}n^{\prime}_{i}$
$\displaystyle\overset{\eqref{eqn:nisum}}{\geq}\left(n+1-|T|-\left\lfloor\frac{m}{4}\right\rfloor\right)-\sum_{i=j+1}^{\ell}n_{i}-2\lambda
n_{j+1}+\sum_{i=j}^{\ell}n^{\prime}_{i}$
$\displaystyle\overset{\eqref{eqn:nisum}}{\geq}\left(m-\left\lfloor\frac{m}{4}\right\rfloor\right)-\Big{(}\left\lfloor\gamma_{2}n^{\prime}_{j+1}\right\rfloor+\sum_{i=j+2}^{\ell}n_{i}^{\prime}+m-1\Big{)}-2\lambda
n^{\prime}_{j+1}+\sum_{i=j}^{\ell}n^{\prime}_{i}$ $\displaystyle\geq
n^{\prime}_{j}+\frac{n^{\prime}_{j+1}}{2}-\frac{m}{2}\geq\left(1+\frac{\gamma_{1}}{2}\right)n^{\prime}_{j}-\frac{m}{2}\hskip
125.19194pt{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color<EMAIL_ADDRESS>$\displaystyle\geq\left(1+\frac{\gamma_{1}}{2}\right)|T_{j}|-m\geq|T_{j}|+20dm,$
(5.9)

where the last inequality follows from
$\gamma_{1}|T_{j}|\geq\gamma_{1}\cdot\gamma Km/3\Delta\geq 20dm$. Furthermore,

$\displaystyle|X_{j}|$ $\displaystyle=|V_{j-1}\setminus
V(S_{j-1})|\overset{\ref{prop:stagejsit2}}{=}\left|\left(\cup_{i=0}^{j-1}V_{i}\right)\setminus\left(\cup_{i=0}^{j-1}V(S_{i})\right)\right|$
$\displaystyle=|G^{\prime}|-|\cup_{i=j}^{\ell}V_{i}|-(|T|-\sum_{i=j}^{\ell}n^{\prime}_{i})$
$\displaystyle\leq
n-\sum_{i=j}^{\ell}(1-\lambda)n_{i}-|T|+\sum_{i=j}^{\ell}n^{\prime}_{i}$
$\displaystyle\leq m+2\lambda
n_{j}-\sum_{i=j}^{\ell}n_{i}+\sum_{i=j}^{\ell}n^{\prime}_{i}$
$\displaystyle\leq n^{\prime}_{j}+2\lambda
n^{\prime}_{j}-\left\lfloor\gamma_{2}n^{\prime}_{j}\right\rfloor+1\leq\left(1-\frac{\gamma_{2}}{2}\right)n^{\prime}_{j}$
$\displaystyle\leq\left(1-\frac{\gamma_{2}}{2}\right)|T_{j}|=(1-\gamma)|T_{j}|.$
(5.10)

Finally, we have $|T_{j}|\geq
n^{\prime}_{j}\geq\gamma_{1}n^{\prime}_{j-1}\geq\gamma_{1}n_{j-1}\geq
2d^{2}\lambda n_{j-1}$ and $G[X_{j}\cup\\{v_{j-1}\\}\cup V_{j}]$ is $(\lambda
n_{j-1})$-joined by E2. Therefore, by I, (5.9), (5.10) and Lemma 4.1, we can
find a copy $S_{j}$ of $T_{j}$ in $G[X_{j}\cup\\{v_{j-1}\\}\cup V_{j}]$ with
$t_{j-1}$ copied to $v_{j-1}$, $t_{j}$ copied into $V_{j}$, and $X_{j}\subset
V(S_{j})$. Then, letting $v_{j}$ to be the copy of $t_{j}$, we have a stage
$j$ situation.

Suppose then that $j=\ell$. From I, we have that
$I(X_{\ell}\cup\\{v_{\ell-1}\\})$ is $(d,\lambda n_{\ell-1})$-extendable in
$G[X_{\ell}\cup\\{v_{\ell-1}\\}\cup V_{\ell}]$, and hence $(d,\lambda
m)$-extendable. As $X_{\ell}\cup\\{v_{\ell-1}\\}\cup V_{\ell}\subset
V_{\ell-1}\cup V_{\ell}$, we have that $G[X_{\ell}\cup\\{v_{\ell-1}\\}\cup
V_{\ell}]$ is $(\lambda m)$-joined. Furthermore,

$\displaystyle|X_{\ell}\cup\\{v_{\ell-1}\\}\cup V_{\ell}|$
$\displaystyle=1+|(V_{\ell-1}\cup V_{\ell})\setminus
V(S_{\ell-1})|\overset{\ref{prop:stagejsit2}}{=}1+\left|\left(\cup_{i=0}^{\ell}V_{i}\right)\setminus\left(\cup_{i=0}^{\ell-1}V(S_{i})\right)\right|$
$\displaystyle\geq 1+|G^{\prime}|-(|T|-|T_{\ell}|+1)\geq
n-\left\lfloor\frac{m}{4}\right\rfloor-|T|+|T_{\ell}|.$
$\displaystyle\geq|T_{\ell}|+\frac{m}{2}\geq|T_{\ell}|+10\lambda dm.$

Therefore, by Corollary 2.19, there is a copy $S_{\ell}$ of $T_{\ell}$ in
$G[X_{\ell}\cup\\{v_{\ell-1}\\}\cup V_{\ell}]$ in which $t_{\ell-1}$ is copied
to $v_{\ell-1}$. Let $v_{\ell}$ be the copy of $t_{\ell}$ and note that we
have a stage $\ell$ situation, as required. This completes the proof of the
claim and hence the theorem. ∎ $\square$

∎

##  6 Ramsey goodness of bounded degree trees

In this section, we prove Theorem 2.1 by induction from Theorem 2.2. To embed
a tree $T$ in a graph $G$ in the setting of Theorem 2.1, we will again show we
can assume some extra expansion condition, before dividing into 3
(overlapping) cases. Roughly, these cases are the following.

  1. a)

$T$ has linearly many leaves.

  2. b)

$G$ is not well connected.

  3. c)

$G$ is well connected and $T$ does not have linearly many leaves.

In each case the embedding is different, and we sketch these at the start of
Sections 6.1–6.3 respectively, before combining them to prove Theorem 2.1 in
Section 6.4.

###  6.1 Trees with linearly many leaves

We first show that, in the setting of Theorem 2.1, if $T$ has linearly many
leaves and $G$ satisfies a simple expansion condition (__J__), then $G$
contains a copy of $T$. This was shown by Balla, Pokrovskiy, and Sudakov [2],
but for completion we include the full proof, following their method while
using the extendability framework.

To embed $T$, we remove a large set of leaves, and embed the resulting tree
into the graph in an extendable fashion. We then show that the relevant
extendability conditions imply that a version of Hall’s matching criterion
holds in the appropriate subgraph to allow unused vertices to be attached to
the embedded tree as leaves in order to create a copy of the original tree.

######  Lemma 6.1.

Let $1/n\ll\mu\ll 1/\Delta$. Let $G$ be a graph with at least $n$ vertices in
which the following holds.

  1. _J_

Every set $U\subset V(G)$ with $|U|=\mu n$ satisfies $|U\cup N_{G}(U)|\geq n$.

Then, $G$ contains a copy of every $n$-vertex tree $T$ with
$\Delta(T)\leq\Delta$ and at least $10\Delta^{2}\mu n$ leaves.

###### Proof.

Let $T$ be an $n$-vertex tree with $\Delta(T)\leq\Delta$ and at least
$10\Delta^{2}\mu n$ leaves. Let $d=2\Delta$, $m=\mu n$ and $n_{0}=|G|-n+1$, so
that $G$ is $(m,n_{0})$-joined by __J__ , and

$|G|=n_{0}+n-1\geq n_{0}+(1-10\Delta\mu)n+(4d+2)m.$ (6.1)

Using Proposition 2.6, we can find $W\subset V(G)$ with $|W|<m$ such that
$G^{\prime}=G-W$ is a $(2d,m)$-expander.

Arbitrarily, pick $v\in V(G^{\prime})$. Note that, for each $U\subset
V(G^{\prime})$ with $1\leq|U|\leq m$, as $G^{\prime}$ is a $(2d,m)$-expander,
we have $|N_{G^{\prime}}(U)|\geq 2d|U|\geq 1+d|U|$. By __J__ , if $U\subset
V(G^{\prime})$ with $m\leq|U|\leq 2m$, we also have $|N_{G^{\prime}}(U)|\geq
n-2m\geq 1+2dm\geq 1+d|U|$. Thus, by Proposition 2.15, $I(\\{v\\})$ is
$(d,m)$-extendable in $G^{\prime}$.

As $T$ has at least $10\Delta^{2}\mu n$ leaves, we can find a set of leaves
$L$ such that $|L|=10\Delta\mu n$ and no pair of leaves in $L$ has a common
neighbour in $T$. Letting $T^{\prime}=T-L$, we will now embed $T^{\prime}$
into $G^{\prime}$. Note that

$1+|T^{\prime}|\leq 1+n-10\Delta\mu
n\overset{\eqref{eqn:Gsize}}{\leq}|G^{\prime}|-(2d+2)m-n_{0}.$

Then, as $G$, and thus $G^{\prime}$, is $(m,n_{0})$-joined, by Corollary 2.19
(applied with an arbitrary $t\in V(T^{\prime})$), there is a
$(d,m)$-extendable subgraph $S^{\prime}$ of $G^{\prime}$ which is a copy of
$T^{\prime}$.

Let $A\subset V(S^{\prime})$ be the copy in $S^{\prime}$ of the set of parents
in $T$ of the leaves in $L$, and let $B=V(G)\setminus V(S^{\prime})$. Observe
that to make $S^{\prime}$ into a copy of $T$, it is sufficient to find a
matching in $G$ from $A$ to $B$ and add this to $S^{\prime}$. We will find
such a matching by showing that the appropriate Hall’s matching criterion
holds.

If $U\subset A$, with $|U|\leq m$, then, as $S^{\prime}$ is $(d,m)$-extendable
in $G^{\prime}$, by (2.1) we have

$|N_{G}(U,B)|\geq|N_{G^{\prime}}(U)\setminus
V(S^{\prime})|=|N^{\prime}_{G^{\prime}}(U)\setminus
V(S^{\prime})|{\geq}(d-1)|U|-(\Delta-1)|U|\geq|U|.$

On the other hand, if $U\subset A$ with $|U|\geq m$, then

$|N_{G}(U,B)|\geq|U\cup
N_{G}(U)|-|T^{\prime}|\overset{\emph{\ref{prop:manyleaves2}}}{\geq}n-(n-|L|)=|A|\geq|U|.$

Therefore, for each $U\subset A$ we have $|N_{G}(U,B)|\geq|U|$, and thus, as
Hall’s matching criterion holds, $G$ has a matching from $A$ to $B$, as
required. ∎

###  6.2 Non-well-connected graphs

For the next case in the induction step of Theorem 2.1, which we prove as
Lemma 6.2 below, we will use properties that will follow from induction (see
_K1_ below) and our graph $G$ will not be well-connected, in the sense that it
will have a vertex partition $V_{0}\cup V_{1}\cup V_{2}$ in which $V_{0}$
contains at most a small linear (in $n$) number of vertices and there are no
edges in $G$ between $V_{1}$ and $V_{2}$, which are both large sets (see
_K2_). We will start by, for each $i\in[2]$, finding a large subset
$V^{\prime}_{i}\subset V_{i}$, so that $G[V_{i}^{\prime}]$ has an expansion
condition, for otherwise we will be done by the induction properties. Neither
of these properties will be necessarily strong enough to embed $T$. However,
if a vertex has $\Delta$ neighbours in both $V_{1}^{\prime}$ and
$V_{2}^{\prime}$ (this is Case I in the proof of Lemma 6.2), then this will
allow us to embed part of the tree in $G[V_{1}^{\prime}]$ and part of the tree
in $G[V_{2}^{\prime}]$ in such a way that they can be connected through this
vertex to get a copy of $T$. Thus, we can then assume that no such vertex
exists (Case II in the proof of Lemma 6.2). This will allow us to partition
$V(G)\setminus(V_{1}^{\prime}\cup V_{2}^{\prime})$ as $U_{1}\cup U_{2}$ so
that there are very few edges between $V_{1}^{\prime}$ and $U_{2}$ and very
few edges between $V_{2}^{\prime}$ and $U_{1}$. Assuming that $G$ contains no
copy of $T$, we then apply induction to find complete partite graphs in
$G^{c}[V_{1}^{\prime}\cup U_{1}]$ and $G^{c}[V_{2}^{\prime}\cup U_{2}]$ which
we can combine (with the deletion of some vertices from the larger parts) to
get a complete $k$-partite graph in $G^{c}$ with the class sizes we need.

######  Lemma 6.2.

Let $k\geq 3$ and $1/n\ll\lambda\ll\mu\ll 1/\Delta$. Let $m\leq\lambda n$ and
let $G$ be a graph with $(k-1)(n-1)+m$ vertices. Let $T$ be an $n$-vertex tree
with $\Delta(T)\leq\Delta$. Suppose the following hold.

  1. K1

For any $2\leq k^{\prime}\leq k-1$ and $m^{\prime}\leq\mu n$, $R(T,K_{\mu
n}^{k^{\prime}-1}\times K_{m^{\prime}}^{c})=(k^{\prime}-1)(n-1)+m^{\prime}$.

  2. K2

There is a partition $V(G)=V_{0}\cup V_{1}\cup V_{2}$ such that
$e_{G}(V_{1},V_{2})=0$, $|V_{1}|,|V_{2}|\geq m$ and $|V_{0}|\leq\lambda n$.

Then, $G$ contains a copy of $T$ or $G^{c}$ contains a copy of $K_{\lambda
n}^{k-1}\times K_{m}^{c}$.

###### Proof.

Assume for a contradiction that $G$ contains no copy of $T$ and $G^{c}$
contains no copy of $K_{\lambda n}^{k-1}\times K_{m}^{c}$. We start by showing
that we have the following property.

  1. K3

For every $U\subset V(G)$ with $|U|=m$, we have $|N_{G}(U)|\geq(1-2\lambda)n$.

Indeed, if there is some set $U\subset V(G)$ with $|U|=m$ with
$|N_{G}(U)|<(1-2\lambda)n$, then $|G-N_{G}(U)-U|>(k-2)(n-1)+\lambda n$, and
thus, by _K1_ , as $G-N_{G}(U)-U$ contains no copy of $T$, its complement
contains a copy of $K_{\lambda n}^{k-1}$. Adding $U$ as a vertex class, we
obtain a copy of $K_{\lambda n}^{k-1}\times K_{m}^{c}$ in $G^{c}$,
contradiction. Thus, K3 holds.

Now, let $d=4\Delta$ and consider the partition $V(G)=V_{0}\cup V_{1}\cup
V_{2}$ given by K2. For each $i\in[2]$ and any $U\subset V_{i}$ with size $m$,
we have $N_{G}(U)\subset V_{i}\cup V_{0}$, so that, by K3,
$|N_{G}(U,V_{i})|\geq(1-2\lambda)n-|V_{0}|\geq(1-3\lambda)n$. In particular,
$|V_{i}|\geq m+(1-3\lambda)n$. For each $i\in[2]$, then, letting
$n_{i}=|V_{i}|-(1-3\lambda)n$, we have that $G[V_{i}]$ is $(m,n_{i})$-joined
and, as $\lambda\ll 1/\Delta$ and $m\leq\lambda n$,

$|V_{i}|=n_{i}+(1-3\lambda)n\geq
n_{i}+\left(1-\frac{1}{4\Delta}\right)n+1+(4d+2)m+2m.$ (6.2)

In particular, $|V_{i}|\geq n_{i}+(4d+2)m$, so, by Proposition 2.6, there is
some $W_{i}\subset V_{i}$ with $|W_{i}|<m$ such that $G[V_{i}]-W_{i}$ is a
$(2d,m)$-expander. For each $i\in[2]$, let $V^{\prime}_{i}=V_{i}\setminus
W_{i}$.

We now consider 2 cases, depending on whether there is some $v\in
V(G)\setminus(V_{1}^{\prime}\cup V_{2}^{\prime})$ with at least $\Delta$
neighbours both in $V_{1}^{\prime}$ and in $V_{2}^{\prime}$ (Case I) or not
(Case II). In Case I, we will show that $G$ contains a copy of $T$, and in
Case II, we will show that $G^{c}$ contains a copy of $K_{\lambda
n}^{k-1}\times K_{m}^{c}$, a contradiction either way.

Case I. Suppose then that there is some vertex $v\in
V(G)\setminus(V_{1}^{\prime}\cup V_{2}^{\prime})$ with at least $\Delta$
neighbours both in $V_{1}^{\prime}$ and in $V_{2}^{\prime}$. Using Proposition
2.10, we can find two subtrees $T_{1}$ and $T_{2}$ of $T$ that share exactly
one vertex $t$ that is a leaf in $T_{1}$, such that $E(T)=E(T_{1})\cup
E(T_{2})$ and $n/4\Delta\leq|T_{2}|\leq n/2$. Let $t_{0}$ be the unique vertex
in $T_{1}$ adjacent to $t$ and let $t_{1},\ldots,t_{r}$ be the neighbours of
$t$ in $T_{2}$. For each $i\in[r]$, let $T^{\prime}_{i}$ be the tree in
$T_{2}-t$ containing $t_{i}$. Using that $v$ has at least $\Delta\geq r$
neighbours in $V_{1}^{\prime}$ and $V_{2}^{\prime}$, we can find a neighbour
$v_{0}$ of $v$ in $V_{1}^{\prime}$ and $r$ distinct neighbours
$v_{1},\ldots,v_{r}$ of $v$ in $V^{\prime}_{2}$.

Now, as $G[V_{1}]-W_{1}=G[V_{1}^{\prime}]$ is an $(m,n_{1})$-joined
$(2d,m)$-expander, we have that $I(\\{v_{0}\\})$ is $(d,m)$-extendable in
$G[V_{1}^{\prime}]$. Futhermore, as $|T_{1}|=n-|T_{2}|+1\leq(1-1/4\Delta)n+1$,
by (6.2), we have $|V_{1}^{\prime}|\geq|T_{1}|+(2d+2)m+n_{1}$. Thus, by
Corollary 2.19 there is a copy $S_{1}$ of $T_{1}-t$ in $G[V_{1}^{\prime}]$ in
which $t_{0}$ is copied to $v_{0}$.

Similarly, as $G[V_{2}]-W_{1}=G[V_{2}^{\prime}]$ is an $(m,n_{2})$-joined
$(2d,m)$-expander, we have that $I(\\{v_{1},\ldots,v_{r}\\})$ is
$(d,m)$-extendable in $G[V_{2}^{\prime}]$ as $r\leq\Delta=d/4$. Futhermore, as
$\sum_{i\in[r]}|T^{\prime}_{i}|=|T_{2}|-1\leq n/2$, by (6.2), we have
$|V_{2}^{\prime}|\geq r+\sum_{i\in[r]}|T^{\prime}_{i}|+(2d+2)m+n_{2}$. Thus,
by induction and Corollary 2.19, for each $j\in[r]$, there are vertex-disjoint
copies $S^{\prime}_{1},\ldots,S^{\prime}_{j}$ of
$T^{\prime}_{1},\ldots,T^{\prime}_{j}$, respectively, such that $t_{i}$ is
copied to $v_{i}$ for each $i\in[j]$, and
$I(\\{v_{1},\ldots,v_{r}\\})\cup(\cup_{i\in[j]}S_{i})$ is $(d,m)$-extendable
in $G[V_{2}^{\prime}]$. Note that at the end of the induction,
$S_{2}=\left(\cup_{i=1}^{r}S^{\prime}_{i}\right)$ is a copy of $T_{2}-t$ in
$G[V^{\prime}_{2}]$. Hence, $S_{1}\cup S_{2}$ together with the vertex $v$ and
edges $vv_{0},\ldots,vv_{r}$ form a copy of $T$ in $G$, contradiction.

Case II. Suppose, then, that we can partition
$V(G)\setminus(V_{1}^{\prime}\cup V_{2}^{\prime})$ as $U_{1}\cup U_{2}$ so
that every vertex in $U_{1}$ has fewer than $\Delta$ neighbours in
$V_{2}^{\prime}$ and every vertex in $U_{2}$ has fewer than $\Delta$
neighbours in $V_{1}^{\prime}$. For each $i\in[2]$, let $k_{i}$ and $m_{i}$ be
such that $|V_{i}^{\prime}\cup U_{i}|=k_{i}(n-1)+m_{i}$ and $0\leq m_{i}<n-1$.
Switching the labels if necessary, we can assume that $m_{1}\geq m_{2}$. Now,
as $V(G)=V_{1}^{\prime}\cup U_{1}\cup V_{2}^{\prime}\cup U_{2}$ is a
partition,

$(k-1)(n-1)+m=(k_{1}+k_{2})(n-1)+(m_{1}+m_{2}),$

and thus, we have that the following hold.

  * •

If $m_{1}+m_{2}<n-1$ then $k-1=k_{1}+k_{2}$ and $m=m_{1}+m_{2}$.

  * •

If $m_{2}<m$, then as $(k-1)(n-1)+(m-m_{2})=(k_{1}+k_{2})(n-1)+m_{1}$ and
$m_{1}<(n-1)$, we have $k-1=k_{1}+k_{2}$ and $m=m_{1}+m_{2}$.

  * •

$k_{1}+k_{2}\geq k-2$, so if $k_{1}+k_{2}\neq k-2$, then $k-1=k_{1}+k_{2}$,
and hence $m=m_{1}+m_{2}$.

Thus, we either have $m_{1}\geq(n-1)/2$, $m_{2}\geq m$ and $k_{1}+k_{2}=k-2$
(Case II.1) or $k-1=k_{1}+k_{2}$ and $m=m_{1}+m_{2}$ (Case II.2). Futhermore,
as $|V_{i}^{\prime}|\geq|V_{i}|-m\geq(1-3\lambda)n$ for each $i\in[2]$, we
have that $k_{1},k_{2}<k-1$.

Case II.1: $m_{1}\geq(n-1)/2$, $m_{2}\geq m$ and $k_{1}+k_{2}=k-2$. As
$k_{1}<k-1$ and $m_{1}\geq n/3$, by _K1_ , we have that $V_{1}^{\prime}\cup
U_{1}$ contains disjoint sets $Y_{1},\ldots,Y_{k_{1}+1}$ with $|Y_{i}|=\mu n$
for each $i\in[k_{1}+1]$, and there are no edges in $G$ between any pair
$Y_{i}$ and $Y_{j}$ for each $1\leq i<j\leq k_{1}+1$. Furthermore, as
$k_{2}<k-1$ and $m_{2}\geq m$, by _K1_ , we have that $V_{2}^{\prime}\cup
U_{2}$ contains disjoint sets $Z_{1},\ldots,Z_{k_{2}+1}$ with $|Z_{i}|=\mu n$
for each $i\in[k_{2}]$ and $|Z_{k_{2}+1}|=m$ so that there are no edges in $G$
between any pair $Z_{i}$ and $Z_{j}$ for $1\leq i<j\leq k_{2}+1$.

Note that

$|U_{1}\cup(N(Z_{k_{2}+1})\cap
V_{1}^{\prime})|\leq|V_{0}|+|W_{1}|+|W_{2}|+(\Delta-1)|Z_{k_{2}+1}|\leq\lambda
n+2m+\Delta m\leq\mu n/2.$ (6.3)

Hence, we can find $Y^{\prime}_{i}\subset
Y_{i}\setminus(U_{1}\cup(N(Z_{k_{2}+1})\cap V_{1}^{\prime}))$ with size
$\lambda n$ for each $i\in[k_{1}+1]$. Similarly, since
$|U_{2}|\leq|V_{0}|+|W_{1}|+|W_{2}|\leq\lambda n+2m\leq\mu n/2$, we can find
$Z_{i}^{\prime}\subset Z_{i}\setminus U_{2}$ having size $\lambda n$ for each
$i\in[k_{2}]$. Let $Z_{k_{2}+1}^{\prime}=Z_{k_{2}+1}$, and observe that there
no edges in $G$ between any of the sets

$Y_{1}^{\prime},Y_{2}^{\prime},\ldots,Y_{k_{1}+1}^{\prime},Z^{\prime}_{1},Z_{2}^{\prime},\ldots,Z^{\prime}_{k_{2}+1},$

and these are $k_{1}+k_{2}+1=k-1$ sets with size $\lambda n$ and 1 set of size
$m$, so that $G^{c}$ contains a copy of $K_{\lambda n}^{k-1}\times K_{m}^{c}$,
contradiction.

Case II.2: $m_{1}+m_{2}=m$ and $k_{1}+k_{2}=k-1$. As $k_{1}<k-1$, by _K1_ , we
have that $V_{1}^{\prime}\cup U_{1}$ contains disjoint sets
$Y_{1},\ldots,Y_{k_{1}+1}$ with $|Y_{i}|=\mu n$ for each $i\in[k_{1}]$, and
$|Y_{k_{1}+1}|=m_{1}$, such that there are no edges in $G$ between any pair
$Y_{i}$ and $Y_{j}$ for each $1\leq i<j\leq k_{1}+1$. Similarly, by _K1_ , we
have that $V_{2}^{\prime}\cup U_{2}$ contains disjoint sets
$Z_{1},\ldots,Z_{k_{2}+1}$ with $|Z_{i}|=\mu n$ for each $i\in[k_{2}]$ and
$|Z_{k_{2}+1}|=m_{2}$, such that there are no edges in $G$ between any pair
$Z_{i}$ and $Z_{j}$ for each $1\leq i<j\leq k_{2}+1$. For each $i\in[k_{1}]$,
using a similar calculation to (6.3), let $Y^{\prime}_{i}\subset
Y_{i}\setminus(U_{1}\cup(N(Z_{k_{2}+1})\cap V_{1}^{\prime}))$ have size
$\lambda n$ and let $Y^{\prime}_{k_{1}+1}=Y_{k_{1}+1}$. For each
$i\in[k_{2}]$, again using a similar calculation to (6.3), let
$Z_{i}^{\prime}\subset Z_{i}\setminus(U_{2}\cup(N(Y_{k_{1}+1})\cap
V_{2}^{\prime}))$ have size $\lambda n$, and let
$Z_{k_{2}+1}^{\prime}=Z_{k_{2}+1}$. Then, observe that there no edges in $G$
between any of the sets

$Y_{1}^{\prime},Y_{2}^{\prime},\ldots,Y_{k_{1}}^{\prime},Z^{\prime}_{1},Z_{2}^{\prime},\ldots,Z^{\prime}_{k_{2}},Y^{\prime}_{k_{1}+1}\cup
Z^{\prime}_{k_{2}+1},$

and these are $k_{1}+k_{2}=k-1$ sets with size $\lambda n$ and 1 set of size
$m_{1}+m_{2}=m$, so that $G^{c}$ contains a copy of $K_{\lambda n}^{k-1}\times
K_{m}^{c}$, a contradiction. ∎

###  6.3 Trees with few leaves in well-connected graphs

For the last case in the induction step for Theorem 2.1, which we prove as
Lemma 6.3, we will have that the graph $G$ is well-connected, in that it has
no partition $V(G)=V_{0}\cup V_{1}\cup V_{2}$ satisfying _K2_ (see __L1__), as
well as an additional expansion condition which will follow from our induction
(see __L2__), and the tree $T$ will have few leaves. That is, we prove the
following lemma.

######  Lemma 6.3.

Let $k\geq 3$ and $1/n\ll\varepsilon\ll\lambda\ll 1/\Delta,1/k$. Let
$m\leq\varepsilon n$ and let $G$ be a graph with $(k-1)(n-1)+m$ vertices. Let
$T$ be an $n$-vertex tree with fewer than $10\Delta^{2}\varepsilon n$ leaves
satisfying $\Delta(T)\leq\Delta$. Suppose the following properties hold.

  1. _L1_

There is no partition $V(G)=V_{0}\cup V_{1}\cup V_{2}$ such that
$e_{G}(V_{1},V_{2})=0$, $|V_{1}|,|V_{2}|\geq m$ and $|V_{0}|\leq\lambda n$.

  2. _L2_

For every set $U\subset V(G)$ with $|U|=m$, we have
$|N_{G}(U)|\geq(1-\lambda)n$.

Then, $G$ contains a copy of $T$ or $G^{c}$ contains a copy of
$K^{k-1}_{\varepsilon n}\times K_{m}^{c}$.

The property __L1__ will imply that any two disjoint sets $U$ and
$U^{\prime}\subset V(G)$, each with size $m$, will have many vertex-disjoint
short paths between them in $G$. If we pick a small but linear-sized (in $n$)
random set $Z\subset V(G)$, then for any pair of such sets $U$ and
$U^{\prime}$, plenty of these paths all have internal vertices in $Z$. This we
prove as Proposition 6.5, where we do a little additional work so that the
paths we can find all have the same prescribed length.

In Lemma 6.3, we have that $k\geq 3$, so that $G$ contains many more vertices
than $T$. As $T$ has few leaves, most of $T$ will consist of bare paths (paths
whose internal vertices have degree 2 in the tree $T$) of some long, constant,
length. We will choose a random partition $V(G)=Z\cup V_{0}\cup V_{1}$, with
$|V_{0}|\geq(1-o(1))\cdot 2n/5$, $|V_{1}|\geq 11n/10$ and so that $Z$ has the
connection property described above. We then embed the tree $T$ steadily into
a large subgraph of $G[V_{0}]$, but, at any available opportunity, try to save
vertices from $V_{0}$ by embedding a long bare path of $T$ using many vertices
in $V_{1}$ and at most a small number of vertices from $Z$, so that only the
last vertex embedded is in $V_{0}$ (see Figure 2). We do this so that the
embedded tree remains extendable in the large subgraph of $G[V_{0}]$ that we
use. After this embedding (described precisely in a)–c) of the proof of Lemma
6.3), we analyse it and show that enough of the long bare paths are embedded
outside of $V_{0}$ so that we do not run out of room within $V_{0}$, and thus
can successfully embed $T$. This is shown in Claims 6.7–6.9, but, roughly
speaking, if we had $2m$ opportunities to embed a long path in $T$ and did not
do so outside of $V_{0}$, then let $U$ be the set of vertices to which we
could have attached a long bare path to extend the embedding of $T$, and do
the following. We find vertex-disjoint long paths $Q_{1},\ldots,Q_{2m}$ in $G$
using vertices in $V_{1}$ which have not yet been used in the embedding, and
show that under our embedding rules we should have embedded one of the paths
$Q_{i}$ connected to a vertex in $U$ using the connectivity property of $Z$.
To find the paths $Q_{1},\ldots,Q_{2m}$, we only need a loose result for the
Ramsey numbers of paths versus general graphs as the paths have constant
length compared to $n$, but for convenience we will use the following result.

######  Theorem 6.4 (Pokrovskiy and Sudakov [23]).

Let $k\geq 2$ and let $H$ be a graph with $\chi(H)=k$. Then, for all $n\geq
4|H|$, $R(P_{n},H)=(k-1)(n-1)+\sigma(H)$.

$V_{0}^{\prime}$$Z$$X$$V_{1}$$v_{1}$ Figure 2: The embedding of $T$ in the
proof of Lemma 6.3. Starting with the extendable subgraph $I(X)$ in
$G[V_{0}]$, in which a vertex of $T$ is embedded to $v_{1}$, we steadily embed
$T$ into $G$ so that many of the long bare paths use vertices in $V_{1}$ along
with some vertices in $Z$ to connect the path back into $G[V_{0}]$ (the grey
paths depicted have all their interior vertices in $Z$), and so that the union
of $I(X)$ and the subgraph embedded in $V_{0}^{\prime}$ remains extendable.

We now prove a result showing that, in the above sketch, the random set $Z$ is
likely to have the connectivity property we want.

######  Proposition 6.5.

Let $k\geq 3$ and $1/n\ll\delta\ll 1/\ell\ll\lambda\ll 1/k$. Let $m\leq\delta
n$ and let $G$ be a graph with $(k-1)(n-1)+m$ vertices such that _L1_ holds
and $G^{c}$ contains no $K_{\delta n}^{k}$. Let $Z\subset V(G)$ be a set
formed by including each element independently at random with probability
$1/5$.

Then, with probability more than $2/3$, for any two disjoint sets
$U,U^{\prime}\subset V(G)$ with size $m$, there are at least $\delta n$
internally vertex-disjoint paths with length $\ell$ through $Z$ connecting $U$
and $U^{\prime}$ in $G$.

###### Proof.

First, let $U,U^{\prime}\subset V(G)$ be disjoint sets and let $Z_{0}\subset
V(G)\setminus(U\cup U^{\prime})$ satisfy $|U|=|U^{\prime}|=m$ and
$|Z_{0}|<\lambda n/2$. We will show that there is a path from $U$ to
$U^{\prime}$ with interior vertices not in $Z_{0}\cup U\cup U^{\prime}$, and
with length at least $2$ and at most $\ell$.

Let $r=\lfloor\ell/2\rfloor$. Let $U_{0}=U$ and, iteratively, for each $1\leq
i\leq r$, let $U_{i}=U_{i-1}\cup N_{G-Z_{0}-U^{\prime}}(U_{i-1})$. Now, the
sets $U_{i}\setminus U_{i-1}$, $i\in[r]$, are disjoint, so there must be some
$j\in[r]$ with $|U_{j}\setminus U_{j-1}|\leq kn/r<\lambda n/2-m$, as
$1/\ell\ll\lambda,1/k$ and $m\leq\delta n\leq\lambda n/4$. Then, $|Z_{0}\cup
U^{\prime}\cup(U_{j}\setminus U_{j-1})|<\lambda n$, $|U_{j-1}|\geq|U_{0}|=m$,
and there are no edges in $G$ between $U_{j-1}$ and $V(G)\setminus(Z_{0}\cup
U^{\prime}\cup U_{j})$, so by __L1__ we must have $|V(G)\setminus(Z_{0}\cup
U^{\prime}\cup U_{j})|<m$. Thus $|U_{j}|\geq|G|-|Z_{0}|-2m\geq|G|-\lambda
n/2-2m>|G|/2$, and therefore $|U_{r}|\geq|U_{j}|>|G|/2$.

Similarly, letting $U_{0}^{\prime}=U^{\prime}$ and iteratively taking
$U^{\prime}_{i}=U^{\prime}_{i-1}\cup N_{G-Z_{0}-U}(U^{\prime}_{i-1})$ for each
$1\leq i\leq r$, we have that $|U^{\prime}_{r}|>|G|/2$. Thus, $U_{r}\cap
U^{\prime}_{r}\neq\emptyset$, and therefore there is a path from $U$ to
$U^{\prime}$ with length at least 2 and at most $\ell$ in $G-Z_{0}$.

Thus, by taking $Z_{0}$ to be the internal vertices of a set of maximal
internally-vertex-disjoint paths from $U$ to $U^{\prime}$ in $G$ with length
at least $2$ and at most $\ell$, we see that $G$ contains at least $\lambda
n/3\ell$ internally-vertex-disjoint paths from $U$ to $U^{\prime}$ with length
at most $\ell$ and at least 2. Let $2\leq j\leq\ell$ be maximal subject to the
condition that there are at least $r_{j}:=\lambda n/3^{j}\ell$ internally-
vertex-disjoint paths from $U$ to $U^{\prime}$ with length $j$. Such a $j$
exists as $\sum_{j=2}^{\ell}r_{j}<\lambda n/3\ell$. If $j<\ell$, then let
$P_{1},\ldots,P_{r_{j}}$ be such a set of paths, and, for each $i\in[j]$, let
$x_{i}$ be the vertex of the path neighbouring the end-vertex in $U$ (which is
not in $U^{\prime}$ as $j\geq 2$). Note that if $G[\\{x_{i}:i\in[r_{j}]\\}]$
contains a matching with $r_{j+1}$ edges, then we can use this matching along
with $P_{1},\ldots,P_{r_{j}}$ to get $r_{j+1}$ internally-vertex-disjoint
paths from $U$ to $U^{\prime}$ in $G$ with length $j+1$, a contradiction. On
the other hand, if $G[\\{x_{i}:i\in[r_{j}]\\}]$ contains no matching with
$r_{j+1}$ edges, then, removing a maximal matching shows that
$G^{c}[\\{x_{i}:i\in[r_{j}]\\}]$, and hence $G^{c}$, contains a copy of
$K_{r_{j}-2r_{j+1}}$, and hence a copy of $K^{k}_{\delta n}$ as $\delta\ll
1/\ell,\lambda$, contradiction. Thus, we must have $j=\ell$.

Therefore, altogether, we have shown that, for any disjoint sets
$U,U^{\prime}\subset V(G)$ of size $m$, there are at least $\lambda
n/3^{\ell}\ell$ internally-vertex-disjoint paths from $U$ to $U^{\prime}$ with
length $\ell$. For any such path, the probability all its internal vertices
lie in $Z$ is $(1/5)^{\ell-1}$. Thus, as $\delta\ll\lambda,\ell$, by Lemma
2.20, the probability that there are fewer than $\delta n$ internally vertex-
disjoint paths with length $\ell$ through $Z$ connecting $U$ and $U^{\prime}$
in $G$ is at most $2\exp(-\lambda n/15^{\ell+1}\ell)$. Therefore, the
probability there are disjoint sets $U,U^{\prime}\subset V(G)$ of size $m$,
with fewer than $\delta n$ internally-vertex-disjoint paths from $U$ to
$U^{\prime}$ with length $\ell$ and internal vertices in $Z$ is at most

$\binom{kn}{m}^{2}\cdot 2\exp\left(-\frac{\lambda
n}{15^{\ell+1}\ell}\right)\leq\left(\frac{ekn}{m}\right)^{2m}\cdot
2\exp\left(-\frac{\lambda
n}{15^{\ell+1}\ell}\right)\leq\left(\frac{ek}{\delta}\right)^{2\delta n}\cdot
2\exp\left(-\frac{\lambda n}{15^{\ell+1}\ell}\right)<1/3,$

as required, where the last inequality follows as $1/n\ll\delta\ll\ell,1/k$. ∎

Next, we give a simple result to show that, in the sketch above, the set
$V_{0}$ will have the expansion property in $G$ that we want.

######  Proposition 6.6.

Let $k\geq 3$ and $1/n\ll\lambda\ll 1/k$. Let $m\leq\lambda n$ and let $G$ be
a graph with $(k-1)(n-1)+m$ vertices in which _L2_ holds. Let $V_{0}\subset
V(G)$ be a set formed by including each element independently at random with
probability $1/5$. Then, with probability more than $2/3$, for any set
$U\subset V(G)$ with $|U|=m$, $|N_{G}(U,V_{0})|\geq n/10$.

###### Proof.

For each set $U\subset V(G)$ with $|U|=m$, we have, by __L2__ , that
$\mathbb{E}|N_{G}(U,V_{0})|\geq n/6$. Thus, by Lemma 2.20, the probability
that there is some set $U\subset V(G)$ with $|U|=m$ and
$|N_{G}(U,V_{0})|<n/10$ is at most

$\binom{kn}{m}\cdot
2\exp\left(-\frac{n}{10^{3}}\right)\leq\left(\frac{ekn}{m}\right)^{m}\cdot
2\exp\left(-\frac{n}{10^{3}}\right)\leq\left(\frac{ek}{\lambda}\right)^{\lambda
n}\cdot 2\exp\left(-\frac{n}{10^{3}}\right)<\frac{1}{3},$

as required, where we have used that $1/n\ll\lambda\ll 1/k$. ∎

Using Propositions 6.5 and 6.6, we can now prove Lemma 6.3 using the sketch
above, as depicted in Figure 2.

###### Proof of Lemma 6.3.

Let $L$, $\delta$ and $\ell$ satisfy $\varepsilon\ll 1/L\ll\delta\ll
1/\ell\ll\lambda$, and let $d=4\Delta$. Let $V(G)=Z\cup V_{0}\cup V_{1}$ be a
partition chosen by selecting the set for each $v\in V(G)$ independently at
random so that $\mathbb{P}(v\in Z)=\mathbb{P}(v\in V_{0})=1/5$ and
$\mathbb{P}(v\in V_{1})=3/5$.

By a simple application of Lemma 2.20, as $|G|\geq 2n-1$ we have that, with
probability greater than $2/3$, $|V_{1}|\geq 11n/10$. Therefore, by __L1__ and
__L2__ , using Propositions 6.5 and 6.6, we can take a choice of partition
$V(G)=W\cup V_{0}\cup V_{1}$ for which the following hold.

  1. M1

$|V_{1}|\geq 11n/10$.

  2. M2

For every pair of vertex disjoint sets $U_{1},U_{2}\subset V(G)$ with size
$m$, there are at least $\delta n$ internally vertex disjoint paths from
$U_{1}$ to $U_{2}$ with length $\ell$ through $Z$.

  3. M3

For each $U\subset V(G)$ with $|U|=m$, $|N(U,V_{0})|\geq n/10$.

Now, let $X_{0}\subset V_{0}$ have size $n/20$ (possible by M3), and note
that, by M3, for each $U\subset V(G)$ with $|U|=m$, $|N(U,V_{0}\setminus
X_{0})|\geq n/20$. Then, similarly to the proof of Proposition 2.13, there is
a set $W\subset V(G)$ with $|W|<m$ such that, for each $U\subset V(G)\setminus
W$ with $|U|\leq m$, $|N_{G}(U,V_{0}\setminus(X_{0}\cup W)|\geq 3d|U|$. Let
$V_{0}^{\prime}=V_{0}\setminus W$ and $X=X_{0}\setminus W$. Then, by
Proposition 2.15, we have that $I(X)$ is $(d,m)$-extendable in
$G[V_{0}^{\prime}]$. Let $n_{0}=|V_{0}^{\prime}|-n/10$, and note that
$G[V_{0}^{\prime}]$ is $(m,n_{0})$-joined by M3 and

$|V_{0}^{\prime}|=n_{0}+n/10\geq n_{0}+|X|+(2d+2)m+n/40.$ (6.4)

Now, take $T$ and arbitrarily select a leaf $t_{1}$ of $T$. For each
$i=2,\ldots,n$ in turn, if possible let $t_{i}$ be a neighbour of $t_{i-1}$ in
$T$ which is not in $\\{t_{1},\ldots,t_{i-2}\\}$, and otherwise, let $t_{i}$
be any vertex of $T$ not in $\\{t_{1},\ldots,t_{i-2}\\}$ with a neighbour in
$\\{t_{1},\ldots,t_{i-2}\\}$. For each $2\leq i\leq n$, let $s_{i}$ be the
neighbour of $t_{i}$ in $T[\\{t_{1},\ldots,t_{i-1}\\}]$. We will build the
embedding $\phi$ of $T$ by embedding $t_{1},t_{2},\ldots,t_{n}$ in this order.
To initialise, set $I_{a}=\\{1\\},I_{b}=\emptyset$ and $\phi(t_{1})=v_{1}$ for
an arbitrary vertex $v_{1}\in X$. Then, beginning with $j=2$, carry out the
process whose step $j$ is as follows.

  1. a)

If $j\leq n-L$ and $t_{j},\ldots,t_{j+L}$ all have degree 2 in $T$, and there
is some $v_{j+L}\in X\setminus\phi(\\{t_{1},\ldots,t_{j-1}\\})$ for which
there is a $\phi(s_{j}),v_{j+L}$-path $\phi(s_{j})v_{j}\ldots v_{j+L}$ in $G$
with internal vertices not in $V_{0}\cup\phi(\\{t_{1},\ldots,t_{j-1}\\})$ and
at most $2\ell$ vertices in $Z$, then let $\phi(t_{i})=v_{i}$ for each $j\leq
i\leq j+L$, and add $j+L$ to $I_{a}$.

If $j+L=n$ then stop, otherwise proceed to step $j+L+1$.

  2. b)

Otherwise, if $s_{j}$ satisfies $\phi(s_{j})\in V_{0}^{\prime}$, and there is
some $v_{j}\in V_{0}^{\prime}\setminus(X\cup\\{t_{1},\ldots,t_{j-1}\\})$ such
that $I(X)\cup\phi(T[\\{t_{i}:i\in I_{a}\cup I_{b}\\}])+\phi(s_{j})v_{j}$ is
$(d,m)$-extendable in $G[V^{\prime}_{0}]$, then let $\phi(t_{j})=v_{j}$ and
add $j$ to $I_{b}$.

If $j=n$, then stop, otherwise proceed to step $j+1$.

  3. c)

If neither of these cases occur, then stop.

Assume we are at the start of step $j$ of this process, note the following. If
$j\leq n-L$ and $t_{j},\ldots,t_{j+L}$ all have degree 2 in $T$, then by the
ordering of the vertices in $T$, we have that $T[\\{t_{j},\ldots,t_{j+L}\\}]$
is a path with length $L$. Also, $I_{a}$ is the set of indices $i\in[j-1]$
such that $\phi(t_{i})\in X$, $I_{b}$ is the set of indices $i\in[j-1]$ such
that $\phi(t_{i})\in V^{\prime}_{0}\setminus X$, and, if $i\in[j-1]$ and
$t_{i}$ is adjacent to some $t_{j^{\prime}}\in V(T)$ with $j^{\prime}\geq j$,
then $\phi(t_{i})\in V^{\prime}_{0}$ and $i\in I_{a}\cup I_{b}$. We now
further analyse this process via the following three claims and show that it
will only stop at a step $j$ if $j+L=n$ or $j=n$, and that, in either case,
this implies that we have embedded a copy of $T$ in $G$.

######  Claim 6.7.

If the process stops at step $j$ with $j\neq n$ and $j+L\neq n$, then
$|I_{b}|\geq n/50$.

###### Proof of Claim 6.7.

Suppose for a contradiction, that $|I_{b}|<n/50$. From the observations above,
we have $\phi(s_{j})\in V^{\prime}_{0}$. Furthermore, using
$|I(X)\cup\phi(T[\\{t_{i}:i\in I_{a}\cup I_{b}\\}])|=|X|+|I_{b}|$ and (6.4),
we have

$|V^{\prime}_{0}|\geq|I(X)\cup\phi(T[\\{t_{i}:i\in I_{a}\cup
I_{b}\\}])|+(2d+2)m+n_{0}+1.$

As $I(X)\cup\phi(T[\\{t_{i}:i\in I_{a}\cup I_{b}\\}])$ is $(d,m)$-extendable
in $G[V^{\prime}_{0}]$, which is $(m,n_{0})$-joined, and the degree of
$\phi(s_{i})$ is at most $\Delta-1$ in $I(X)\cup\phi(T[\\{t_{i}:i\in I_{a}\cup
I_{b}\\}])$, by Lemma 2.16, there is $v_{j}\in
V_{0}^{\prime}\setminus(X\cup\\{t_{1},\ldots,t_{j-1}\\})$ adjacent to
$\phi(s_{i})$, such that $I(X)\cup\phi(T[\\{t_{i}:i\in I_{a}\cup
I_{b}\\}])+\phi(s_{j})v_{j}$ is $(d,m)$-extendable in $G[V_{0}^{\prime}]$.
This contradicts that the process stopped at step $j$ as we could have carried
out b). ∎

######  Claim 6.8.

$|X\cap\phi(\\{t_{1},\ldots,t_{j-1}\\})|\leq n/100$ and
$|Z\cap\phi(\\{t_{1},\ldots,t_{j-1}\\})|<\delta n/4$.

###### Proof of Claim 6.8.

Note that, for each $j\geq 2$, $\phi(t_{j})\in X$ only if step $j-L$ is
carried out via part a), and exactly 1 vertex is embedded into $X$ in this
step. Thus, $|X\cap\phi(\\{t_{1},\ldots,t_{j-1}\\})|\leq 1+(n-1)/L\leq n/100$.
Similarly, the only vertices embedded into $Z$ are embedded via part a), where
at most $2\ell$ vertices are used each step. Thus,
$|Z\cap\phi(\\{t_{1},\ldots,t_{j-1}\\})|\leq 2\ell(n-1)/L<\delta n/4$. ∎

######  Claim 6.9.

If $|I_{b}|\geq n/50$, then there are vertex disjoint sets $U_{1},U_{2}\subset
V^{\prime}_{0}$ with size $m$ such that there is no path in $G$ from $U_{1}$
to $U_{2}$ of length $L$ with internal vertices not in
$V^{\prime}_{0}\cup\phi(\\{t_{1},\ldots,t_{j-1}\\})$ and at most $2\ell$
vertices in $Z$.

###### Proof of Claim 6.9.

Suppose $|I_{b}|\geq n/50$. Let $J\subset I_{b}$ be the set of $j\in I_{b}$
such that $t_{j},\ldots,t_{j+L}$ all have degree 2 in $T$. Suppose for a
contradiction that $|J|<|I_{b}|/2$. For each $j\in J\setminus I_{b}$, there is
some $j\leq i\leq{j+L}$ such that $t_{i}$ either has degree 1 or degree at
least 3 in $T$, so in total there are at least $|I_{b}|/2(L+1)\geq n/100(L+1)$
such indices $i$. As $T$ has at most $10\Delta^{2}\varepsilon n$ leaves and
$\varepsilon\ll 1/L$, $T$ must then have fewer leaves than vertices with
degree at least 3. However,

$2(n-1)=2e(T)=\sum_{i\in[n]}d_{T}(t_{i})\geq|\\{i:d_{T}(t_{i})=1\\}|+2(n-|\\{i:d_{T}(t_{i})=1\\}|)+|\\{i:d_{T}(t_{i})\geq
3\\}|,$

so it follows that $T$ has at least as many leaves as vertices with degree at
least 3, contradiction. Thus, $|J|\geq|I_{b}|/2\geq n/100\geq\Delta m$.