# Extremal density for subdivisions with length or sparsity constraints

Jaehoon Kim Department of Mathematical Science, KAIST, South Korea. Email:
<EMAIL_ADDRESS>Supported by the Fulbright Visiting Scholar
Fellowship and by the National Research Foundation of Korea (NRF) grant funded
by the Korean government(MSIT) No. RS-2023-00210430.  Hong Liu Extremal
Combinatorics and Probability Group (ECOPRO), Institute for Basic Science
(IBS), Daejeon, South Korea. Email<EMAIL_ADDRESS>Supported by
IBS-R029-C4. Yantao Tang Zhongtai Securities Institute for Financial Studies,
Shandong University, Jinan, Shandong, China. Email<EMAIL_ADDRESS>Guanghui Wang School of Mathematics, Shandong University, Jinan, Shandong,
China. Email<EMAIL_ADDRESS>GW is supported by National Key R&D
Program of China (2023YFA1009603), by Young Taishan Scholar program of
Shandong Province (201909001) and by Natural Science Foundation of China
(11871311). DY is supported by Natural Science Foundation of China (12101365)
and by Natural Science Foundation of Shandong Province (ZR2021QA029). Donglei
Yang44footnotemark: 4 Fan Yang Data Science Institute, Shandong University,
Jinan, Shandong, China. Email<EMAIL_ADDRESS>Supported by Natural Science
Foundation of China (12301447) and by China Postdoctoral Science Foundation
(12570073310023).

###### Abstract

Given a graph $H$, a balanced subdivision of $H$ is obtained by replacing all
edges of $H$ with internally disjoint paths of the same length. In this paper,
we prove that for any graph $H$, a linear-in-$e(H)$ bound on average degree
guarantees a balanced $H$-subdivision. This strengthens an old result of
Bollobás and Thomason, and resolves a question of Gil-Fernández, Hyde, Liu,
Pikhurko and Wu.

We observe that this linear bound on average degree is best possible whenever
$H$ is logarithmically dense. We further show that this logarithmic density is
the critical threshold: for many graphs $H$ below this density, its
subdivisions are forcible by a sublinear bound in $e(H)$ on average degree. We
provide such examples by proving that the subdivisions of any almost bipartite
graph $H$ with sublogarithmic density are forcible by a sublinear-in-$e(H)$
bound on average degree, provided that $H$ satisfies some additional
separability condition.

##  1 Introduction

For a graph $H$, a _subdivision_ of $H$, denoted by $TH$, is a graph obtained
by replacing edges of $H$ by internally vertex-disjoint paths. This is a
fundamental concept for studying topological and structural aspects of graphs
as a subdivision of $H$ has the same topological structure as $H$. For
example, the celebrated theorem of Kuratowski [32] in 1930 used this notion to
characterize the planar graphs, proving that a graph is planar if and only if
it contains no $K_{5}$ or $K_{3,3}$ as a subdivision.

A well-studied direction of research is to find sufficient conditions on a
graph $G$ that would guarantee the existence of an $H$-subdivision in $G$. For
instance, condition on chromatic number was proposed by Hajós, who conjectured
in 1961 a strengthening of Hadwiger’s conjecture that every graph $G$ with
chromatic number $\chi(G)\geq t$ contains a $TK_{t}$. Dirac [9] showed that
this conjecture is true for $t\leq 4$, but in 1979 Catlin [6] disproved the
conjecture for all $t\geq 7$. Later, Erdős and Fajtlowicz [14] showed that the
conjecture is false for almost all graphs by considering random graphs, see
also [29, 31] for more recent developments. As a stronger and more fundamental
question, conditions on average degree guaranteeing an $H$-subdivision have
been extensively studied, starting from a result of Mader [37] from 1967. He
showed that large but constant average degree implies a large clique
subdivision. More precisely, for every $k\in\mathbb{N}$, there exists (finite)
$f(k)$ such that every graph $G$ with average degree at least $f(k)$ contains
a $TK_{k}$. Mader furthermore conjectured that one can take $f(k)=O(k^{2})$.
This conjecture was finally resolved in the 90s by Bollobás and Thomason [5]
and independently by Komlós and Szemerédi [25]. Jung [21] observed that
$K_{k^{2}/10,k^{2}/10}$ does not contain $TK_{k}$, hence the quadratic bound
on $f(k)$ is optimal.

As this example implies that the quadratic bound is best possible, the
following stability-type question naturally arises. Can we find a larger
clique subdivision in $G$ if it does not structurally look like (disjoint
union of) dense bipartite graph? One way to formalize this question was
suggested by Mader [39], conjecturing that the quadratic bound can be improved
to a linear one; that is, every $C_{4}$-free graph $G$ with average degree
$d(G)=\Omega(k)$ contains a $TK_{k}$. After some partial results (see e.g. [3,
29, 31]), this conjecture was resolved by Liu and Montgomery [34]. In fact,
they proved a stronger statement that for every $t\geq s\geq 2$, there exists
a constant $c=c(s,t)$ such that if $G$ is $K_{s,t}$-free with $d(G)=d$, then
$G$ contains a $TK_{cd^{\frac{s}{2(s-1)}}}$. Another way to formalize the
question was suggested by Liu and Montgomery [34]. Observing that the disjoint
union of dense bipartite graphs has a small size subgraph with almost same
average degree, Liu and Montgomery conjectured that if a graph $G$ has
$\omega(k^{2})$ vertices and has no small induced subgraphs with almost same
average degree as the entire graph, then $o(k^{2})$-average degree yields a
$TK_{k}$. This conjecture was resolved by Im, Kim, Kim and Liu [20] using the
notion of ‘crux’ measuring the size of smallest subgraph with almost same
average degree.

###  1.1 Balanced subdivisions

Recent trends have been focusing on the existence of subdivisions with length
constraints. In particular, a subdivision of $H$ is _balanced_ if each edge of
$H$ is subdivided the same number of times. For $\ell\in\mathbb{N}$, denote by
$TH^{(\ell)}$ a balanced subdivision of $H$ where each edge of $H$ is
subdivided $\ell$ times. For dense graphs, an old conjecture of Erdős [13]
states that for every $\varepsilon>0$, there exists $\delta>0$ such that every
graph with $n$ vertices and at least $\varepsilon n^{2}$ edges contains a
$TK_{\delta\sqrt{n}}^{(1)}$. Alon, Krivelevich and Sudakov [2] confirmed the
conjecture with $\delta=\varepsilon^{\frac{3}{2}}$, and this result was
improved to $\delta=\varepsilon$ by Fox and Sudakov [15]. In the sparse
regime, Thomassen [43] in the 80s conjectured a strenghening of Mader’s result
[37] that large constant average degree suffices to force a large balanced
clique subdivision: for each $k\in\mathbb{N}$, there exists some $g(k)$ such
that every graph $G$ with $d(G)\geq g(k)$ contains a $TK^{(\ell)}_{k}$ for
some $\ell\in\mathbb{N}$. Very recently, Thomassen’s conjecture was resolved
in the positive by Liu and Montgomery [35]. Wang [44] later gave a
quantitative improvment, showing that one can take $g(k)=k^{2+o(1)}$. Finally,
the optimal quadratic bound $g(k)=O(k^{2})$ forcing balanced clique
subdivision was proved by Luan, Tang, Wang and Yang [36] and independently by
Gil-Fernández, Hyde, Liu, Pikhurko and Wu [16]. In [36], the result of [34]
was also strengthened to a balanced version, i.e. every $C_{4}$-free graph
contains a balanced clique subdivision of order linear in its average degree.

In this paper, we focus on forcing $H$-subdivisions for general graphs $H$.
Bollobás and Thomason [4] proved a nice structural result that highly
connected graphs are highly linked. Their result, together with Mader’s result
[38] on subgraphs with high connectivity, implies that for any graph $H$ with
no isolated vertices, every graph with average degree at least $100e(H)$
contains a subdivision of $H$. Note that when $H$ is a clique, the linear-
in-$e(H)$ bound recovers the quadratic bound in [5, 25]. However, the
structural linkage approach in [4] fails to provide any control on how edges
in $H$ are subdivided. Gil-Fernández, Hyde, Liu, Pikhurko and Wu [16] raised
the problem of whether the same linear bound $O(e(H))$ suffices to force a
balanced $H$-subdivision.

######  Problem A ([16]).

Does there exist a constant $C$ such that for any $H$ without isolated
vertices, if a graph $G$ has average degree at least $C\cdot e(H)$, then $G$
contains a balanced subdivision of $H$?

Our first result answers Problem A in the affirmative.

######  Theorem 1.1.

There exists a constant $C>0$ such that for any $H$ with no isolated vertices,
if $G$ is a graph with average degree $d(G)\geq C\cdot e(H)$, then $G$
contains a $TH^{(\ell)}$ for some $\ell\in\mathbb{N}$.

###  1.2 When a sublinear bound suffices?

Recall that the observation of Jung [21] shows that the linear-in-$e(H)$ bound
is optimal when $H$ is a clique. It is a natural problem to study when a
sublinear bound suffices to ensure an $H$-subdivision. A specific question of
this sort was proposed by Wood from the Barbados workshop in 2020.

######  Problem B (Wood).

For given $k\in\mathbb{N}$, does there exist $h(k)=o(k^{2})$, such that every
graph with average degree at least $h(k)$ contains a subdivision of $K_{k,k}$?

This problem essentially asks whether the structure of $H$ could affect the
density needed to force an $H$-subdivision. To understand why the above
question imposes bipartite condition among many other structural conditions,
consider the following example. Consider a graph $H$ with $5n$ edges having no
spanning bipartite subgraph with more than $3n$ edges, then it is easy to see
that $G=K_{n,n}$ does not contain any $H$-subdivision while
$d(G)\geq\Omega(e(H))$. Hence, this shows that being almost bipartite (in the
sense that deleting $o(e(H))$ edges from $H$ leaves a bipartite graph) is a
necessary condition for a sublinear bound to ensure an $H$-subdivision.

However, Im, Kim, Kim and Liu [20] recently observed that bipartiteness on $H$
alone is not sufficient, so the answer to Problem B is no. They showed that
regardless of the structure of $H$, the linear bound $O(e(H))$ cannot be
improved as long as $H$ is dense, i.e. when $d(H)=\Omega(|H|)$. We notice that
a more careful analysis of their construction shows that for any
logarithmically dense $H$, the linear bound is optimal.

######  Proposition 1.2.

For any $h$-vertex graph $H$ with $d(H)\geq 128\log h$, there exists an
$n$-vertex graph $G$ for all sufficiently large $n$ such that
$d(G)\geq\frac{e(H)}{40}$ and $TH\nsubseteq G$.

Thus, to search for graphs $H$ for which a $o(e(H))$-bound on average degree
suffices to force an $H$-subdivision, one has to look into those sparser
almost-bipartite graphs with $d(H)=O(\log h)$. With this proposition, the
following natural question arises. Here, we say that $H$ is $\alpha$-almost-
bipartite if one can delete $\alpha e(H)$ edges to make $H$ bipartite.

######  Problem C.

For given $\varepsilon$, does there exists $\alpha,c,K,h_{0}$ satisfying the
following for all $h\geq h_{0}$? For a given $h$-vertex $\alpha$-almost-
bipartite graph $H$ with $K\leq d(H),\Delta(H)\leq c\log h$, every graph $G$
with average degree at least $\varepsilon e(H)$ contains a subdivision of $H$.

Here, the condition $d(H)\geq K$ is imposed merely to avoid some trivial
counterexamples such as the graphs $H$ having more than $\varepsilon e(H)$
vertices. Indeed, our next theorem proves that the answer to this problem is
yes if we impose an additional separability condition. To ease the notation,
we give the following notion of biseparability, which incorporate both almost-
bipartiteness and separability.

######  Definition 1.3 (Biseparable).

A graph $H$ is called _$(s,k)$ -biseparable_ if there exists $E_{1}\subseteq
E(H)$ with $|E_{1}|\leq s$ such that $H\backslash E_{1}$ is bipartite and
every component in $H\backslash E_{1}$ has at most $k$ vertices.

######  Theorem 1.4.

For given $\varepsilon>0$, there exist $\alpha,c,K>0$ and $h_{0}$ satisfying
the following for all $h>h_{0}$. If $H$ is an $h$-vertex $(\alpha e(H),c\log
h)$-biseparable graph with $d(H)\geq K$, then any graph $G$ with
$d(G)\geq\varepsilon e(H)$ contains a $TH$.

This theorem also shows that the logarithmic density of $H$ in Proposition 1.2
is the correct threshold for the necessity of the linear-in-$e(H)$ bound
forcing $H$-subdivision. The families of graphs $H$ in this theorem includes
almost-bipartite graphs with bounded maximum degree from e.g. any proper
minor-closed classes [1, 22] and classes of graphs with polynomial expansion
[10]. The maximum degree condition is needed only to ensure the above
definition of edge-separability for the graphs in those classes. Below, we
provide two interesting families of $H$ for which a sublinear bound suffices
to force an $H$-subdivision. While the first family is covered by Theorem 1.4,
the second family of the Cartesian powers are not covered by Theorem 1.4 as
their separability is much weaker. This suggests that there are more desired
graphs than Theorem 1.4 provides.

1\. Graphs from stochastic block model. The _stochastic block model_ is a
model for random graphs, introduced in 1983 to study communities in social
network by Holland, Laskey and Leinhardt [19]. This model is heavily studied
thanks to its importance role in recognizing community structure in graph data
in statistics, machine learning, and network science. We will work with the
following bipartite version. Let $t,k,n\in\mathbb{N}$ with $n=2kt$ and
$p,q\in[0,1]$. Denote by $\mathbb{G}(n,p;t,q)$ the $n$-vertex random graph
with an equipartition of the vertex set $V=V_{1}\cup\ldots\cup V_{k}$ such
that (1) for each $i\in[k]$, the subgraph induced on each $V_{i}$ distributed
as a bipartite Erdős-Renyi random graph $G(t,t,q)$,111That is the random
subgraph of $K_{t,t}$ where each edge is retained with probability $q$
independent of others. and (2) for every distinct $i,j\in[k]$, the bipartite
subgraph induced on $[V_{i},V_{j}]$ is distributed as $G(2t,2t,p)$. Such a
model is called _assortative_ if $q>p$.

The first family of graphs $H$ comes from (bipartite strongly assortative)
stochastic block model with logarithmic communities size.

######  Corollary 1.5.

There exists a universal $c>0$ such that the following holds. For any
$\varepsilon>0$, there are $\delta>0$ and $h_{0}\in\mathbb{N}$ satisfying the
following. Let $h\geq h_{0},\leavevmode\nobreak\ t=c\log h$ and
$0<p<\frac{\delta\log h}{h}$. If $H\sim\mathbb{G}(h,p;t,\frac{1}{2})$, then
with probability $1-o_{h}(1)$ every $n$-vertex graph $G$ with $n>h$ and
$d(G)\geq\varepsilon e(H)$ contains a $TH$.

We remark that with high probability, a graph
$H\sim\mathbb{G}(h,p;t,\frac{1}{2})$ above has logarithmic density:
$d(H)=\Omega(t)=\Omega(\log h)$. Furthermore, using standard concentration
inequalities, Theorem 1.4 immediately implies Corollary 1.5.

2\. Cartesian powers of bipartite planar graphs. Given two graphs $G$ and $H$,
the _Cartesian product_ of $G$ and $H$, denoted by $G\Box H$, is the graph
with vertex set $V(G)\times V(H)$ such that two vertices $(x,y)$ and
$(x^{\prime},y^{\prime})$ are adjacent if and only if $(i)$ $x=x^{\prime}$ and
$yy^{\prime}\in E(H)$, or $(ii)$ $y=y^{\prime}$ and $xx^{\prime}\in E(G)$.
Denote by $G^{\Box r}$ the Cartesian powers of $r$ copies of $G$.

The second family consists of Cartesian powers of bounded degree planar
graphs.

######  Theorem 1.6.

For any $\varepsilon>0$ and $D\in\mathbb{N}$, there exists $K>0$ such that the
following holds for all $f\geq K$. Let $F$ be an $f$-vertex bipartite planar
graph with $1\leq d(F),\Delta(F)\leq D$ and let $H=F^{\Box r}$. If
$r\leq\frac{\log\log f}{K}$, then any $n$-vertex graph $G$ with $n\geq f^{r}$
and $d(G)\geq\varepsilon e(H)$ contains a $TH$.

Indeed, the condition on the maximum degree is crucial only for obtaining
required separability. Hence the above condition $\Delta(F)\leq D$ can be
relaxed with $\Delta(F)=o(\sqrt{\log f})$ without much changes in our
argument, see Lemma 3.3 and the discussion afterwards.

###  1.3 Related work

There is a parallel line of research on extremal density forcing a minor of a
graph $H$. The extremal function $c(H)$ of a graph $H$ is the supremum of
average degrees of graphs not containing $H$ as a minor. One classical such
result is by Kostochka [26] and independently Thomason [41]
$c(K_{k})=\Theta(k\sqrt{\log k})$. Later, Thomason and Wales [42] showed that
for general graphs $H$, $c(H)=O(|H|\sqrt{d(H)})$, which is optimal for almost
all polynomially dense $H$. Analogous to Problem B, finding graphs $H$ with
$c(H)$ being $o(|H|\sqrt{d(H)})$ has gained much attention. Here are some
families of such $H$: complete bipartite graphs $K_{s,t}$ [27, 30], disjoint
union of cycles [7] and graphs with strong separation properties [18]. In
particular, Hendrey, Norin and Wood [18] proved that (among others) the
hypercube $Q_{d}$ has $c(Q_{d})=O(2^{d})$. Note that Theorem 1.6 does not
apply to the hypercube. It would be interesting to know whether a sublinear
bound suffices to force a subdivision of hypercube.

######  Problem D.

For given $d\in\mathbb{N}$, does there exist $q(d)=o(d2^{d})$, such that every
graph with average degree at least $q(d)$ contains a subdivision of $Q_{d}$?

Organization. The rest of the paper is organized as follows. Preliminaries are
given in Section 2 and the proof of Proposition 1.2 is given in Section 2.4.
In Section 3, we give overviews of the proof strategies and pack the main
steps of Theorems 1.1, 1.4 and 1.6 into Lemmas 3.1, 3.5 and 3.6; the proofs of
these three main lemmas are given in Sections 4, 5 and 6 respectively.

##  2 Preliminaries

###  2.1 Notation

Denote by $X\sim\mathrm{Bin}(n,p)$ the random variable drawn according to the
binomial distribution with parameters $n$ and $p$. For any positive integer
$r$, we write $[r]$ for the set $\\{1,\ldots,r\\}$. Given a graph $G=(V,E)$,
we denote by $d(G)$ and $\delta(G)$ the average degree and the minimum degree
of $G$, respectively. Given a set $W\subseteq V(G)$, we write
$N_{G}(W)=(\cup_{u\in W}N_{G}(u))\backslash W$. Furthermore, set
$N_{G}^{0}(W):=W$ and $N_{G}^{1}(W):=N_{G}(W)$ and for each $i\geq 1$, define
$N_{G}^{i+1}(W):=N(N_{G}^{i}(W))\setminus N_{G}^{(i-1)}(W)$. Denote by
$B_{G}^{r}(W)$ the ball of radius $r$ around $W$, that is,
$B_{G}^{r}(W)=\cup_{i\leq r}N_{G}^{i}(W)$. For simplicity, write
$B_{G}^{r}(v)=B_{G}^{r}(\\{v\\})$. For any set $W\subset V(G)$, the subgraph
of $G$ induced on $W$, denoted as $G[W]$, is the graph with vertex set $W$ and
edge set $\\{xy\in E(G)|x,y\in W\\}$, and write $G-W=G[V(G)\backslash W]$. For
any $A,B\subseteq V(G)$, we denote by $G[A,B]$ the graph with vertex set
$A\cup B$ and edge set $\\{xy\in E(G)|x\in A,y\in B\\}$. We simply use
$e_{G}(A,B)=|E(G[A,B])|$. Moreover, we define the _density_ between $A$ and
$B$ to be

$d_{G}(A,B)=\frac{e_{G}(A,B)}{|A||B|}.$

For a path $P$, the length of $P$ is the number of edges in $P$, and we say
$P$ is an $x,y$-path if $x$ and $y$ are the endvertices of $P$. Given a family
of graphs $\mathcal{F}$, denote by $|\mathcal{F}|$ the number of graphs in
$\mathcal{F}$ and we write $V(\mathcal{F})=\cup_{G\in\mathcal{F}}V(G)$.

######  Definition 2.1.

A graph $G$ is called _$(\alpha,\beta)$ -dense_ if for every $W\subseteq V(G)$
with $|W|\leq\alpha$, we have $d(G-W)\geq\beta$.

Throughout the paper, we omit floor and ceiling signs when they are not
essential. Also, we use standard hierarchy notation, that is, we write $a\ll
b$ to denote that given $b$ one can choose $a_{0}$ such that the subsequent
arguments hold for all $0<a\leq a_{0}$.

###  2.2 Tools

Let $\mathrm{ex}(n,H)$ be the maximum number of edges in an $H$-free graph on
$n$ vertices. The following lemma gives an upper bound for
$\mathrm{ex}(n,K_{s,t})$.

######  Lemma 2.2 ([28], Kővári-Sós-Turán).

For every integers $1\leq s\leq t$, $\mathrm{ex}(n,K_{s,t})\leq
t^{\frac{1}{s}}n^{2-\frac{1}{s}}$.

The following lemma provide a result for embedding large bipartite graphs with
bounded degeneracy, which is useful in the proof of Lemma 3.4.

######  Lemma 2.3 ([33]).

There exists $K>0$ such that the following holds for every natural number
$\kappa$ and real number $\alpha\leq\frac{1}{2}$. For every natural number
$n\geq\alpha^{-K\kappa^{2}}$, if $G$ is a graph with at least
$\alpha^{-K\kappa}n$ vertices and density at least $\alpha$, then it contains
all graphs in the family of $\kappa$-degenerate bipartite graphs on $n$
vertices as subgraphs.

We discuss the regularity lemma that will be used for embedding certain
subgraphs. Firstly, we introduce the following two definitions.

######  Definition 2.4 ($\varepsilon$-regular pair).

Let $G$ be a graph and $X,Y\subseteq V(G)$. We call $(X,Y)$ an _$\varepsilon$
-regular pair_ (in $G$) if for all $A\subset X,B\subset Y$ with
$|A|\geq\varepsilon|X|,|B|\geq\varepsilon|Y|$, one has

$|d(A,B)-d(X,Y)|\leq\varepsilon.$

Additionally, we say that $(X,Y)$ is _$(\varepsilon,\beta)$ -regular_ if
$d(X,Y)\geq\beta$ for some $\beta>0$.

######  Lemma 2.5 ([8]).

Let $(A,B)$ be an $(\varepsilon,\beta)$-regular pair, and let $Y\subseteq B$
have size $|Y|\geq\varepsilon|B|$. Then all but fewer than $\varepsilon|A|$ of
the vertices in $A$ have $($each$)$ at least $(\beta-\varepsilon)|Y|$
neighbors in $Y$.

######  Definition 2.6 (Regular partition).

A partition $\mathcal{P}=\\{V_{0},V_{1},\ldots,V_{r}\\}$ of $V(G)$ is
_$\varepsilon$ -regular_ if

  * $(i)$

$|V_{0}|\leq\varepsilon|V(G)|$;

  * $(ii)$

$|V_{1}|=|V_{2}|=\cdots=|V_{r}|$;

  * $(iii)$

all but $\varepsilon r^{2}$ pairs $(V_{i},V_{j})$ with $1\leq i<j\leq r$ are
$\varepsilon$-regular.

We need the following form of the regularity lemma.

######  Lemma 2.7 ([40], Szemerédi’s regularity lemma).

For every $\varepsilon>0$, there exists a constant $M=M(\varepsilon)$ such
that for any graph $G=(V,E)$ and $\beta\in[0,1]$, there is an
$\varepsilon$-regular partition $\mathcal{P}=\\{V_{0},V_{1},\ldots,V_{r}\\}$
of $V$ and a subgraph $G^{\prime}=(V,E^{\prime})$ with the following
properties:

  * $(1)$

$r\leq M$,

  * $(2)$

$|V_{i}|\leq\varepsilon|V|$ for all $i\geq 1$,

  * $(3)$

$d_{G^{\prime}}(v)>d_{G}(v)-(\beta+\varepsilon)|V|$ for all $v\in V$,

  * $(4)$

$e(G^{\prime}[V_{i}])=0$ for all $i\geq 1$,

  * $(5)$

every pair $G^{\prime}(V_{i},V_{j})$, $1\leq i<j\leq r$, is
$\varepsilon$-regular, with density either $0$ or greater than $\beta$.

###  2.3 Sublinear expander

Komlós and Szemerédi [24, 25] introduced a notion of expander that is a graph
in which any subset of vertices of reasonable size expands by a sublinear
factor.

######  Definition 2.8 ([24, 25]).

Let $\varepsilon_{1}>0$ and $k\in\mathbb{N}$. A graph $G$ is an
_$(\varepsilon_{1},k)$ -expander_ if

$|N(X)|\geq\rho(|X|,\varepsilon_{1},k)\cdot|X|$

for all $X\subseteq V(G)$ of size $\frac{k}{2}\leq|X|\leq\frac{|V(G)|}{2}$,
where

$\displaystyle\begin{split}\rho(|X|,\varepsilon_{1},k):=\left\\{\begin{array}[]{ll}0&\text{if}\
|X|<\frac{k}{5},\\\
\frac{\varepsilon_{1}}{\log^{2}(\frac{15|X|}{k})}&\text{if}\
|X|\geq\frac{k}{5}.\end{array}\right.\end{split}$

For simplicity, we write $\rho(|X|)$ for $\rho(|X|,\varepsilon_{1},k)$. Note
that $\rho(x)$ is a decreasing function when $x\geq\frac{k}{5}$.

Komlós and Szemerédi [25] showed that every graph $G$ contains a sublinear
expander almost as dense as $G$.

######  Lemma 2.9 ([25]).

There exist $0<\varepsilon_{0},\varepsilon_{1}<\frac{1}{8}$ such that for any
$k\in\mathbb{N}$ every graph $G$ contains an $(\varepsilon_{1},k)$-expander
$H(V,E)$ with

$d(H)\geq\frac{d(G)}{1+\varepsilon_{0}}\geq\frac{d(G)}{2}\ \text{and}\
\delta(H)\geq\frac{d(H)}{2},$

which has the following additional robust property where $n=|V|$. For every
$X\subseteq V$ with $|X|<\frac{n\rho(n)d(H)}{4\Delta(H)}$, there is a subset
$Y\subseteq V\backslash X$ of size
$|Y|>n-\frac{2\Delta(H)}{d(H)}\cdot\frac{|X|}{\rho(n)}$ such that the
restriction $H|_{Y}$ is still an $(\varepsilon_{1},k)$-expander. Moreover,
$d(H[Y])\geq\frac{d(H)}{2}$.

The ‘moreover’ part can be easily obtained by going through their proof in
[25], though it is not explicitly stated in the original lemma.

######  Property 2.10.

Every graph $G$ contains a bipartite subgraph $H$ with
$d(H)\geq\frac{d(G)}{2}$.

Combining Property 2.10 and Lemma 2.9, we immediately obtain the following
corollary.

######  Corollary 2.11.

There exists $\varepsilon_{1}>0$ such that the following holds for every $k>0$
and $d\in\mathbb{N}$. Every graph $G$ with $d(G)\geq 8d$ has a bipartite
$(\varepsilon_{1},k)$-expander $H$ with $\delta(H)\geq d$.

######  Proposition 2.12.

Let $m$ be the smallest even integer which is larger than
$\log^{4}\frac{n}{d}$. If $G$ is an
$(\varepsilon_{1},\varepsilon_{2}d)$-expander and there is a vertex $v\in
V(G)$ with $d(v)\geq\varepsilon_{2}d$, then $|B_{G}^{m}(v)|\geq\frac{n}{2}$.

Proposition 2.12 implies that the vertex with large degree has large $m$-ball
around it, and we postpone its proof in the appendix. A key property of the
expanders that we shall use is to connect vertex sets with a short path whilst
avoiding a reasonable-sized set of vertices.

######  Lemma 2.13 ([25]).

Let $\varepsilon_{1},k>0$. If $G$ is an $n$-vertex
$(\varepsilon_{1},k)$-expander, then for any two vertex sets $X_{1},X_{2}$
each of size at least $x\geq k$, and a vertex set $W$ of size at most
$\frac{\rho(x)x}{4}$, there exists a path in $G-W$ between $X_{1}$ and $X_{2}$
of length at most
$\frac{2}{\varepsilon_{1}}\log^{3}\left(\frac{15n}{k}\right)$.

###  2.4 Proof of Proposition 1.2

We first consider the case when $n=\frac{e(H)}{5}$. Let $G(A,B,\frac{1}{2})$
be an $n$-vertex random bipartite graph, where
$|A|=|B|:=n_{1}=\frac{e(H)}{10}$. We shall verify that with positive
probability, $d(G)\geq\frac{e(H)}{40}$ and $TH\nsubseteq G$. First, let
$X_{1}$ denote the number of edges in $G(A,B,\frac{1}{2})$, then by Chernoff
bound,

$\mathbb{P}\left[X_{1}\leq\frac{\mathbb{E}[X_{1}]}{2}\right]<e^{-\frac{\mathbb{E}[X_{1}]}{8}}.$
(1)

Let $\mathcal{F}$ denote the set of all injections from $V(H)$ to $V(G)$. Note
that $|\mathcal{F}|\leq n^{h}$. To find in $G$ a subdivision of $H$, we first
fix an injection $f\in\mathcal{F}$ and if an edge $uv\in E(H)$ satisfies
$f(u)f(v)\notin E(G)$ (we call it _missing_ in $G$), then we need a path of
length at least $2$ in $G$ to connect $f(u)$ and $f(v)$. Moreover, all such
paths are internally vertex disjoint. Thus, if the number of missing edges is
at least $\frac{e(H)}{4}$, then we can not find a $TH$ in $G$ under the
injection $f$ since each missing edge requires a distinct internal vertex in
$G$ and so $|V(TH)|\geq\frac{e(H)}{4}>2n_{1}=n$.

Hence our strategy is to find a graph $G$ in which every $f\in\mathcal{F}$
witnesses many missing edges. For a fixed $f\in\mathcal{F}$, let $X_{f}$ be
the random variable to count the missing edges under $f$ in
$G(A,B,\frac{1}{2})$. Let $M(f)$ be the set of edges $e=uv$ in $H$ such that
$f(u),f(v)$ lie in the same part, and $B(f)=E(H)\backslash M(f)$. Moreover,
write $m(f)=|M(f)|$. Let $Y_{f}$ be a random variable such that
$Y_{f}\sim\mathrm{Bin}(|B(f)|,\frac{1}{2})$. Then we have $X_{f}=m(f)+Y_{f}$,
and

$\mathbb{E}[X_{f}]=m(f)+\frac{e(H)-m(f)}{2}\geq\frac{e(H)}{2}.$

Then by Chernoff bound,

$\displaystyle\mathbb{P}\left[X_{f}\leq\frac{e(H)}{4}\right]$
$\displaystyle\leq\mathbb{P}\left[X_{f}\leq\mathbb{E}[X_{f}]-\frac{e(H)}{4}\right]=\mathbb{P}\left[m(f)+Y_{f}\leq
m(f)+\mathbb{E}[Y_{f}]-\frac{e(H)}{4}\right]$
$\displaystyle=\mathbb{P}\left[Y_{f}\leq\mathbb{E}[Y_{f}]-\frac{e(H)}{4}\right]\leq
e^{-\frac{(e(H))^{2}}{32\mathbb{E}[Y_{f}]}}\leq e^{-\frac{e(H)}{32}}.$

By union bound, recalling that $n=\frac{e(H)}{5}$, we have

$\displaystyle\mathbb{P}\left[\bigcap_{f\in\mathcal{F}}\left(X_{f}\geq\frac{e(H)}{4}\right)\right]\geq
1-n^{h}e^{-\frac{e(H)}{32}}=1-e^{h\log(\frac{e(H)}{5})-\frac{e(H)}{32}}>\frac{1}{2},$

where the last inequality holds as $e(H)\leq h^{2}$ and $d(H)\geq 128\log h$.
Hence, together with (1), we have that there exists a bipartite graph $G$ such
that $e(G)\geq\frac{n_{1}^{2}}{4}$ and for every $f\in\mathcal{F}$, the number
of missing edges in $G$ is at least $\frac{e(H)}{4}$ under the injection $f$.
So $d(G)\geq\frac{n_{1}}{4}=\frac{e(H)}{40}$ and $TH\nsubseteq G$ as desired.
For larger values of $n$, one can take disjoint union of $G$.

##  3 Main lemmas and overviews

###  3.1 Proof of Theorem 1.1

Note that by Corollary 2.11, $G$ contains a bipartite subgraph with expansion
properties. We divide the proof of Theorem 1.1 into two cases depending on
whether the bipartite subgraph is dense or sparse. The sparse case (see Lemma
3.2) follows from a recent result of Wang [44] on balanced clique
subdivisions. The dense case is the most involved and the bulk of the work is
to handle dense expanders (see Lemma 3.1). Throughout the proof we always
assume $H$ is a graph without isolated vertices.

######  Lemma 3.1.

Suppose
$\frac{1}{n},\frac{1}{d}\ll\frac{1}{C}\ll\varepsilon_{1},\varepsilon_{2}<\frac{1}{5}$
and $s,q\in\mathbb{N}$ satisfy $s\geq 1600$, $\log^{s}n\leq d\leq n$ and
$q\leq\frac{d}{C}$. If $H$ is a graph with $q$ edges and $G$ is an $n$-vertex
bipartite $(\varepsilon_{1},\varepsilon_{2}d)$-expander with $\delta(G)\geq
d$, then $G$ contains a $TH^{(\ell)}$ for some $\ell\in\mathbb{N}$.

######  Lemma 3.2 ([44]).

Suppose
$\frac{1}{n},\frac{1}{d},c\ll\varepsilon_{1},\varepsilon_{2}<\frac{1}{5}$ and
$s\in\mathbb{N}$ satisfies $s\geq 20$ and $\log^{s}n>d$. If $G$ is an
$n$-vertex $TK_{\frac{d}{2}}^{(2)}$-free bipartite
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $\delta(G)\geq d$, then $G$
contains a $TK_{cd}^{(\ell)}$ for some $\ell\in\mathbb{N}$.

###### Proof of Theorem 1.1.

Take $\varepsilon_{2}=\frac{1}{10},s=1600$, then we obtain constants
$\varepsilon_{1}$ from Corollary 2.11 and
$C_{\ref{dense}},c_{\ref{sparse}},d_{0}$ from Lemma 3.1 and Lemma 3.2. Let
$C=\max\\{8C_{\ref{dense}},\frac{16}{c_{\ref{sparse}}}\\}$. Let $G$ be a graph
with average degree $d(G)=d$ for some $d\geq d_{0}$ and let $H$ be an $q$-edge
graph with $q<\frac{d}{C}$. Let $d_{1}=\frac{d}{8}$. By Corollary 2.11, $G$
has a bipartite $(\varepsilon_{1},\varepsilon_{2}d_{1})$-expander $G_{1}$ with
$\delta(G_{1})\geq d_{1}$, and let $|G_{1}|=n$. If $d_{1}\geq\log^{s}n$, then
by Lemma 3.1, $G\supseteq TH^{(\ell)}$ for some $\ell\in\mathbb{N}$.
Otherwise, by Lemma 3.2, either $G\supseteq TK_{\frac{d_{1}}{2}}^{(2)}$ or
$G\supseteq TK_{c_{\ref{sparse}}d_{1}}^{(\ell)}$ for some $\ell\in\mathbb{N}$.
As $c_{\ref{sparse}}d_{1}>2q\geq|V(H)|$, $TH^{(\ell)}\subseteq G$ as desired.
∎

###  3.2 Overview of the proof of Lemma 3.1

Here we give an overview of the proof of Lemma 3.1. We aim to embed a balanced
$TH$ for each $q$-edge graph $H$ with $q\leq\frac{d}{C}$ into the
$(\varepsilon_{1},\varepsilon_{2}d)$-expander $G$ with $\delta(G)\geq d$. If
there are at least $4q$ vertices of large degree ($2dm^{12}$) in $G$, then it
is easy to build a balanced $TH$ (see Lemma 4.12) using adjusters (see
Definition 4.9) to control lengths of paths. Otherwise we will find star-like
structures that serve as the bases for building a balanced subdivision of $H$.
We build for every $v\in V(H)$ a unit or a web (see Definitions 4.3 and 4.4)
in $G$ such that all these units/webs have disjoint interiors to enjoy further
robust expansion. In order to greedily build many units and webs, we shall
first prove that $G$ is locally dense (see Lemmas 4.1 and 4.2). We then divide
$V(H)$ into three parts $\\{\mathbf{L},\mathbf{M},\mathbf{S}\\}$ depending on
their degrees in $H$, and equip every vertex a unit or web with size depending
on the degree (see Lemmas 4.5 and 4.6).

Anchoring at the units or webs as above, we proceed the connection in two
rounds. Let $H_{1}$ be the spanning subgraph of $H$ with $E(H_{1})$ consisting
of all edges incident with vertices in $\mathbf{S}$, and $H_{2}=H\backslash
E(H_{1})$. In the first round, we shall iteratively build, for all edges in
$H_{1}$, internally vertex-disjoint paths in $G$ to obtain a balanced
$TH_{1}$. The problem here is that the union of interiors of webs for all
vertices in $\mathbf{S}$ could be relatively large ($\mathbf{S}=V(H)$ is the
worst-case scenario) and we cannot hope to carry out connections
completelyavoiding their interiors. To overcome this, we instead adopt an
approach developed in [17], which we call _good $\ell$-path systems_. The
rough idea is that one can prepare twice as many webs as needed for vertices
in $\mathbf{S}$ and discard a web once its interior is over-used in the
connection process. Vertices in $\mathbf{L}\cup\mathbf{M}$ (edges in $H_{2}$)
are relatively easier to handle as their units/webs have large exteriors for
robust connections.

###  3.3 Proofs of Theorems 1.4 and 1.6

The following result on partitioning graphs with strongly sublinear separators
is folklore. A _balanced separator_ in a graph $G$ is a set $S\subseteq V(G)$
such that every component of $G-S$ has at most $\frac{2}{3}|V(G)|$ vertices.

######  Lemma 3.3 ([11, 12, 46]).

Let $c>0$ and $\beta\in(0,1)$. Let $G$ be a graph with $n$ vertices such that
every subgraph $G^{\prime}$ has a balanced separator of size at most
$c|V(G^{\prime})|^{1-\beta}$. Then for all $p\geq 1$, there exists $S\subseteq
V(G)$ of size at most $\frac{c2^{\beta}n}{(2^{\beta}-1)p^{\beta}}$ such that
each component of $G-S$ has at most $p$ vertices.

Note that every $f$-vertex planar graph $F$ has a balanced separator of size
$O(\sqrt{f})$ [46]. Thus by the assumption $\Delta(F)=O(1)$ and applying Lemma
3.3 with $p=\log f$, we obtain $S\subseteq V(F)$ of size
$O(\frac{f}{\sqrt{\log f}})$ such that after removing all the
$O(\frac{f}{\sqrt{\log f}})$ edges incident with $S$, each component has at
most $\log f$ vertices. This immediately tells that any planar bipartite graph
$F$ is $(o(f),\log f)$-biseparable. Note that this is the only place where we
need the bounded maximum degree condition, so we can actually relax the
condition $\Delta(F)\leq\Delta$ to $\Delta(F)\leq\sqrt{\log f}$ without much
changes. As a consequence, Theorem 1.6 is an immediate corollary of the
following theorem regarding more general graphs $F$ with similar
biseparability property. A graph $G$ is said to be _$k$ -degenerate_ if every
nonempty subgraph $H$ of $G$ has a vertex of degree at most $k$ in $H$.

######  Lemma 3.4.

Suppose
$\frac{1}{f},\frac{1}{r}\ll\frac{1}{K},\alpha\ll\frac{1}{\kappa},\varepsilon<1$
and $\log f>e^{K\kappa^{2}r}$. If $F$ is an $f$-vertex $\kappa$-degenerate
$(\alpha e(F),\log f)$-biseparable graph with $d(F)\geq 1$, and $H=F^{\Box
r}$, then any graph $G$ with $d(G)\geq\varepsilon e(H)$ contains a $TH$.

Note that $|V(G^{\Box r})|=|V(G)|^{r}$ and $|E(G^{\Box
r})|=r|V(G)|^{r-1}|E(G)|$. To see this, let
$\boldsymbol{a}=(a_{1},a_{2},\ldots,a_{r})$,
$\boldsymbol{b}=(b_{1},b_{2},\ldots,b_{r})$ be two vertices in $V(G^{\Box
r})$, $\boldsymbol{a},\boldsymbol{b}$ are adjacent whenever they only differ
at one coordinate and the corresponding coordinates form an edge in $G$, that
is, there exists $j\in[r]$ such that $a_{j}\neq b_{j}$, $a_{j}b_{j}\in E(G)$
and $a_{i}=b_{i}$ for all $i\neq j$. Moreover, this also verifies that the
Cartesian powers of bipartite graphs is still bipartite [45].

The proofs of Theorem 1.4 and Lemma 3.4 are split into the following two
lemmas depending on the density of the host graph. Denote by $TH^{(\leq\ell)}$
the graph obtained by replacing some edges of $H$ by internally vertex-
disjoint paths of length at most $\ell+1$.

######  Lemma 3.5 (Dense case).

Suppose
$\frac{1}{h},\frac{1}{f},\frac{1}{r}\ll\frac{1}{K},\alpha,c\ll\beta,\varepsilon<1$.

  1. $(1)$

Let $H$ be an $h$-vertex $(\alpha e(H),c\log h)$-biseparable graph with
$d(H)\geq K$. Then any $n$-vertex graph $G$ with $d(G)=\beta n\geq\varepsilon
e(H)$ contains a $TH^{(\leq 3)}$.

  2. $(2)$

Further suppose $\frac{1}{K},\alpha\ll\beta,\frac{1}{\kappa}$ and $\log
f>e^{K\kappa^{2}r}$ for some $\kappa\in\mathbb{N}$. Let $F$ be an $f$-vertex
$\kappa$-degenerate $(\alpha e(F),\log f)$-biseparable graph with $d(F)\geq 1$
and $H=F^{\Box r}$. Then any $n$-vertex graph $G$ with $d(G)=\beta
n\geq\varepsilon e(H)$ contains a $TH^{(\leq 3)}$.

######  Lemma 3.6 (Sparse case).

Suppose
$\frac{1}{h},\frac{1}{f},\frac{1}{r}\ll\frac{1}{K},\alpha,c\ll\varepsilon_{1},\varepsilon_{2},\frac{1}{\kappa}<1$
and $s\in\mathbb{N}$ satisfies $s\geq 1600$ and $\log^{s}n<d<\frac{n}{K}$. Let
$H$ be an $h$-vertex graph satisfying any one of the following properties:

  1. $(1)$

H is $(\alpha e(H),c\log h)$-biseparable with $d(H)\geq K$;

  2. $(2)$

$H=F^{\Box r}$, where $F$ is an $f$-vertex $\kappa$-degenerate $(\alpha
e(F),\log f)$-biseparable graph with $d(F)\geq 1$ and $\log
f>e^{K\kappa^{2}r}$. Observe that $d(H)=rd(F)\geq K$.

Then every $n$-vertex bipartite $(\varepsilon_{1},\varepsilon_{2}d)$-expander
$G$ with $\delta(G)\geq d\geq\varepsilon e(H)$ contains a $TH$.

For these lemmas, we need to build a desired subdivision by finding a sequence
of $x,y$-paths in the host graph $G$, where $xy\in E(H)$. For the dense case,
we use the biseparability of $H$ to embed most of its edges in a regular pair
from a regularity partition; for the remaining edges of $H$, we find disjoint
short paths to replace them. For the sparse case, we shall use sublinear
expanders again to embed an $H$-subdivision in $G$, which is similar as the
proof of Theorem 1.1.

Now we derive Theorem 1.4 and Lemma 3.4 from Lemmas 3.2, 3.5 and 3.6. The
proofs are essentially the same and for simplicity we only present the latter
(Lemma 3.4).

###### Proof of Lemma 3.4.

Take $\varepsilon_{2}=\frac{1}{10},s=1600$, and we obtain a constant
$\varepsilon_{1}$ from Corollary 2.11. Choose
$\frac{1}{f},\frac{1}{r}\ll\frac{1}{K},\alpha\ll\frac{1}{K_{\ref{inte}}}\ll\frac{1}{\kappa},\varepsilon,\varepsilon_{1},\varepsilon_{2}$.
Let $F$ be an $f$-vertex $\kappa$-degenerate $(\alpha e(F),\log
f)$-biseparable graph and $H=F^{\Box r}$. Let $G$ be a graph with average
degree $d(G)=d\geq\varepsilon e(H)=\frac{1}{2}\varepsilon rf^{r}d(F)$ and set
$d_{1}:=\frac{d}{8}$. By Corollary 2.11, $G$ has a bipartite
$(\varepsilon_{1},\varepsilon_{2}d_{1})$-expander $G_{1}$ with
$\delta(G_{1})\geq d_{1}$. Now we let $|G_{1}|=n$. Using Lemma 3.6, we obtain
that if $\log^{s}n\leq d_{1}\leq\frac{n}{K_{\ref{inte}}}$, then $G\supseteq
TH$. If $d_{1}\geq\frac{n}{K_{\ref{inte}}}$, then by Lemma 3.5 with
$\beta=K^{-1}_{\ref{inte}}$, we also have $G\supseteq TH$. Otherwise, by Lemma
3.2, $G\supseteq TK_{cd_{1}}^{(\ell)}$ for some $c>0$ and $\ell\in\mathbb{N}$.
Since $r$ is sufficiently large and $cd_{1}\geq\frac{1}{16}c\varepsilon
rf^{r}d(F)\geq f^{r}$, we have a $TH$ in $G$. ∎

##  4 Proof of Lemma 3.1

Our aim is to find a sequence of $x,y$-paths in the host graph $G$ whose
lengths are exactly $\ell+1$. First in Section 4.1, we reduce the problem to
graphs that are locally dense. Then in Section 4.2, we shall construct webs or
units for building balanced subdivisons of $H$ in $G$. In Section 4.3, we
introduce the concept of _adjuster_ , which is a useful tool to adjust long
paths with the required length. In Section 4.5, we presents a full proof of
Lemma 3.1.

###  4.1 Reduction to locally dense graphs

The next lemma is based on a simple yet powerful method known as dependent
random choice. The _codegree_ of a pair of vertices $u,v$ in a graph, denoted
as $d(u,v)$, is the number of their common neighbors.

######  Lemma 4.1.

Let $G=(V_{1},V_{2})$ be a bipartite graph with $|V_{i}|=n_{i}$ for each
$i\in[2]$ and $e(G)=\alpha n_{1}n_{2}$. If for $p,q\in\mathbb{N}$ it holds
that $\alpha n_{1}>4(p+q)$ and $\alpha^{2}n_{2}>256q$, then $G$ contains a
$TH^{(3)}$ for every $p$-vertex $q$-edge graph $H$.

###### Proof.

Let $w\in V_{2}$ be a vertex chosen uniformly at random. Let $A$ denote the
set of neighbors of $w$ in $V_{1}$, and define random variables $X=|A|$ and
$Y$ as the number of pairs in $A$ with fewer than $4q$ common neighbors. Then

$\mathbb{E}[X]=\sum_{v\in V_{1}}\frac{d(v)}{n_{2}}=\alpha n_{1}\quad\text{and
}\quad\mathbb{E}[Y]\leq\binom{n_{1}}{2}\cdot\frac{4q}{n_{2}}.$

Using linearity of expectation, we obtain

$\mathbb{E}\left[X^{2}-\frac{\mathbb{E}[X]^{2}}{2\mathbb{E}[Y]}Y-\frac{\mathbb{E}[X]^{2}}{2}\right]\geq
0.$

Hence, there is a choice of $w$ such that this expression is non-negative.
Then

$X^{2}\geq\frac{1}{2}\mathbb{E}[X]^{2}>\frac{\alpha^{2}n_{1}^{2}}{2}\quad\text{and
}\quad Y\leq
2\frac{X^{2}}{\mathbb{E}[X]^{2}}\mathbb{E}[Y]<\frac{4qX^{2}}{\alpha^{2}n_{2}}.$

Consequently, $|A|=X>\frac{\alpha n_{1}}{2}$. Denote by $B$ the set of
vertices each of which has codegree less than $4q$ with more than
$\frac{|A|}{16}$ other vertices of $A$. Note that
$|B|\leq\frac{32Y}{|A|}\leq\frac{128q|A|}{\alpha^{2}n_{2}}<\frac{|A|}{2}$ as
$\alpha^{2}n_{2}>256q$.

Figure 1: Embedding

Now we shall embed all vertices of $H$ into $A\backslash B$ and replace each
edge in $H$ by a copy of $P_{5}$ in $G$. Label the vertices of $H$ as
$\\{v_{1},\ldots,v_{p}\\}$. Let $f:V(H)\rightarrow A\backslash B$ be any
injective mapping. Suppose $v_{i}v_{j}$ is the current edge for which we shall
find a $f(v_{i}),f(v_{j})$-path of length $4$ whilst avoiding all internal
vertices used in previous connections. Let

$T_{i}=\\{u\in A\backslash B\mid d(u,f(v_{i}))<4q\\}\quad\text{and }\quad
T_{j}=\\{u\in A\backslash B\mid d(u,f(v_{j}))<4q\\}.$

Then $|T_{i}|,|T_{j}|\leq\frac{|A|}{16}$, and we pick a vertex in
$A\backslash(B\cup T_{i}\cup T_{j}\cup\\{v_{i},v_{j}\\})$, say $u_{ij}$. Since
there are at most $2(q-1)$ vertices in $V_{2}$ used in previous connections,
by the choice of $u_{ij}$, we have $d(f(v_{i}),u_{ij}),\leavevmode\nobreak\
d(f(v_{j}),u_{ij})>4q>2(q-1)$, and thus one can pick two distinct vertices
$x_{i},x_{j}$ not used in previous connections to get the desired
$f(v_{i}),f(v_{j})$-path (see Figure 1). As $|A\backslash B|>\frac{|A|}{2}$
and $|A\backslash B|-|T_{i}|-|T_{j}|-p\geq q$, there are enough vertices in
$A\backslash(B\cup V(H))$ to serve as $u_{ij}$. ∎

######  Lemma 4.2.

Suppose $0<\frac{1}{K}\ll\frac{1}{x}<1$ and $n,d$ and $q$ satisfy $n\geq Kd$
and $d\geq Kq$. Let $H$ be a $q$-edge graph and $G$ be an $n$-vertex graph
with $\delta(G)\geq d$. If $G$ does not contain $TH^{(3)}$, then $G$ is
$(dm^{x},\frac{d}{2})$-dense, where $m=\log^{4}\frac{n}{d}$.

###### Proof.

Fix $W\subseteq V(G)$ with $|W|\leq dm^{x}$. As $\delta(G)\geq d$,
$d(G-W)\geq\delta(G)-|W|\geq\frac{d}{2}$ when $|W|\leq\frac{d}{2}$. We may
assume $|W|>\frac{d}{2}$. Suppose to the contrary that $d(G-W)<\frac{d}{2}$,
then

$e(V(G-W),W)=\sum_{v\in V(G-W)}d(v)-2e(G-W)\geq\frac{d}{2}(n-|W|).$

Let $\alpha=\frac{e(V(G-W),W)}{(n-|W|)|W|}$. Then
$\alpha|W|=\frac{e(V(G-W),W)}{n-|W|}\geq\frac{d}{2}>4(|V(H)|+q)$ as
$|V(H)|\leq 2q$ and

$\alpha^{2}(n-|W|)\geq\frac{d^{2}(n-|W|)}{4|W|^{2}}>\frac{n-|W|}{4m^{2x}}.$
(2)

Since $n\geq Kd$, we get $dm^{2x}\leq\frac{n}{2}$ and $n-|W|>\frac{n}{2}$.
Thus, (2) implies that $\alpha^{2}(n-|W|)>\frac{d}{4}>64q$. Hence, applying
Lemma 4.1 with $W,V(G)-W$ playing the roles of $V_{1},V_{2}$, respectively, we
can find a copy of $TH^{(3)}$ in $G$, a contradiction. ∎

###  4.2 Constructing units and webs

######  Definition 4.3 (unit).

For $h_{1},h_{2},h_{3}\in\mathbb{N}$, a graph $F$ is an _$(h_{1},h_{2},h_{3})$
-unit_ if it contains distinct vertices $u$ (the _core_ vertex of $F$) and
$x_{1},\ldots,x_{h_{1}}$, and $F=\bigcup_{i\in[h_{1}]}(P_{i}\cup S_{i})$,
where

  * •

$\mathcal{P}=\bigcup_{i\in[h_{1}]}P_{i}$ is a collection of pairwise
internally vertex-disjoint paths, each of length at most $h_{3}$, such that
$P_{i}$ is a $u,x_{i}$-path, and

  * •

$\mathcal{S}=\bigcup_{i\in[h_{1}]}S_{i}$ is a collection of vertex-disjoint
$h_{2}$-stars such that $S_{i}$ has center $x_{i}$ and
$\bigcup_{i\in[h_{1}]}(V(S_{i})\backslash\\{x_{i}\\})$ is disjoint from
$V(\mathcal{P})$.

We call $S_{i}$ a _pendent_ star in the unit $F$ and every such path $P_{i}$
is a _branch_ of $F$. Define the _exterior_
$\mathsf{Ext}(F):=\bigcup_{i\in[h_{1}]}(V(S_{i})\backslash\\{x_{i}\\})$ and
_interior_ $\mathsf{Int}(F):=V(F)\backslash\mathsf{Ext}(F)$.

Figure 2: $(h_{0},h_{1},h_{2},h_{3})$-web

######  Definition 4.4 (web).

For $h_{0},h_{1},h_{2},h_{3}\in\mathbb{N}$, a graph $W$ is an
_$(h_{0},h_{1},h_{2},h_{3})$ -web_ if it contains distinct vertices $v$ (the
_core_ vertex of $W$), $u_{1},\ldots,u_{h_{0}}$, and
$W=\bigcup_{i\in[h_{0}]}(Q_{i}\cup F_{i})$, where

  * •

$\mathcal{Q}=\bigcup_{i\in[h_{0}]}Q_{i}$ is a collection of pairwise
internally vertex-disjoint paths such that each $Q_{i}$ is a $v,u_{i}$-path of
length at most $h_{3}$.

  * •

$\mathcal{F}=\bigcup_{i\in[h_{0}]}F_{i}$ is a collection of vertex-disjoint
$(h_{1},h_{2},h_{3})$-units such that $F_{i}$ has core vertex $u_{i}$ and
$\bigcup_{i\in[h_{0}]}(V(F_{i})\backslash\\{u_{i}\\})$ is vertex-disjoint from
$V(\mathcal{Q})$.

We call each $Q_{i}$ a _branch_ and call the branches inside each unit $F_{i}$
the _second-level_ branches of $W$. Similarly define the _exterior_
$\mathsf{Ext}(W):=\bigcup_{i\in[h_{0}]}\mathsf{Ext}(F_{u_{i}})$, and the
_interior_ $\mathsf{Int}(W):=V(W)\backslash\mathsf{Ext}(W)$ and additionally
define _center_ $\mathsf{Ctr}(W):=V(\mathcal{Q})$.

We need two technical results that enable us to find a collection of units and
webs with varying sizes as anchoring points for building a balanced
subdivision of $H$.

######  Lemma 4.5.

Suppose
$\frac{1}{n},\frac{1}{d}\ll\frac{1}{K}\ll\varepsilon_{1},\varepsilon_{2}<\frac{1}{5}$
and $x,y,z\in\mathbb{N}$ satisfy $\frac{y-9}{2}<z<y<\min\\{x,z+10\\}$. Let
$n,d,\gamma$ be integers satisfying $m^{x}\leq d\leq\frac{n}{K}$ and
$m^{z}\leq\gamma<\frac{d}{m^{10}}$ where $m=\log^{4}\frac{n}{d}$. If
$G=(V_{1},V_{2},E)$ is a $(dm^{x},\frac{d}{2})$-dense bipartite
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $d(G)=d$ and $W$ is a set
of vertices with $|W|\leq 100dm^{x-2y+z-4}$, then $G-W$ contains a
$(22\gamma,m^{y-z},\frac{dm^{z}}{20\gamma},4m)$-web with core vertex lying in
$V_{1}$.

Lemma 4.5 can be proved following the strategy in [23]. We provide a detailed
proof in the appendix of the arXiv version.

######  Lemma 4.6.

Suppose $\frac{1}{n},\frac{1}{d}\ll\frac{1}{K}\ll
c_{0}\ll\varepsilon_{1},\varepsilon_{2}\leq 1$ and $x,y,z,s\in\mathbb{N}$
satisfies $s\geq\max\\{8x,y\\}$ and $\log^{s}n\leq d\leq\frac{n}{K}$. Let
$m=\log^{4}\frac{n}{d}$. Let $G=(V_{1},V_{2},E)$ be an $n$-vertex bipartite
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with
$dm^{x}\geq\Delta(G)\geq\delta(G)\geq d$ and $W$ be a vertex set with $|W|\leq
dm^{z}$. Then $G-W$ contains a $(c_{0}d,m^{y},2m)$-unit with core vertex lying
in $V_{1}$.

Previous approach for building units proceeds by linking many stars, which can
only produce units with sublinear in $d(G)$ many branches. Here we use
directly the robust expansion property to construct the large unit with linear
number of branches in Lemma 4.6. For this, we need the following notion.

######  Definition 4.7 ([34]).

Given a graph $G$ and $W\subseteq V(G)$, we say that paths
$P_{1},\ldots,P_{t}$, each starting with a vertex $v$ and contained in the
vertex set $W$, are _consecutive shortest paths_ from $v$ in $W$ if for each
$i$ $(1\leq i\leq t)$, the path $P_{i}$ is a shortest path between its
endpoints in the set $W\setminus(\bigcup_{j<i}V(P_{j}))\cup\\{v\\}$.

The robust expansion property we need is as follows. We defer its proof in the
appendix.

######  Lemma 4.8.

Suppose $\frac{1}{n},\frac{1}{d}\ll
c,\frac{1}{K}\ll\varepsilon_{1},\varepsilon_{2}<\frac{1}{5}$ and
$s,x\in\mathbb{N}$ satisfy $s\geq 8x$ and $\log^{s}n<d<\frac{n}{K}$. Let
$m=\log^{4}\frac{n}{d}$. Let $H$ be an $n$-vertex
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $\delta(H)\geq\frac{d}{2}$
and $P_{1},\dots,P_{t}$ be consecutive shortest paths from $v$ in
$B^{m}_{H}(v)$. Writing $U=\bigcup_{i\in t}V(P_{i})$, if $t\leq cd$, then
$|B_{H-(U\backslash\\{v\\})}^{m}(v)|\geq dm^{x}$.

###### Proof of Lemma 4.6.

Given $\varepsilon_{1},\varepsilon_{2},x,y,z,s$ such that
$s\geq\max\\{8x,y\\}$, we choose $\frac{1}{K}\ll
c_{0}\ll\frac{1}{x},\frac{1}{y},\frac{1}{z},\varepsilon_{1},\varepsilon_{2}$
and take $t=|y-z|+4$. Let $G=(V_{1},V_{2},E)$ be a bipartite
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $\delta(G)\geq d$,
$\Delta(G)\leq dm^{x}$ and $W\subseteq V(G)$ with $|W|\leq dm^{z}$. We first
greedily find $dm^{t}$ vertex-disjoint stars $S_{1},\ldots,S_{dm^{t}}$, each
with $2m^{y}$ leaves. This can indeed be done by picking an average vertex as
$\Delta(G)\leq dm^{x}$ and $\Delta(G)\cdot dm^{t}\cdot
2m^{y}<n\cdot\delta(G)/10\leq e(G)/5$. Denote by $u_{i}$ the center vertex of
$S_{i}$ for each $i\in[dm^{t}]$ and $U:=\\{u_{1},\ldots,u_{dm^{t}}\\}$. Note
that $|W|+|\bigcup_{i\in[dm^{t}]}V(S_{i})|\leq 2dm^{y+t}+dm^{z}$. Applying
Lemma 2.9 with $G,\bigcup_{i\in[dm^{t}]}V(S_{i})\cup W$ playing the roles of
$H,X$, we have that $G-W-\bigcup_{i\in[dm^{t}]}V(S_{i})$ contains a set
$Y_{1}$ such that $|Y_{1}|\geq n-\frac{4dm^{x+y+t}+2dm^{x+z}}{\rho(n)d(G)}\geq
n-\frac{6dm^{x+y+t}}{\rho(n)d(G)}\geq\frac{n}{2}$ and $G[Y_{1}]$ is an
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with
$d(G[Y_{1}])\geq\frac{d}{2}$. Next we will find a desired ball in
$G_{1}:=G[Y_{1}]$. Arbitrarily choose a vertex of degree $\frac{d}{2}$ in
$G_{1}$. Then by Proposition 2.12, there exists a ball $B_{G_{1}}^{m}(v)$ in
$G_{1}$ such that

$|B_{G_{1}}^{m}(v)|\geq\frac{|G_{1}|}{2}\geq\frac{n}{4}\geq dm^{y+t}.$

To build the desired $(c_{0}d,m^{y},2m)$-unit, we shall proceed by finding
$2c_{0}d$ internally vertex-disjoint paths $Q_{1},\ldots,Q_{2c_{0}d}$ in $G$
from $v$ satisfying the following rules.

  1. (A1)

Each path is a $v,u_{i}$-path of length at most $2m$.

  2. (A2)

Each path does not contain any vertex in $U\cup W$ as an internal vertex.

  3. (A3)

The subpaths $Q_{i}[B^{m}_{G_{1}}(v)]$, $i\in[2c_{0}d]$, form consecutive
shortest paths from $v$ in $B^{m}_{G_{1}}(v)$.

Assume that we have iteratively obtained a collection of shortest paths
$\mathcal{Q}=\\{Q_{1},\ldots,Q_{s^{\prime}}\\}$ $(0\leq s^{\prime}<2c_{0}d)$
as in (A1)-(A3). Then $|\mathsf{Int}(\mathcal{Q})|<4c_{0}dm$. Note that (A3)
gives $s^{\prime}$ consecutive shortest paths $P_{1},\ldots,P_{s^{\prime}}$
from $v$ in $B_{G_{1}}^{r}(v)$, where $P_{i}=Q_{i}[B^{m}_{G_{1}}(v)]$. Write
$\mathcal{P}=\\{P_{1},\ldots,P_{s^{\prime}}\\}$. Applying Lemma 4.8 to
$G_{1}$, we get

$|B^{m}_{G_{1}-\mathsf{Int}(\mathcal{Q})}(v)|=|B_{G_{1}-\mathsf{Int}(\mathcal{P})}^{m}(v)|\geq
dm^{y+t}.$

Let $U^{\prime}$ be the set of leaves of all stars $S_{i}$ whose centers are
not used as endpoints of paths $Q_{i}$ for all $i\in[s^{\prime}]$ and
$U^{\prime}\cap\mathsf{Int}(\mathcal{Q})=\varnothing$. Then we have

$|U^{\prime}|\geq
2m^{y}(dm^{t}-2c_{0}d)-|\mathsf{Int}(\mathcal{Q})|>dm^{y+t}.$

Note that

$|W|+|V(\mathcal{Q})|+|U|\leq dm^{z}+4c_{0}dm+dm^{t}<2c_{0}dm^{y+t-1}.$

Applying Lemma 2.13 with $B_{G_{1}-\mathsf{Int}(\mathcal{Q})}^{m}(v)$,
$U^{\prime}$, $V(\mathcal{Q})\cup U\cup W$ playing the roles of
$X_{1},X_{2},W$, respectively, we can find a shortest path, say $Q^{\prime}$
from $B_{G_{1}-\mathsf{Int}(\mathcal{Q})}^{m}(v)$ to some $u_{j}$, and write
$w^{\prime}$ for the endpoint of $Q^{\prime}$ inside the ball
$B^{m}_{G_{1}-\mathsf{Int}(\mathcal{Q})}(v)$. Then
$B^{m}_{G_{1}-\mathsf{Int}(\mathcal{Q})}(v)\cap
V(Q^{\prime})=\\{w^{\prime}\\}$ and one can easily find a $v,w^{\prime}$-path,
denoted as $P_{s^{\prime}+1}$, inside
$B^{m}_{G_{1}-\mathsf{Int}(\mathcal{Q})}(v)$. Let
$Q_{s^{\prime}+1}=P_{s^{\prime}+1}Q^{\prime}$ be the concatenation of two
paths $P_{s^{\prime}+1}$ and $Q^{\prime}$. Then the paths
$Q_{1},\ldots,Q_{s^{\prime}+1}$ satisfy (A1)-(A3). Repeating this for
$k=0,1,\ldots,2c_{0}d$, yields $cd$ paths $Q_{1},\ldots,Q_{2c_{0}d}$ as
desired.

Let $W^{\prime}=\bigcup_{i\in[2c_{0}d]}V(Q_{i})$. Then $|W^{\prime}|\leq
4c_{0}dm$. For every $i\in[dm^{t}]$, we say $S_{i}$ is _overused_ if at least
$m^{y}$ leaves of $S_{i}$ are used in $W^{\prime}$. Then there are at most
$\frac{4c_{0}dm}{m^{y}}=\frac{4c_{0}d}{m^{y-1}}$ overused stars. Hence, we
have at least $2c_{0}d-\frac{4c_{0}d}{m^{y-1}}>c_{0}d$ remaining stars not
overused, say $S_{1},\ldots S_{c_{0}d}$, such that their centers are connected
to $v$ via the paths $Q_{i}$ as above. Then these stars together with the
corresponding paths $Q_{i}$ yield a $(c_{0}d,m^{y},2m)$-unit as desired. ∎

###  4.3 Constructing adjusters

Given a graph $F$ and a vertex $v\in V(F)$, we say $F$ is a _$(D,m)$
-expansion_ centered at $v$ if $|F|=D$ and $v$ is at distance at most $m$ in
$F$ from any other vertex of $F$.

######  Definition 4.9 ([35]).

A _$(D,m,k)$ -adjuster_ $\mathcal{A}=(v_{1},F_{1},v_{2},F_{2},A)$ in a graph
$G$ consists of vertices $v_{1},v_{2}\in V(G)$, graphs $F_{1},F_{2}\subseteq
G$ such that the following holds for some $\ell\in\mathbb{N}$.

  1. (B1)

$A$, $V(F_{1})$ and $V(F_{2})$ are pairwise disjoint.

  2. (B2)

For each $i\in[2]$, $F_{i}$ is a $(D,m)$-expansion centered at $v_{i}$.

  3. (B3)

$|A|\leq 10mk$.

  4. (B4)

For each $i\in\\{0,1,\ldots,k\\}$, there is a $v_{1},v_{2}$-path in
$G[A\cup\\{v_{1},v_{2}\\}]$ with length $\ell+2i$.

We denote by $\ell(\mathcal{A})$ the smallest integer $\ell$ for which (B4)
holds. Note that $\ell(\mathcal{A})\leq|A|+1\leq 10mk+1$. We refer to the
graphs $F_{1}$ and $F_{2}$ of an adjuster
$\mathcal{A}=(v_{1},F_{1},v_{2},F_{2},A)$ as the _ends_ of the adjuster, and
let $V(\mathcal{A})=V(F_{1})\cup V(F_{2})\cup A$. Moreover, $v_{1},v_{2}$ are
called _core_ vertices of $\mathcal{A}$, and $A$ is called _center_ vertex set
of $\mathcal{A}$. We call a $(D,m,1)$-adjuster a _simple_ adjuster.

We use the following variations of lemmas from [35] to control lengths of
paths. We defer their proofs in the appendix.

######  Lemma 4.10.

Suppose
$\frac{1}{n},\frac{1}{d}\ll\frac{1}{K}\ll\varepsilon_{1},\varepsilon_{2}<\frac{1}{5}$
and $s,x,y\in\mathbb{N}$ satisfy $s\geq 1600$, $s\geq 8x>8y$ and
$\log^{s}n<d<\frac{n}{K}$. Let $m=\log^{4}\frac{n}{d}$ and $D=10^{-7}dm^{y}$.
If $G$ is an $n$-vertex $(dm^{x},\frac{d}{2})$-expander with $\delta(G)\geq d$
and $W\subseteq V(G)$ satisfies $|W|\leq m^{-\frac{3}{4}}D$, then $G-W$
contains a $(D,m,r)$-adjuster for any $r\leq 10^{-1}dm^{y-2}$.

######  Lemma 4.11.

Suppose
$\frac{1}{n},\frac{1}{d}\ll\frac{1}{K}\ll\varepsilon_{1},\varepsilon_{2}<1$
and $s,x,y\in\mathbb{N}$ satisfy $s\geq 1600$, $s\geq 8x>8y$ and
$\log^{s}n<d<\frac{n}{K}$. Let $m=\log^{4}\frac{n}{d}$ and $D=10^{-7}dm^{y}$
and $\ell\leq dm^{y-2}$. Suppose that $G$ is an $n$-vertex
$(dm^{x},\frac{d}{2})$-dense $(\varepsilon_{1},\varepsilon_{2}d)$-expander
with $\delta(G)\geq d$ and the following hold.

  1. $(1)$

$W\subseteq V(G)$ with $|W|\leq m^{-\frac{3}{4}}D$.

  2. $(2)$

$Z_{i}\subseteq V(G)\setminus W$ are pairwise disjoint vertex sets of size at
least $D$ for each $i\in[2]$.

  3. $(3)$

$I_{j}\subseteq V(G)\setminus(W\cup Z_{1}\cup Z_{2})$ are vertex-disjoint
$(D,m)$-expansion centered at some vertex $v_{j}$ for each $j\in[2]$.

Then $G-W$ contains vertex-disjoint paths $P$ and $Q$ with
$\ell\leq\ell(P)+\ell(Q)\leq\ell+18m$ such that $P,Q$ link $\\{z_{1},z_{2}\\}$
to $\\{v_{1},v_{2}\\}$ for some $z_{1}\in Z_{1}$ and $z_{2}\in Z_{2}$.

###  4.4 Warm-up: many large degree vertices

Let $L_{G}:=\\{v\in V(G):d_{G}(v)\geq 2dm^{12}\\}$, where
$m=\log^{4}\frac{n}{d}$. In this subsection, we consider the case when
$|L_{G}|\geq 4q$.

######  Lemma 4.12.

Suppose
$\frac{1}{n},\frac{1}{d}\ll\frac{1}{K}\ll\varepsilon_{1},\varepsilon_{2},\frac{1}{s}<1$
and $s\geq 400$ and $q\in\mathbb{N}$ satisfies $\log^{s}n\leq
d\leq\frac{n}{K}$ and $q\leq\frac{d}{K}$. Let $G$ be an $n$-vertex bipartite
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $\delta(G)\geq d$ and $H$
be a $q$-edges graph. If $|L_{G}|\geq 4q$, then $TH^{(\ell)}\subseteq G$ for
some $\ell\in\mathbb{N}$.

###### Proof.

We may assume that $G$ is $TH^{(3)}$-free, otherwise we are done. Given
$\varepsilon_{1},\varepsilon_{2}>0$ and $s\geq 400$, we choose
$\frac{1}{d}\ll\frac{1}{K}\ll\varepsilon_{1},\varepsilon_{2},\frac{1}{s}$ and
$m=\log^{4}\frac{n}{d}$. Applying Lemma 4.2 to $G$ with $x=50$, we have that
$G$ is $(dm^{50},\frac{d}{2})$-dense. Let $V(H)=\\{x_{1},\ldots,x_{h}\\}$ and
$E(H)=\\{e_{1},\ldots,e_{q}\\}$ with $q\leq\frac{d}{K}$. Since $H$ has no
isolated vertices, we obtain $q\geq\frac{h}{2}$, and so
$|L_{G}|\geq\frac{h}{2}\cdot 4=2h$. Thus, it is possible to take a set
$Z=\\{u_{1},\ldots,u_{h}\\}$ of $h$ distinct vertices in $L_{G}$ such that all
vertices in $Z$ lie in the same part of $G$. Let $\tau:V(H)\rightarrow Z$ be
an arbitrary injection. Note that for each $i\in[h]$, the set $N(u_{i})$ has
size at least $2dm^{12}$. Next we shall construct a $TH^{(\ell)}$ by greedily
finding a collection of paths of the same length $\ell=m^{3}$. Assume that we
have a maximal collection of pairwise internally disjoint paths, say
$P(e_{1}),\ldots,P(e_{t})$, such that $t\leq q$ and each $P(e_{j})$ is a path
of length exactly $\ell$ in $G$ connecting the two vertices in $\tau(e_{j})$
whilst $P(e_{j})$ is internally disjoint from $Z$. We claim that $t=q$ and so
these paths $P(e_{j})$ yield a balanced subdivision of $H$. Suppose for
contradiction that $t<q$. We shall find one more path $P(e_{t+1})$ for
$e_{t+1}\in E(H)$. Write $e_{t+1}=x_{1}x_{2}$ and let $u_{i}=\tau(x_{i})$ for
$i\in[2]$.

Let $W=\bigcup_{j\in[t]}\mathsf{Int}(P(e_{j}))$ be the union of the interior
vertices of the paths. Then $|W|+|Z|<q\cdot\ell+h\leq 2dm^{3}$. Set
$D=10^{-7}dm^{12}$ and we have $|W\cup Z|<\frac{1}{2}m^{-\frac{3}{4}}D$.
Applying Lemma 4.10 with $y=12$, $r=20m$ and $W\cup Z$ playing the role of
$W$, we obtain a $(D,m,20m)$-adjuster say
$\mathcal{A}=(v_{1},F_{1},v_{2},F_{2},A)$ in $G-(W\cup Z)$, and observe that
$\ell(\mathcal{A})\leq|A|\leq 200m^{2}$. Note that

$|N(u_{i})\setminus(V(\mathcal{A})\cup W\cup Z)|\geq
2dm^{12}-2D-200m^{2}-qm^{3}-h\geq 2D\leavevmode\nobreak\ \text{for
each}\leavevmode\nobreak\ i\in[2].$

Then there are disjoint vertex sets $U_{1}\subseteq N(u_{1})$ and
$U_{2}\subseteq N(u_{2})$ each of size $D$ in $G-(V(\mathcal{A})\cup W\cup
Z)$. Choose $\ell^{\prime}=\ell-19m-\ell(\mathcal{A})$. Since $d\geq\log^{s}n$
and $|W\cup A\cup Z|\leq 200m^{2}+\frac{1}{2}m^{-\frac{3}{4}}D+q\leq
m^{-\frac{3}{4}}D$, by applying Lemma 4.11 with $x=50$ and
$W_{\ref{extadju}}=W\cup A\cup Z$, there exist vertex-disjoint paths $P$ and
$Q$ linking $\\{y_{1},y_{2}\\}$ to $\\{v_{1},v_{2}\\}$ for $y_{1}\in
U_{1},y_{2}\in U_{2}$, and
$\ell^{\prime}\leq\ell(P)+\ell(Q)\leq\ell^{\prime}+18m$. We may assume that
$P$ is a $y_{1},v_{1}$-path and $Q$ is a $y_{2},v_{2}$-path. Then
$P^{\prime}=\\{u_{1}y_{1}\\}\cup P$ is a $u_{1},v_{1}$-path and
$Q^{\prime}=\\{u_{2}y_{2}\\}\cup Q$ is a $u_{2},v_{2}$-path with
$\ell^{\prime}\leq\ell(P^{\prime})+\ell(Q^{\prime})\leq\ell^{\prime}+19m$.
Also observe that
$\ell(\mathcal{A})\leq\ell-\ell(P^{\prime})-\ell(Q^{\prime})\leq\ell(\mathcal{A})+19m$.
Since $u_{1},u_{2}$ lie in the same part of $G$, we obtain that
$\ell(\mathcal{A})$ and $\ell(P^{\prime})+\ell(Q^{\prime})$ have the same
parity. Furthermore, since $\ell$ is even and $\mathcal{A}$ is a
$(D,m,20m)$-adjuster, it follows by definition that $A$ contains a
$v_{1},v_{2}$-path say $R^{\prime}$ of length
$\ell-\ell(P^{\prime})-\ell(Q^{\prime})$. Thus, the path $P^{\prime}\cup
R^{\prime}\cup Q^{\prime}$, denoted as $P(e_{t+1})$, has length $\ell$ and
connects $u_{1}$ and $u_{2}$ whilst avoiding $W\cup Z$, which together with
$\\{P(e_{1}),\ldots,P(e_{t})\\}$ contradicts the maximality of $t$. ∎

###  4.5 Putting things together, proof of Lemma 3.1

We need the following result.

######  Lemma 4.13 ([15]).

Let $H$ be a graph with at most $n$ edges and vertices and let $G$ be a graph
with $N$ vertices and $\varepsilon N^{2}$ edges such that
$N>128\varepsilon^{-3}n$. Then $TH^{(1)}\subseteq G$.

###### Proof of Lemma 3.1.

Given $0<\varepsilon_{1},\varepsilon_{2}<\frac{1}{5}$, we choose

$\frac{1}{d}\ll\frac{1}{C}\ll\frac{1}{K}\ll
c_{0}\ll\varepsilon_{1},\varepsilon_{2},\frac{1}{s}.$

Let $G$ be an $n$-vertex bipartite
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $\delta(G)\geq
d\geq\log^{s}n$ and $H$ be a $q$-edge graph with $q\leq\frac{d}{C}$. If
$d>\frac{n}{K}$, then as $\frac{1}{C}\ll\frac{1}{K}$ and $d\geq Cq$, we have
$n\geq 128(2K)^{3}\cdot 2q>2048K^{2}(|V(H)|+q)$. Applying Lemma 4.13 with
$\varepsilon=\frac{1}{2K}$, we can get $TH^{(1)}\subseteq G$. Hence it remains
to consider the case when $\log^{s}n\leq d\leq\frac{n}{K}$. Let
$m=\log^{4}\frac{n}{d}$. If $|L_{G}|\geq 4q$, then Lemma 4.12 gives us a
$TH^{(\ell)}$ for some $\ell\in\\{3,m^{3}\\}$. Now we assume that
$|L_{G}|<4q\leq\frac{4d}{C}<\frac{\varepsilon_{2}d}{2}$. We may further assume
that $G$ is $TH^{(3)}$-free, otherwise we are done. Applying Lemma 4.2 to $G$
with $x=50$, we have that $G$ is $(dm^{50},\frac{d}{2})$-dense.

In the rest of the proof, we take $\ell=m^{3}$ and our goal is to embed a
$TH^{(\ell)}$. We call $Z$ an _object_ if it is a web or unit. We divide
$V(H)$ into three parts according to the degree:

$\mathbf{L}=\\{v\in V(H)|d(v)\geq\frac{d}{m^{10}}\\},\quad\mathbf{M}=\\{v\in
V(H)|m^{4}<d(v)<\frac{d}{m^{10}}\\},\quad\mathbf{S}=\\{v\in V(H)|d(v)\leq
m^{4}\\}.$

In the following, for every $v\in V(H)$, we shall construct a web or a unit in
$G$ (depends on the degree of $v$), such that these objects are pairwise
internally disjoint. Note that

$2e(H)=\sum_{v\in V(H)}d_{H}(v)\geq|\mathbf{L}|\cdot\frac{d}{m^{10}},$

and thus $|\mathbf{L}|\leq m^{10}$.

First greedily find a family of internally vertex-disjoint webs
$\\{Z_{v}\\}_{v\in\mathbf{M}}$, where each $Z_{v}$ is a
$(22d_{H}(v),m^{8},\frac{dm^{4}}{20d_{H}(v)},4m)$-web and $2|\mathbf{S}|$
internally vertex-disjoint $(22m^{4},m^{8},\frac{d}{20},4m)$-webs, say
$Z_{1},\ldots,Z_{2|\mathbf{S}|}$. This can be done by repeatedly applying
Lemma 4.5 to $G$ with $x=50,y=12,z=4$ and $W$ being the set of internal
vertices of objects found so far, since

$|W|\leq\sum_{v\in\mathbf{M}}90d_{H}(v)m^{9}+2|\mathbf{S}|22m^{13}\leq
180qm^{9}+44qm^{13}<100dm^{13}.$

######  Claim 4.14.

$G_{1}:=G-L_{G}$ is an $(\frac{\varepsilon_{1}}{2},\varepsilon_{2}d)$-expander
satisfying $\delta(G_{1})\geq\frac{d}{2}$ and $|G_{1}|\geq\frac{n}{2}$.

###### Proof.

Recall that $|L_{G}|\leq\frac{4d}{C}<\delta(G)<|G|$, we know that $L_{G}\neq
V(G)$. Therefore $|G_{1}|\geq n-|L_{G}|\geq n-\frac{4d}{C}\geq\frac{n}{2}$.
Furthermore, $\delta(G_{1})\geq\delta(G)-|L_{G}|\geq\frac{d}{2}$. To finish
the proof of the claim, it is left to show that $G_{1}$ is an
$(\frac{\varepsilon_{1}}{2},\varepsilon_{2}d)$-expander. Since $G$ is an
$(\varepsilon_{1},\varepsilon_{2}d)$-expander and $\rho(x)x$ is increasing
when $x\geq\frac{\varepsilon_{2}d}{2}$, for any set $X$ in $G_{1}$ of size
$x\geq\frac{\varepsilon_{2}d}{2}$ with
$x\leq\frac{|G_{1}|}{2}\leq\frac{|G|}{2}$, we have

$|N_{G}(X)|\geq
x\cdot\rho(x,\varepsilon_{1},\varepsilon_{2}d)\geq\frac{\varepsilon_{2}d}{2}\cdot\rho\left(\frac{\varepsilon_{2}d}{2},\varepsilon_{1},\varepsilon_{2}d\right)=\frac{\varepsilon_{2}d}{2}\cdot\frac{\varepsilon_{1}}{\log^{2}(\frac{15}{2})}\geq\frac{\varepsilon_{1}\varepsilon_{2}d}{10}\geq\frac{8d}{C}\geq
2|L_{G}|.$

Hence,
$|N_{G_{1}}(X)|\geq|N_{G}(X)|-|L_{G}|\geq\frac{1}{2}|N_{G}(X)|\geq\frac{1}{2}x\cdot\rho(x,\varepsilon_{1},\varepsilon_{2}d)=x\cdot\rho\left(x,\frac{\varepsilon_{1}}{2},\varepsilon_{2}d\right)$
as desired. ∎

Applying Lemma 4.6 on $G_{1}$ with $x=14,y=13,z=14$, we can greedily pick a
family $\\{Z_{v}\\}_{v\in\mathbf{L}}$ of pairwise internally vertex-disjoint
units such that $Z_{v}$ is a $(c_{0}d,m^{13},2m)$-unit and they are internally
disjoint from the previous obtained webs. This is possible because in the
process, the union of $L_{G}$ and the interiors of all possible units or webs
has size at most $dm^{14}$.

Denote by $z_{v}$ the core vertex of the object
$\\{Z_{v}\\}_{v\in\mathbf{M}\cup\mathbf{L}}$ and $z_{i}$ the core vertex of
the web $Z_{i}$ for each $i\in[2|\mathbf{S}|]$. Recall that all these core
vertices lie in the same part $V_{1}$. Moreover, every two objects can only
overlap at their exteriors. Note that

$|\mathsf{Ext}(Z_{v})|=\begin{cases}c_{0}dm^{13},\quad\text{if
}v\in\mathbf{L},\\\ \frac{11dm^{12}}{10},\quad\text{if
}v\in\mathbf{M},\end{cases}\text{and}\quad|\mathsf{Ext}(Z_{i})|=\frac{11dm^{12}}{10},\quad\text{if
}i\in[2|\mathbf{S}|].$

Let $H_{1}$ be a spanning subgraph of $H$ with

$E(H_{1})=E(H[\mathbf{S}])\cup E(H[\mathbf{S},\mathbf{L}\cup\mathbf{M}]),$

that is, all edges that touch $\mathbf{S}$ and write $H_{2}=H\backslash
E(H_{1})$. We shall find a mapping $f:V(H)\rightarrow V(G)$ and a family of
pairwise internally disjoint paths of the same length $\ell$ respecting the
adjacencies of $H$ in the following two rounds, where we may abuse the
notation $f$ as the up-to-date embedding. We begin with embedding every
$v\in\mathbf{L}\cup\mathbf{M}$ by taking $f(v)=z_{v}$.

First round: Finding the desired paths (in $G$) for the adjacencies in
$H_{1}$.

Let
$W=(\bigcup_{v\in\mathbf{L}\cup\mathbf{M}}\mathsf{Int}(Z_{v}))\cup(\bigcup_{i\in[2|\mathbf{S}|]}\mathsf{Ctr}(Z_{i}))\cup
L_{G}$. Then

$|W|\leq|\mathbf{L}|\cdot
2c_{0}dm+\sum_{v\in\mathbf{M}}22d_{H}(v)m^{9}+2|\mathbf{S}|22m^{4}\cdot
4m+\frac{\varepsilon_{2}d}{2}\leq 30dm^{11}.$

For a given vertex set $Y$ and $i\in[2|\mathbf{S}|]$, we say a web $Z_{i}$ is
_$Y$ -good_ if $|\mathsf{Int}(Z_{i})\cap Y|\leq 11m^{12}$ (which is at most
$\frac{1}{2}|\mathsf{Int}(Z_{i})|$). To extend $f$ to $V(H)$ whilst finding
the desired paths for the adjacencies in $H_{1}$, we use the notion of _good
$\ell$-path system_ as follows. We define $(X,I,I^{\prime},\mathcal{Q},f)$ to
be a _good $\ell$-path system_ if the followings hold.

  1. (C1)

$X\subseteq\mathbf{S}$ and $f$ injectively maps $X$ to
$I\subseteq[2|\mathbf{S}|]$.

  2. (C2)

$\mathcal{Q}$ is a collection of internally vertex-disjoint paths $Q_{x,y}$ of
length $\ell$ for all edges $xy\in E(H_{1})$ touching $X$, such that $Q_{x,y}$
is a $z_{f(x)},z_{f(y)}$-path disjoint from
$W\setminus(\mathsf{Int}(Z_{f(x)})\cup\mathsf{Int}(Z_{f(y)}))$.

  3. (C3)

In particular, $Q_{x,y}$ begins (or ends) with a subpath within the object
$Z_{f(x)}$ (resp. $Z_{f(y)}$) connecting the core $z_{f(x)}$ (resp.
$z_{f(y)}$) to $\mathsf{Ext}(Z_{f(x)})$, denoted as $P_{x}(y)$ (resp.
$P_{y}(x)$). Moreover, we write $Q_{x,y}^{\prime}$ for the middle segment of
$Q_{x,y}$, i.e. $Q_{x,y}^{\prime}=Q_{x,y}\setminus(P_{x}(y)\cup P_{y}(x))$ and
let $\mathcal{Q}^{\prime}$ be the family of these paths $Q_{x,y}^{\prime}$.

  4. (C4)

$I^{\prime}=\\{i\in[2|\mathbf{S}|]:Z_{i}\ \text{is}\ \text{not}\
V(\mathcal{Q}^{\prime})\text{-good}\\}$ and $I^{\prime}\cap I=\varnothing$.

Now it suffices to build a good $\ell$-path system with $X=\mathbf{S}$. We
proceed our construction as follows.

Step $0$. Fix an arbitrary ordering $\sigma$ on $\mathbf{S}$, say the first
vertex is $x_{1}$. Let $X_{1}=\\{x_{1}\\}$, $f(x_{1})=1$, $I_{1}=\\{1\\}$,
$I^{\prime}_{1}=\varnothing$ and $\mathcal{Q}_{1}=\varnothing$. Then by
definition $(X_{1},I_{1},I^{\prime}_{1},\mathcal{Q}_{1},f|_{X_{1}})$ is a good
$\ell$-path system. Proceed to Step $1$.

Step $i$. Stop if either $X_{i}=\mathbf{S}$ or $I_{i}\cup
I^{\prime}_{i}=[2|\mathbf{S}|]$. Otherwise we continue:

  1. (D1)

Let $x$ be the first vertex in $\sigma$ on $\mathbf{S}\backslash X_{i}$.
Choose a $V(\mathcal{Q}^{\prime}_{i})$-good object $Z_{t}$ with
$t\in[2|\mathbf{S}|]\backslash(I_{i}\cup I^{\prime}_{i})$ and define $f(x)=t$.

  2. (D2)

Find internally vertex-disjoint paths $Q_{x,y}$ for every neighbor $y$ of $x$
in $X_{i}\cup\mathbf{M}\cup\mathbf{L}$ satisfying (C2)-(C3). Once this is
done, we add these paths to $\mathcal{Q}_{i}$ to get $\mathcal{Q}_{i+1}$.

  3. (D3)

Update bad webs
$I^{\prime}_{i+1}=\\{i^{\prime}\in[2|\mathbf{S}|]:Z_{i^{\prime}}\ \text{is}\
\text{not}\ V(\mathcal{Q}^{\prime}_{i+1})\text{-}\text{good}\\}$ as
$I_{i+1}=(I_{i}\cup\\{t\\})\backslash I^{\prime}_{i+1}$,
$X_{i+1}=f^{-1}(I_{i+1})$ and replace $f$ with its restriction $f|_{X_{i+1}}$.

  4. (D4)

Proceed to Step $(i+1)$ with a good $\ell$-path system
$(X_{i+1},I_{i+1},I^{\prime}_{i+1},\mathcal{A}_{i+1},\mathcal{Q}_{i+1},$
$f|_{X_{i+1}})$.

Now we claim the following result and postpone its proof later.

######  Claim 4.15.

In each step the desired paths in _(D2)_ can be successfully found.

Therefore Claim 4.15 implies that $|I_{i}\cup I^{\prime}_{i}|$ is strictly
increasing at each step and the above process must terminate in at most
$2|\mathbf{S}|$ steps. Let $(X,I,I^{\prime},\mathcal{Q},f)$ be the final good
$\ell$-path system returned from the above process and $\mathcal{Q}^{\prime}$
be given as in (C3). Note that the sequence $|X_{1}|,|X_{2}|,\ldots$ might not
be an increasing sequence, as we may delete some elements when updating the
list of bad webs. Next we show that the process must terminate with
$X=\mathbf{S}$.

Observe that by the definition of $W$, for each
$v\in\mathbf{M}\cup\mathbf{L}$, $Z_{v}$ is $V(\mathcal{Q}^{\prime})$-good, and
$\mathcal{Q}^{\prime}$ might contain some paths whose vertex set intersects
$\mathsf{Int}(Z_{i^{\prime}})\setminus\mathsf{Ctr}(Z_{i^{\prime}})$ with
$i^{\prime}\in I^{\prime}$. As at most $m^{4}$ paths are added at each step
(D2), we have $|I^{\prime}|\leq\frac{2|\mathbf{S}|m^{4}\cdot
m^{3}}{11m^{12}}=\frac{2|\mathbf{S}|}{11m^{5}}<|\mathbf{S}|$. Thus, $|I\cup
I^{\prime}|<2|\mathbf{S}|$, and then the process terminates with
$X=\mathbf{S}$. To complete the proof, it remains to show that all connections
in (D2) can be guaranteed in each step.

###### Proof of Claim 4.15.

Given a good $\ell$-path system
$(X_{i},I_{i},I^{\prime}_{i},\mathcal{Q}_{i},f|_{X_{i}})$ and
$x\in\mathbf{S}\setminus X_{i}$, $Z_{f(x)}$ as in (D1), we let
$\\{y_{1},\ldots,y_{s}\\}=N_{H_{1}}(x)\cap(X_{i}\cup\mathbf{M}\cup\mathbf{L})$
and recall that our aim is to build pairwise internally disjoint paths
$Q_{x,y_{j}}$ for all $j\in[s]$, each being a $z_{f(x)},z_{f(y_{j})}$-path of
length $\ell$. Note that by definition $Z_{f(y_{j})}$ is
$V(\mathcal{Q}^{\prime}_{i})$-good as $y_{j}\in
X_{i}\cup\mathbf{M}\cup\mathbf{L}$ for every $j\in[s]$. Recall that $Z_{f(x)}$
is actually a $(22m^{4},m^{8},\frac{d}{20},4m)$-web that is also
$V(\mathcal{Q}^{\prime}_{i})$-good by our choice.

Fix a vertex $y=y_{j}$ as above and set $D=10^{-7}dm^{12}$ and
$W^{\prime}=W\cup\mathsf{Int}(Z_{f(x)})\cup\mathsf{Int}(Z_{f(y)})\cup
V(\mathcal{Q}_{i})$. Thus $|W^{\prime}|\leq
30dm^{11}+22m^{4}[4m+m^{8}(m+2)]+\max\\{22\cdot
dm^{-10}\cdot[4m+m^{8}(m+2)],c_{0}d\\}+m^{3}|\mathcal{Q}_{i}|\leq\frac{1}{2}Dm^{-\frac{3}{4}}.$
Applying Lemma 4.10 to $G$ with $y=12$ and $W^{\prime}$ playing the role of
$W$, we obtain a $(D,m,20m)$-adjuster in $G-W^{\prime}$, denoted as
$\mathcal{A}=(v_{1},F_{1},v_{2},F_{2},A)$. Therefore, $|A|\leq 200m^{2}$,
$\ell(\mathcal{A})\leq|A|+1\leq 210m^{2}$.

Recall that $Z_{f(x)}$ and $Z_{f(y)}$ are $V(\mathcal{Q}^{\prime}_{i})$-good.
we shall see that they still have large boundaries for further connections.
Consider the case when $y\in\mathbf{S}\cup\mathbf{M}$, that is, $Z_{f(y)}$ is
either a $(22m^{4},m^{8},\frac{d}{20},4m)$-web or a
$(22d_{H}(y),m^{8},\frac{dm^{4}}{20d_{H}(y)},4m)$-web with $d_{H}(y)\geq
m^{4}$. Here we may take the case $y\in\mathbf{M}$ for instance (the case
$y\in\mathbf{S}$ is much easier). Note that there are at most $d_{H}(x)$
branches of $Z_{f(y)}$ are used for previous connections in $\mathcal{Q}_{i}$.
Hence, there are at least $21d_{H}(y)m^{8}-11m^{12}\geq 10d_{H}(y)m^{8}$
available paths in $\mathsf{Int}(Z_{f(y)})\backslash\mathsf{Ctr}(Z_{f(y)})$,
that is, the second-level branches which are not touched by $\mathcal{Q}_{i}$.
Let $U_{y}\subseteq\mathsf{Ext}(Z_{f(y)})$ be the union of the leaves of the
pendant stars attached to the ends of these available paths. Then
$|U_{y}|\geq\frac{1}{2}dm^{12}-dm^{3}\geq 4D$. Similarly, the case when
$Z_{f(y)}$ is a $(c_{0}d,m^{13},2m)$-unit, also witnesses such a vertex set
$U_{y}\subseteq\mathsf{Ext}(Z_{f(y)})$ of size at least
$c_{0}dm^{13}-dm^{3}>4D$. Thus by taking subsets and renaming, there are two
disjoint vertex sets $U_{x}\subseteq\mathsf{Ext}(Z_{f(x)})$ and
$U_{y}\subseteq\mathsf{Ext}(Z_{f(y)})$ each of size $D$ and they are disjoint
from $F_{1}$ and $F_{2}$.

Let $\ell^{\prime}=\ell-34m-\ell(\mathcal{A})$. Since $d\geq\log^{s}n$,
$|A\cup W^{\prime}|\leq 200m^{2}+\frac{1}{2}Dm^{-\frac{3}{4}}\leq
Dm^{-\frac{3}{4}}$, by applying Lemma 4.11, we obtain vertex-disjoint paths,
say $P_{x}$ and $P_{y}$ with
$\ell^{\prime}\leq\ell(P_{x})+\ell(P_{y})\leq\ell^{\prime}+18m$, and we may
further assume that $P_{x}$ is a $v_{1},v_{x}$-path and $P_{y}$ is a
$v_{2},v_{y}$-path for some $v_{x}\in U_{x}$, $v_{y}\in U_{y}$. On the other
hand, by extending $P_{x}$ (similarly $P_{y}$) within the object $Z_{f(x)}$
(resp. $Z_{f(y)}$), we can obtain a $v_{1},z_{f(x)}$-path say $P_{x}^{\prime}$
(resp. $P_{y}^{\prime}$) of length at most $8m+\ell(P_{x})$. Note that
$\ell^{\prime}\leq\ell(P_{x}^{\prime})+\ell(P_{y}^{\prime})\leq\ell^{\prime}+34m$.
Thus
$\ell(\mathcal{A})\leq\ell-\ell(P_{x}^{\prime})-\ell(P_{y}^{\prime})\leq\ell(\mathcal{A})+34m$.
As $\mathcal{A}$ is a $(D,m,20m)$-adjuster, there is a $v_{1},v_{2}$-path $R$
(in $A$) of length $\ell-\ell(P_{x}^{\prime})-\ell(P_{y}^{\prime})$, which
together with $P_{x}^{\prime},P_{y}^{\prime}$ yields a
$z_{f(x)},z_{f(y)}$-path of length $\ell$ as desired, which is denoted as
$Q_{x,y}$. We can greedily build the pairwise disjoint paths $Q_{x,y}$ for all
$y\in\\{y_{1},\ldots,y_{s}\\}$ using the same argument as above. ∎

Second round: Finding the desired paths (in $G$) for the adjacencies in
$H_{2}$.

Let $\mathcal{Q}$ be the resulting family of paths for the adjacencies in
$H_{1}$ and $f$ be the resulting embedding of $V(H)$ returned from the first
round. Note that $|\mathcal{Q}|\leq\ell\cdot e(H_{1})\leq\ell\cdot
e(H)<dm^{3}$ and $\mathcal{Q}$ is disjoint from
$\bigcup_{v\in\mathbf{L}\cup\mathbf{M}}\mathsf{Int}(Z_{v})$. Recall that
$|\mathsf{Ext}(Z_{v})|=\frac{11dm^{12}}{10}$ for each $v\in\mathbf{M}$ and
$|\mathsf{Ext}(Z_{v})|=c_{0}dm^{13}$ for each $v\in\mathbf{L}$. Update
$W=(\bigcup_{v\in\mathbf{L}\cup\mathbf{M}}\mathsf{Int}(Z_{v}))\cup
V(\mathcal{Q})$. Then

$|W|\leq|\mathbf{L}|\cdot
2c_{0}dm+\sum_{v\in\mathbf{M}}22d_{H}(v)m^{9}+dm^{3}\leq 30dm^{11}.$

Observe that every $v\in\mathbf{L}$ witnesses at least $c_{0}d-d_{H}(v)$
available branches in the unit $Z_{f(v)}$ and every $v\in\mathbf{M}$ witnesses
at least $22d_{H}(v)-d_{H}(v)$ branches in $\mathsf{Ctr}(Z_{f(v)})$, which are
disjoint from $V(\mathcal{Q})$. Similarly for each
$x\in\mathbf{L}\cup\mathbf{M}$, let $V_{x}\subseteq\mathsf{Ext}(Z_{x})$ be the
union of the leaves from the pendant stars attached to one end of these
available paths. Then
$|V_{x}|\geq\min\\{(c_{0}d-d_{H}(v))m^{13}-dm^{3},\frac{21dm^{12}}{10}-dm^{3}\\}\geq
dm^{12}$.

Let $I\subseteq E(H_{2})$ be a maximum set of edges for which there exists a
collection $\mathcal{P}_{I}=\\{P_{e}:e\in I\\}$ of internally vertex-disjoint
paths under the following rules.

  1. (E1)

For each $xy=e\in E(H_{2})$, $P_{e}$ is a $z_{f(x)},z_{f(y)}$-path of length
$\ell$ and $P_{e}$ is disjoint from
$W\setminus(\mathsf{Int}(Z_{f(x)})\cup\mathsf{Int}(Z_{f(y)}))$.

  2. (E2)

$P_{e}$ begins (or ends) with the unique subpath within the object $Z_{f(x)}$
(resp. $Z_{f(y)}$) connecting the core vertex $z_{f(x)}$ (resp. $z_{f(y)}$)
and some vertex in $\mathsf{Ext}(Z_{f(x)})$.

######  Claim 4.16.

$I=E(H_{2})$.

###### Proof of Claim 4.16.

Suppose to the contrary that there exists $e=x_{1}x_{2}\in E(H_{2})\setminus
I$ with no desired path in $\mathcal{P}_{I}$ between their corresponding
objects, say $Z_{1},Z_{2}$. Set $D=10^{-7}dm^{12}$ and $W^{\prime}=W\cup
V(\mathcal{P}_{I})$, and thus

$|W^{\prime}|\leq 30dm^{11}+\ell e(H)\leq
32dm^{11}<\min\left\\{\frac{1}{2}Dm^{-\frac{3}{4}},\tfrac{\rho(2D)2D}{4}\right\\}.$

Applying Lemma 4.10 with $y=12$ and $W^{\prime}$ playing the role of $W$, we
obtain a $(D,m,20m)$-adjuster $\mathcal{A}=(v_{1},F_{1},v_{2},F_{2},A)$ in
$G-W^{\prime}$. Note that $|A|\leq 200m^{2}$ and
$\ell(\mathcal{A})\leq|A|+1\leq 210m^{2}$. Now let
$\ell^{\prime}=\ell-30m-\ell(\mathcal{A})$. On the other hand, as
$|V_{x_{i}}|\geq dm^{12}\geq 2D$ for $i\in[2]$, there are disjoint vertex sets
$U_{1}\subseteq V_{x_{1}}$ and $U_{2}\subseteq V_{x_{2}}$ of size $D$. Since
$d\geq\log^{s}n$, $|A\cup W^{\prime}|\leq
200m^{2}+\frac{1}{2}Dm^{-\frac{3}{4}}\leq Dm^{-\frac{3}{4}}$, applying Lemma
4.11 gives vertex-disjoint paths say $Q_{1}$, $Q_{2}$ with
$\ell^{\prime}\leq\ell(Q_{1})+\ell(Q_{2})\leq\ell^{\prime}+18m$ and we may
assume that $Q_{1}$ is a $u_{1},v_{1}$-path and $Q_{2}$ is a
$u_{2},v_{2}$-path for some $u_{1}\in U_{1},u_{2}\in U_{2}$. By the adjustment
as above via $\mathcal{A}$, we can easily extend $Q_{1},Q_{2}$ into a desired
path of length $\ell$ connecting $z_{1}$ and $z_{2}$ while avoiding
$W^{\prime}$, denoted as $P_{e}$. Thus $\\{P_{e}\\}\cup\mathcal{P}_{I}$ yields
a contradiction to the maximality of $\mathcal{P}_{I}$. ∎

In summary, the resulting families of paths $\mathcal{Q}$ in the first round
and $\mathcal{P}_{E(H_{2})}$ in the second round form a copy of $TH^{(\ell)}$
as desired. ∎

##  5 Proof of Lemma 3.5

To prove $(1)$, take $\beta_{1}=\frac{\beta}{2}$ and choose

$\frac{1}{h}\ll\frac{1}{K},\alpha,c\ll\frac{1}{k}\ll\varepsilon_{1}\ll\beta,\varepsilon.$

First, we apply Lemma 2.7 to obtain an $\varepsilon_{1}$-regular partition
$\mathcal{P}=\\{V_{0},V_{1},\ldots,V_{k}\\}$ of $V(G)$ ($k\leq
M(\varepsilon_{1})$). Arbitrarily choose an
$(\varepsilon_{1},\beta_{1})$-regular pair, say $(V_{1},V_{2})$. Note that
$|V_{1}|=|V_{2}|\geq\frac{(1-\varepsilon_{1})n}{k}$. For each $i\in[2]$, a
vertex $v$ in $V_{i}$ is _bad_ if
$d_{G[V_{3-i}]}(v)<(\beta_{1}-\varepsilon_{1})|V_{3-i}|$, and denote by
$B_{i}$ the set of bad vertices in $V_{i}$. By Lemma 2.5,
$|B_{i}|\leq\varepsilon_{1}|V_{i}|$. As $H$ is $(\alpha e(H),c\log
h)$-biseparable, there exists $E_{1}\subseteq E(H)$ with $|E_{1}|\leq\alpha
e(H)$ such that each component of $H\setminus E_{1}$ is bipartite on at most
$c\log h$. Let $C_{1},C_{2},\ldots C_{m}$ be all components of $H\setminus
E_{1}$. Note that $m\geq\frac{h}{c\log h}$. Now we shall embed each $C_{i}$
into $U:=(V_{1}\cup V_{2})\backslash(B_{1}\cup B_{2})$.

For simplicity, let $\rho n=|V_{1}\cup V_{2}|$ and $t=c\log h$. Then
$\rho\geq\frac{2(1-\varepsilon_{1})}{k}$, $|B_{1}\cup
B_{2}|\leq\varepsilon_{1}\rho n$. Suppose that $C_{1},\ldots,C_{i-1}$ have
been embedded into $U$, and $C_{i}$ is the current component to embed. Observe
that since $d(H)\geq K$,

$\sum_{j=1}^{i-1}|C_{j}|\leq h\leq\frac{2\beta n}{\varepsilon
d(H)}\leq\frac{\rho n}{3}.$

Let $R_{j}=V_{j}\cap\left(\bigcup_{z=1}^{i-1}C_{z}\right)$ for each $j\in[2]$.
Now we shall embed $C_{i}$ into $(V_{1}\cup V_{2})\backslash(R_{1}\cup
R_{2}\cup B_{1}\cup B_{2})$, which has size $\xi n$, where
$\xi\geq(1-\varepsilon_{1}-\frac{1}{3})\rho\geq\frac{\rho}{2}$. Since $t=c\log
h$ and $c\ll\frac{1}{k},\beta$, we have

$\mathrm{ex}(\xi n,K_{t,t})\leq t^{\frac{1}{t}}(\xi
n)^{2-\frac{1}{t}}=\left(\frac{t}{\xi n}\right)^{\frac{1}{t}}(\xi
n)^{2}<\frac{(\beta_{1}-\varepsilon_{1})\cdot(\xi n)^{2}}{100}\leq e(U).$

Hence can embed a $K_{t,t}\supseteq C_{i}$ into $U$. Let
$V(H)=\\{v_{1},v_{2},\ldots,v_{h}\\}$. Denote by $\varphi:V(H)\rightarrow
V(G)$ the resulting embedding of $C_{1},\ldots,C_{m}$ and let
$\varphi(v_{i})=u_{i}$ for each $i\in[h]$.

Next, for all edges in $H[C_{i},C_{j}]$ $(i,j\in[m])$, we embed pairwise
internally disjoint paths of length at most $4$ avoiding $\varphi(V(H))$ in
$G[V_{1},V_{2}]$. Suppose that $v_{i}v_{j}$ $(v_{i}\in C_{i},v_{j}\in C_{j})$
is the current edge for which we shall find a $u_{i},u_{j}$-path whilst
avoiding all internal vertices used in previous connections. Denote by $W$ the
vertex set containing all internal vertices used in previous connections, then
$|W|\leq 3|E_{1}|$. Recall that $|E_{1}|\leq\alpha e(H)\leq\frac{\alpha
n}{\varepsilon}$. If $u_{i},u_{j}$ are located in the same part, say
$u_{i},u_{j}\in V_{1}$, then we have that for each $p\in\\{i,j\\}$

$|N(u_{p})\cap(V_{2}\backslash
W)|\geq(\beta_{1}-\varepsilon_{1})|V_{2}|-3\alpha
e(H)\geq\frac{\beta_{1}|V_{2}|}{2}.$

Thus, fixing an arbitrary $A\subseteq V_{1}$ such that
$A\cap(\varphi(V(H))\cup W)=\varnothing$ and $|A|\geq\varepsilon_{1}|V_{1}|$,
we have that for each $p\in\\{i,j\\}$

$|d(A,N(u_{p})\cap(V_{2}\backslash W))|>\beta_{1}-\varepsilon_{1}.$

Therefore, any typical vertex $a\in A$ with positive degree to
$N(u_{p})\cap(V_{2}\backslash W)$, $p\in\\{i,j\\}$, yields a
$u_{i},u_{j}$-path of length $4$ as desired. We can choose such typical
vertices by Lemma 2.5. The case when $u_{i},u_{j}$ are in different parts is
simpler. Say $u_{i}\in V_{1}$, $u_{j}\in V_{2}$, then it is easy to find a
$u_{i},u_{j}$-path of length $3$ using edges between
$N(u_{i})\cap(V_{2}\backslash W)$ and $N(u_{j})\cap(V_{1}\backslash W)$; we
omit the details. Note that all these paths corresponding to $E_{1}=\cup
H[C_{i},C_{j}]$ together with $C_{1},\ldots,C_{m}$ form a desired copy of
$TH^{(\leq 3)}$

To prove $(2)$, we first need the following claim.

######  Claim 5.1.

If $F$ is $\kappa$-degenerate and $(\alpha e(F),\log f)$-biseparable, then
$H=F^{\Box r}$ is $r\kappa$-degenerate and $(\alpha
e(H),\log^{r}f)$-biseparable.

###### Proof of Claim 5.1.

Since $F$ is $\kappa$-degenerate, there exists an ordering of vertices in $F$,
say $v_{1},\ldots,v_{f}$ such that each $v_{i}$ has at most $\kappa$ neighbors
in $\\{v_{i+1},\ldots,v_{f}\\}$. Give two vertices
$\boldsymbol{x}=(x_{1},x_{2},\ldots,x_{r})$,
$\boldsymbol{y}=(y_{1},y_{2},\ldots,y_{r})$ in $V(H)$, we define an ordering
on $V(H)$ by letting $\boldsymbol{x}<\boldsymbol{y}$ if there exists $i\in[r]$
such that $x_{j}=y_{j}$ for all $j\in[i]$ but $x_{i+1}\neq y_{i+1}$, say
$x_{i+1}=v_{k_{1}}$, $y_{i+1}=v_{k_{2}}$ for some $k_{1}<k_{2}$. It is obvious
that the resulting ordering, say
$\boldsymbol{w_{1}},\boldsymbol{w_{2}},\ldots,\boldsymbol{w_{h}}$, satisfies
that every vertex $\boldsymbol{w_{i}}$ has at most $r\kappa$ neighbors in
$\\{\boldsymbol{w_{i+1}},\ldots,\boldsymbol{w_{h}}\\}$. Thus, $H$ is
$r\kappa$-degenerate.

Next, as $F$ is $(\alpha e(F),\log f)$-biseparable, we get that there exists
$E_{1}\subseteq E(F)$ with $|E_{1}|\leq\alpha e(F)$ such that each component
of $F\setminus E_{1}$ is bipartite on at most $\log f$ vertices. Let $E_{2}$
be the set of all edges $\boldsymbol{x}\boldsymbol{y}\in E(H)$ by writing
$\boldsymbol{x}=(x_{1},x_{2},\ldots,x_{r})$ and
$\boldsymbol{y}=(y_{1},y_{2},\ldots,y_{r})$ such that $x_{i}y_{i}\in E_{1}$
for some $i\in[r]$. Hence, $|E_{2}|=rf^{r-1}|E_{1}|\leq\alpha
rf^{r-1}e(F)=\alpha e(H)$. By the construction of $H$, it is easy to see that
each component of $H\setminus E_{2}$ is bipartite on at most $\log^{r}f$
vertices, as claimed. ∎

Now we choose
$\frac{1}{r},\frac{1}{f}\ll\frac{1}{K},\alpha\ll\frac{1}{k}\ll\varepsilon_{1}\ll\beta,\varepsilon,\frac{1}{\kappa}$,
and apply Lemma 2.7 with $\beta_{1}=\frac{\beta}{2}$ to obtain an
$\varepsilon_{1}$-regular partition $\mathcal{P}=\\{V_{0},V_{1},...V_{k}\\}$
($k\leq M(\varepsilon_{1})$) of $V(G)$. Arbitrarily choose an
$(\varepsilon_{1},\beta_{1})$-regular pair, say $(V_{1},V_{2})$. Note that
$|V_{1}|=|V_{2}|\geq\frac{(1-\varepsilon_{1})n}{k}$. We shall embed all
components $C_{1},\ldots,C_{m}$ $(m\geq\frac{f^{r}}{\log^{r}f})$ of
$H\setminus E_{2}$ into $V_{1}\cup V_{2}$ one by one disjointly using Lemma
2.3. To this end, we need check two inequalities mentioned in Lemma 2.3, that
is,

$\log^{r}f\geq\left(\frac{\beta}{2}\right)^{-K_{\ref{Leethm}}(r\kappa)^{2}}$
(3)

and

$\frac{|V_{1}|}{2}\geq\frac{(1-\varepsilon_{1})n}{2k}\geq(\frac{\beta}{2})^{-K_{\ref{Leethm}}r\kappa}\log^{r}f.$
(4)

Under the condition $\log f>e^{K\kappa^{2}r}$, we obtain that the inequality
$(\ref{1ineq})$ holds by taking $K\geq K_{\ref{Leethm}}\log\frac{2}{\beta}$.
As $n\geq d\geq\varepsilon e(H)=\frac{1}{2}\varepsilon rf^{r}d(F)$ and $\log
f>e^{K\kappa^{2}r}$, we have that

$\log n\geq r\log f\geq Kr(\kappa+\log\log f)$

holds, which implies inequality (4) from the choice
$\frac{1}{K}\ll\frac{1}{k},\beta$.

For all edges in $H[C_{i},C_{j}]$ $(i,j\in[m])$, we embed pairwise disjoint
paths of length at most 4 in $G[V_{1},V_{2}]$ using the same argument as in
Part (1), which together with all $C_{1},\ldots,C_{m}$ form the desired
$TH^{(\leq 3)}$.

##  6 Proof of Lemma 3.6

We need the following lemma.

######  Lemma 6.1.

Suppose
$\frac{1}{h},\frac{1}{f},\frac{1}{r}\ll\frac{1}{K},\alpha,c\ll\frac{1}{x},\frac{1}{\kappa},\varepsilon<1$
and $s,n,d\in\mathbb{N}$ satisfy $s\geq 1600$ and $\log^{s}n\leq
d\leq\frac{n}{K}$. Let $H$ be an $h$-vertex graph and $G$ be an bipartite
graph with $\delta(G)\geq d\geq\varepsilon e(H)$ satisfying one of the
following conditions.

  1. $(1)$

$H$ is $(\alpha e(H),c\log h)$-biseparable with $d(H)\geq K$.

  2. $(2)$

$H=F^{\Box r}$, where $F$ is an $f$-vertex $\kappa$-degenerate $(\alpha
e(F),\log f)$-biseparable graph with $d(F)\geq 1$ and $\log
f>e^{K\kappa^{2}r}$.

Then either $G$ contains a $TH^{(\leq 7)}$ or $G$ is
$(dm^{x},\frac{d}{2})$-dense for $m=\log^{4}\frac{n}{d}$.

###### Proof.

Suppose that $G$ is not $(dm^{x},\frac{d}{2})$-dense, then there exists some
$W\subseteq V(G)$ with $|W|\leq dm^{x}$ such that $d(G-W)<\frac{d}{2}$. As
$\delta(G)\geq d$, we may assume $|W|>\frac{d}{2}$. Denote by $n_{1}:=|W|\leq
dm^{x}$ and $n_{2}:=|V(G-W)|\geq n-dm^{x}$. Then

$\pi:=\frac{e(W,V(G-W))}{n_{1}n_{2}}>\frac{n_{2}\cdot\frac{d}{2}}{n_{1}n_{2}}=\frac{d}{2n_{1}}\geq\frac{1}{2m^{x}}.$

Let $w\in V(G-W)$ be a vertex chosen uniformly at random, and let $A$ denote
the set of neighbors of $w$ in $W$, and $X=|A|$. Then $\mathbb{E}[X]=\pi
n_{1}>\frac{d}{2}$.

Let $Y$ be the random variable counting the number of pairs in $A$ with fewer
than $4e(H)$ common neighbors in $G-W$. Then
$\mathbb{E}[Y]\leq\frac{4e(H)}{n_{2}}\binom{n_{1}}{2}\leq\frac{2e(H)n_{1}^{2}}{n_{2}}.$
Using linearity of expectation, we obtain

$\mathbb{E}\left[X^{2}-\frac{\mathbb{E}[X]^{2}}{2\mathbb{E}[Y]}Y-\frac{\mathbb{E}[X]^{2}}{2}\right]\geq
0.$

Hence, there is a choice of $w$ such that this expression is nonnegative. Then

$X^{2}\geq\frac{1}{2}\mathbb{E}[X]^{2}>\frac{d^{2}}{8}\quad\text{and}\quad
Y\leq
2\frac{X^{2}}{\mathbb{E}[X]^{2}}\mathbb{E}[Y]<\frac{4e(H)X^{2}}{\alpha^{2}n_{2}}<\frac{16m^{2x}e(H)|A|^{2}}{n-dm^{x}}\leq\frac{|A|^{2}}{8}.$

Then, $|A|=X>\frac{d}{4}$.

Define a graph $G_{1}=(V(G_{1}),E(G_{1}))$ with $V(G_{1})=A$, and $uv$ is an
edge of $G_{1}$ if and only if $d_{G-W}(u,v)\geq 4e(H)$. Thus,

$e(G_{1})\geq\binom{|A|}{2}-Y\geq\frac{|A|^{2}}{4},$

and

$d(G_{1})\geq\frac{2e(G_{1})}{|A|}\geq\frac{|A|}{2}\geq\frac{d}{8}\geq\frac{\varepsilon}{8}e(H).$

Applying Lemma 3.5 with $\beta=\frac{1}{2}$ to $G_{1}$, we get a $TH^{(\leq
3)}$ in $G_{1}$, denoted as $Q$. Now we shall replace each edge of $Q$ with a
copy of $P_{3}$ in $G$. Let $V(Q)=\\{u_{1},u_{2},\ldots,u_{t}\\}$, and let
$f:V(Q)\rightarrow V(G)$ be any injective mapping. Suppose $u_{i}u_{j}$ is the
current edge for which we shall find a $f(u_{i}),f(u_{j})$-path of length $2$
whilst avoiding all internal vertices used in previous connections. Since
there are at most $2e(H)$ vertices in $N_{G-W}(u_{i})\cap N_{G-W}(u_{j})$ used
in previous connections, there exists an un-used common neighbors $u_{ij}$ of
$u_{i}$ and $u_{j}$, which forms a copy of $P_{3}$ in $G$. Thus we can find a
$TH^{(\leq 7)}$ in $G$. ∎

###### Proof of Lemma 3.6.

The proof is similar as the one in Section 4. We take $x=50$ and choose
$\frac{1}{h},\frac{1}{f},\frac{1}{r}\ll\frac{1}{K},\alpha,c\ll\frac{1}{\kappa},\varepsilon,\varepsilon_{1},\varepsilon_{2}<1$
and $n,d\in\mathbb{N}$ satisfy $\log^{s}n<d<\frac{n}{K}$. Let $H$ be an
$h$-vertex graph with $d(H)\geq K$ and the biseparability constraints as in
$(1)$-$(2)$ and $G$ be an $n$-vertex bipartite
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $\delta(G)=d\geq\varepsilon
e(H)$. Write $m=\log^{4}\frac{n}{d}$. Then we have $h\leq\frac{2d}{\varepsilon
d(H)}\leq\frac{\varepsilon_{1}\varepsilon_{2}d}{20}$ by the choice of $K$. We
further assume that $G$ is $(dm^{50},\frac{d}{2})$-dense as otherwise Lemma
6.1 implies $TH\subseteq G$ as desired.

Let $L_{G}:=\\{v\in V(G):d_{G}(v)\geq 2dm^{12}\\}$, where
$m=\log^{4}\frac{n}{d}$. We divide the proof into two cases depending on
whether there are many large degree vertices.

Case 1: $|L_{G}|\geq h$. Let $V(H)=\\{x_{1},\ldots,x_{h}\\}$ and
$E(H)=\\{e_{1},\ldots,e_{q}\\}$ with $q=e(H)$. Hence, we can take a set
$Z=\\{u_{1},\ldots,u_{h}\\}$ of $h$ distinct vertices in $L_{G}$. Let
$\tau:V(H)\rightarrow Z$ be an arbitrary injection. Note that for each
$i\in[h]$, the set $N(u_{i})$ has size at least $2dm^{12}$. Next we shall
construct a $TH$ by greedily finding a collection of internally vertex-
disjoint paths. Assume that we have pairwise internally disjoint paths of
length at most $2m$, say $P(e_{1}),\ldots,P(e_{t})$, such that $t\leq q$ and
each $P(e_{j})$ connects the two vertices in $\tau(e_{j})$ whilst $P(e_{j})$
is internally disjoint from $Z$.

Let $W=\bigcup_{j\in[t]}\mathsf{Int}(P(e_{j}))$ be the union of the interior
vertices of the paths. Then
$|W|+|Z|<2qm+h\leq\frac{1}{4}\rho(2dm^{12})2dm^{12}$. We can apply Lemma 2.13
to get a path $P$ avoiding $W\cup Z$ of length at most $m$, and extend $P$ to
obtain a path $P_{t+1}$ of length at most $m+2\leq 2m$. Repeating this for
$t=0,1,\ldots,q$ in order, we obtain $\bigcup_{j\in[q]}P_{j}$, which is an
$H$-subdivision in $G$.

Case 2: $|L_{G}|\leq h$. We choose $\frac{1}{K}\ll c_{0}\ll\varepsilon$ so
that $h\leq c_{0}d$. Denote by $\mathbf{L}=\\{v\in
V(H)|d(v)>\frac{d}{m^{10}}\\}$, $\mathbf{M}=\\{v\in V(H)\mid m^{2}\leq
d(v)\leq\frac{d}{m^{10}}\\}$ and $\mathbf{S}=\\{v\in V(H)\mid d(v)<m^{2}\\}$.
Note that

$2e(H)=\sum_{v\in V(H)}d_{H}(v)\geq|\mathbf{L}|\cdot\frac{d}{m^{10}},$

and thus $|\mathbf{L}|\leq\frac{2m^{10}}{\varepsilon}$.

As usual, we shall find units and webs for each vertex in $H$. First, Applying
Lemma 4.5 with $x=50,y=12,z=4$, we can greedily find a family of internally
vertex-disjoint webs $\\{Z_{v}\\}_{v\in\mathbf{M}}$, where $Z_{v}$ is a
$(22d_{H}(v),m^{8},\frac{dm^{4}}{20d_{H}(v)},4m)$-web and $2|\mathbf{S}|$
internally vertex-disjoint $(22m^{4},m^{8},\frac{d}{20},4m)$-webs
$Z_{1},\ldots,Z_{2|\mathbf{S}|}$. Indeed, this can be done by repeatedly
applying Lemma 4.5 to $G$ with $W_{0}$ being the set of internal vertices of
objects found so far and by the fact that

$|W_{0}|\leq\sum_{v\in\mathbf{M}}90d_{H}(v)m^{9}+44|\mathbf{S}|m^{13}\leq
180e(H)m^{9}+44hm^{13}<100dm^{13}.$

Next, we need the following claim.

######  Claim 6.2.

$G_{1}:=G-L_{G}$ is an $(\frac{\varepsilon_{1}}{2},\varepsilon_{2}d)$-expander
satisfying $\delta(G_{1})\geq\frac{d}{2}$ and $|G_{1}|\geq\frac{n}{2}$.

###### Proof.

Recall that $|L_{G}|\leq h<\varepsilon_{2}d$, then $|G_{1}|\geq
n-|L_{G}|\geq\frac{n}{2}$, and
$\delta(G_{1})\geq\delta(G)-|L_{G}|\geq\frac{d}{2}$. It remains to show that
$G_{1}$ is an $(\frac{\varepsilon_{1}}{2},\varepsilon_{2}d)$-expander. Since
$G$ is an $(\varepsilon_{1},\varepsilon_{2}d)$-expander and $\rho(x)x$ is
increasing when $x\geq\frac{\varepsilon_{2}d}{2}$, for any set $X$ in $G_{1}$
of size $x\geq\frac{\varepsilon_{2}d}{2}$ with
$x\leq\frac{|G_{1}|}{2}\leq\frac{|G|}{2}$, we have

$|N_{G}(X)|\geq
x\cdot\rho(x,\varepsilon_{1},\varepsilon_{2}d)\geq\frac{\varepsilon_{2}d}{2}\cdot\rho\left(\frac{\varepsilon_{2}d}{2},\varepsilon_{1},\varepsilon_{2}d\right)=\frac{\varepsilon_{2}d}{2}\cdot\frac{\varepsilon_{1}}{\log^{2}(\frac{15}{2})}\geq\frac{\varepsilon_{1}\varepsilon_{2}d}{10}\geq
2h.$

Hence,
$|N_{G_{1}}(X)|\geq|N_{G}(X)|-|L_{G}|\geq\frac{1}{2}|N_{G}(X)|\geq\frac{1}{2}x\cdot\rho(x,\varepsilon_{1},\varepsilon_{2}d)=x\cdot\rho\left(x,\frac{\varepsilon_{1}}{2},\varepsilon_{2}d\right)$
as desired. ∎

As $\Delta(G_{1})\leq 2dm^{12}$, applying Lemma 4.6 on $G_{1}$ with
$x=14,y=13,z=14$, we can greedily pick a family $\\{Z_{v}\\}_{v\in\mathbf{L}}$
of pairwise internally vertex-disjoint units such that $Z_{v}$ is a
$(c_{0}d,m^{13},2m)$-unit which are internally disjoint from the previously
obtained webs. This is possible because in the process, the union of $L_{G}$
and the interiors of all possible units or webs has size at most $dm^{14}$.

Denote by $z_{v}$ the core vertex of $Z_{v}$ for each
$v\in\mathbf{M}\cup\mathbf{L}$ and $z_{i}$ the core vertex of the web $Z_{i}$
for each $i\in[2|\mathbf{S}|]$. In addition,

$|\mathsf{Ext}(Z_{v})|=\begin{cases}c_{0}dm^{13},\quad\text{if
}v\in\mathbf{L},\\\ \frac{11dm^{12}}{10},\quad\text{if
}v\in\mathbf{M},\end{cases}\text{and}\quad|\mathsf{Ext}(Z_{i})|=\frac{11dm^{12}}{10},\quad\text{if
}i\in[2|\mathbf{S}|].$

Let $H_{1}$ be a spanning subgraph of $H$ with

$E(H_{1})=E(H[\mathbf{S}])\cup E(H[\mathbf{S},\mathbf{L}\cup\mathbf{M}]),$

and write $H_{2}=H\backslash E(H_{1})$. We shall find a mapping
$f:V(H)\rightarrow V(G)$ and a family of pairwise internally disjoint paths
respecting the adjacencies of $H$ in the following two rounds, where we may
abuse the notation $f$ as the up-to-date embedding. To begin, we embed every
$v\in\mathbf{L}\cup\mathbf{M}$ by taking $f(v)=z_{v}$.

First round: Finding the desired paths (in $G$) for the adjacencies in
$H_{1}$.

Let
$W=(\bigcup_{v\in\mathbf{L}\cup\mathbf{M}}\mathsf{Int}(Z_{v}))\cup(\bigcup_{i\in[2|\mathbf{S}|]}\mathsf{Ctr}(Z_{i}))$.
Then as $|\mathbf{L}|\leq\frac{m^{10}}{\varepsilon}$ and
$c_{0}\ll\varepsilon$, we have

$|W|\leq|\mathbf{L}|\cdot
2c_{0}dm+\sum_{v\in\mathbf{M}}88d_{H}(v)m^{9}+176|\mathbf{S}|m^{5}\leq
30dm^{11}.$

For a given vertex set $Y$ and $i\in[2|\mathbf{S}|]$, we say a web $Z_{i}$ is
$Y$-_good_ if $|\mathsf{Int}(Z_{i})\cap Y|\leq 11m^{12}$. To extend $f$ to
$V(H)$ whilst finding the desired paths for the adjacencies in $H_{1}$, we
define $(X,I,I^{\prime},\mathcal{Q},f)$ to be a good path system if the
followings hold.

  1. (F1)

$X\subseteq\mathbf{S}$ and $f$ injectively maps $X$ to
$I\subseteq[2|\mathbf{S}|]$.

  2. (F2)

$\mathcal{Q}$ is a collection of internally vertex-disjoint paths $Q_{x,y}$ of
length at most $13m$ for all edges $xy\in E(H_{1})$ touching $X$, such that
$Q_{x,y}$ is a $z_{f(x)},z_{f(y)}$-path disjoint from
$W\setminus(\mathsf{Int}(Z_{f(x)})\cup\mathsf{Int}(Z_{f(y)}))$.

  3. (F3)

In particular, $Q_{x,y}$ begins (or ends) with a subpath within the web
$Z_{f(x)}$ (resp. $Z_{f(y)}$) connecting the core $z_{f(x)}$ (resp.
$z_{f(y)}$) to $\mathsf{Ext}(Z_{f(x)})$, denoted as $P_{x}(y)$ (resp.
$P_{y}(x)$). Moreover, we write $Q_{x,y}^{\prime}$ for the middle segment of
$Q_{x,y}$, i.e. $Q_{x,y}^{\prime}=Q_{x,y}\setminus(P_{x}(y)\cup P_{y}(x))$ and
let $\mathcal{Q}^{\prime}$ be the family of these paths $Q_{x,y}^{\prime}$.

  4. (F4)

$I^{\prime}=\\{i\in[2|\mathbf{S}|]:Z_{i}\ \text{is}\ \text{not}\
V(\mathcal{Q}^{\prime})\text{-good}\\}$ and $I^{\prime}\cap I=\varnothing$.

Now we shall build a good path system with $X=\mathbf{S}$, and we proceed as
follows.

Step $0$. Fix an arbitrary ordering $\sigma$ on $\mathbf{S}$, say the first
vertex is $x_{1}$. Let $X_{1}=\\{x_{1}\\}$, $f(x_{1})=1$, $I_{1}=\\{1\\}$,
$I^{\prime}_{1}=\varnothing$ and $\mathcal{Q}_{1}=\varnothing$. Then
$(X_{1},I_{1},I^{\prime}_{1},\mathcal{Q}_{1},f|_{X_{1}})$ is a good path
system. Proceed to Step $1$.

Step $i$. Stop if either $X_{i}=\mathbf{S}$ or $I_{i}\cup
I^{\prime}_{i}=[2|\mathbf{S}|]$. Otherwise we continue:

  1. (G1)

Let $x$ be the first vertex in $\sigma$ on $\mathbf{S}\backslash X_{i}$.
Choose a $V(\mathcal{Q}^{\prime}_{i})$-good web $Z_{t}$ with
$t\in[2|\mathbf{S}|]\backslash(I_{i}\cup I^{\prime}_{i})$ and let $f(x)=t$.

  2. (G2)

Find internally vertex-disjoint paths $Q_{x,y}$ for every neighbor $y$ of $x$
in $X_{i}\cup\mathbf{L}\cup\mathbf{M}$ satisfying (F2)-(F3). Once this is
done, we add these paths to $\mathcal{Q}_{i}$ to get $\mathcal{Q}_{i+1}$.

  3. (G3)

Update bad webs
$I^{\prime}_{i+1}=\\{i^{\prime}\in[2|\mathbf{S}|]:Z_{i^{\prime}}\ \text{is}\
\text{not}\ V(\mathcal{Q}^{\prime}_{i+1})\text{-}\text{good}\\}$ as
$I_{i+1}=I_{i}\cup\\{t\\}\backslash I^{\prime}_{i+1}$,
$X_{i+1}=f^{-1}(I_{i+1})$ and replace $f$ with its restriction $f|_{X_{i+1}}$.

  4. (G4)

Proceed to Step $(i+1)$ with a good path system
$(X_{i+1},I_{i+1},I^{\prime}_{i+1},\mathcal{Q}_{i+1},$ $f|_{X_{i+1}})$.

Now we give the following claim and postpone its proof later.

######  Claim 6.3.

In each step the desired paths in _( G2)_ can be successfully found.

By Claim 6.3, $|I_{i}\cup I^{\prime}_{i}|$ is strictly increasing at each step
and the above process must terminate in at most $2|\mathbf{S}|$ steps. Let
$(X,I,I^{\prime},\mathcal{Q},f)$ be the final good path system returned from
the above process and $\mathcal{Q}^{\prime}$ be given as in (F3). Note that
the sequence $|X_{1}|,|X_{2}|,\ldots$ might not be an increasing sequences, as
we may delete some elements when updating the list of bad webs in each step.
Next we show that the process must terminate with $X=\mathbf{S}$.

Note that for each $v\in\mathbf{L}\cup\mathbf{M}$, $Z_{v}$ is
$V(\mathcal{Q}^{\prime})$-good, and $\mathcal{Q}^{\prime}$ might contain some
paths whose vertex set intersects
$\mathsf{Int}(Z_{i^{\prime}})\backslash\mathsf{Ctr}(Z_{i^{\prime}})$ with
$i^{\prime}\in I^{\prime}$. As at most $m^{2}$ paths are added at each step,
we have $|I^{\prime}|\leq\frac{2|\mathbf{S}|m^{2}\cdot
13m}{11m^{12}}=\frac{26|\mathbf{S}|}{11m^{9}}<|\mathbf{S}|$. Thus, $|I\cup
I^{\prime}|<2|\mathbf{S}|$, and then the process terminates with
$X=\mathbf{S}$. To complete the proof, it remains to show that all connections
in (G2) can be guaranteed in each step.

###### Proof of Claim 6.3.

Given a good path system
$(X_{i},I_{i},I_{i}^{\prime},\mathcal{Q}_{i},f|_{X_{i}})$ and
$x\in\mathbf{S}\backslash X_{i}$, $Z_{f(x)}$ as in (G1), we let
$\\{y_{1},\ldots,y_{s}\\}=N_{H_{1}}(x)\cap(X_{i}\cup\mathbf{L}\cup\mathbf{M})$.
For $j\in f(X_{i}\cup\\{x\\})$, we know that $Z_{j}$ is
$V(\mathcal{Q}_{i})$-good as $(X_{i},I_{i},I^{\prime}_{i},\mathcal{Q}_{i},f)$
is a good path system. By (F3), $V(\mathcal{Q}_{i})$ is disjoint from $W$.
Denote by $Z_{|\mathbf{M}|+1},\ldots,Z_{|\mathbf{M}|+2|\mathbf{S}|}$ the
$2|\mathbf{S}|$ webs we found as above. Note that there are at most $m^{2}$
paths in $\mathsf{Ctr}(Z_{j})$
$(j\in[|\mathbf{M}|+1,|\mathbf{M}|+2|\mathbf{S}|])$ are involved in precious
connections. Hence, there are at least
$(22m^{2}-m^{2})m^{10}-11m^{12}=10m^{12}$ available paths in
$\mathsf{Int}(Z_{j})\backslash\mathsf{Ctr}(Z_{j})$, and their corresponding
paths in $\mathsf{Ctr}(Z_{j})$ are disjoint from $V(\mathcal{Q}_{i})$. Let
$U_{j}\subseteq\mathsf{Ext}(Z_{j})$ be the union of the leaves of the stars
corresponding to these available paths. Then $|U_{j}|\geq dm^{12}$. Hence,
$U^{\prime}_{j}=dm^{12}$ for each $j\in f(X_{i}\cup\\{x\\})$. However, for
each $j\in[s]$, we have
$|W\cup\mathsf{Int}(Z_{f(x)})\cup\mathsf{Int}(Z_{f(y_{j})})\cup
V(\mathcal{Q}_{i})|\leq 30dm^{11}+2\cdot
22m^{12}+15m|\mathcal{Q}|\leq\frac{\rho(dm^{12})dm^{12}}{4}$ (if $Z_{k}$ is a
web with $k\in[|\mathbf{M}|]$, then $\mathsf{Int}(Z_{k})=0$ in this
inequality). Similarly, the case when $Z_{f(y)}$ is a
$(c_{0}d,m^{13},2m)$-unit, also witnesses such a vertex set
$U_{y}\subseteq\mathsf{Ext}(Z_{f(y)})$ of size at least $dm^{12}$. Thus, we
can find the desired path $Q_{f(x),f(y_{j})}$ connecting $Z_{f(x)}$ and
$Z_{f(y_{j})}$ while avoiding
$W\cup\mathsf{Int}(Z_{f(x)})\cup\mathsf{Int}(Z_{f(y_{j})})\cup
V(\mathcal{Q}_{i})$. ∎

Second round: Finding the desired paths (in $G$) for the adjacencies in
$H_{2}$.

Let $\mathcal{Q}$ be the resulting family of paths for the adjacencies in
$H_{1}$ and $f$ be the resulting embedding of $V(H)$ returned from the first
round. Note that $|V(\mathcal{Q})|\leq 13m\cdot e(H_{1})\leq 13m\cdot
e(H)<13dm^{2}$. As the arguments as above,
$V(\mathcal{Q})\cap(\bigcup_{v\in\mathbf{L}\cup\mathbf{M}}\mathsf{Int}(Z_{v}))=\varnothing$.
Further, $|\mathsf{Ext}(Z_{v})|\geq dm^{12}$ for each
$v\in\mathbf{L}\cup\mathbf{M}$. Let
$W^{*}=V(\mathcal{Q})\cup(\bigcup_{v\in\mathbf{L}\cup\mathbf{M}}\mathsf{Int}(Z_{v}))$,
then $|W^{*}|\leq 30dm^{10}$.

Let $I\subseteq E(H_{2})$ be a maximum set of edges for which there exists a
collection $\mathcal{P}_{I}=\\{P_{e}:e\in I\\}$ of internally vertex-disjoint
paths under the following rules.

  1. (H1)

For each $xy=e\in E(H_{2})$, $P_{e}$ is a $z_{f(x)},z_{f(y)}$-path of length
at most $13m$ and $P_{e}$ is disjoint from
$W^{*}\backslash(\mathsf{Int}(Z_{f(x)})\cup\mathsf{Int}(Z_{f(y)}))$.

  2. (H2)

$P_{e}$ begins (or ends) with the unique subpath within the web $Z_{f(x)}$
(resp. $Z_{f(y)}$) connecting the core vertex $z_{f(x)}$ (resp. $z_{f(y)}$)
and some vertex in $\mathsf{Ext}(Z_{f(x)})$.

Observe that every $v\in\mathbf{L}$ witnesses at least $c_{0}d-d_{H}(v)$
available branches in the unit $Z_{f(v)}$ and every $v\in\mathbf{M}$ witnesses
at least $22d_{H}(v)-d_{H}(v)$ branches in $\mathsf{Ctr}(Z_{f(v)})$, which are
internally disjoint from $V(\mathcal{Q}\cup\mathcal{P}_{I})$. For every
$x\in\mathbf{L}\cup\mathbf{M}$, let $V_{x}\subseteq\mathsf{Ext}(Z_{x})$ be the
union of the leaves from the pendant stars attached to one end of these
available paths. Then
$|V_{x}|\geq\min\\{(c_{0}d-d_{H}(v))m^{13},\frac{21dm^{12}}{10}\\}\geq
dm^{12}$.

######  Claim 6.4.

$I=E(H_{2})$.

###### Proof of Claim 6.4.

Suppose to the contrary that there exists an edge $e=xy\in E(H_{2})\backslash
I$ with no paths in $\mathcal{P}_{I}$ between their corresponding webs, say
$Z_{f(x)},Z_{f(y)}$. Then $|\mathcal{P}_{I}|\leq 13dm^{2}$, and
$|W^{*}|+|\mathcal{P}_{I}|\leq
30dm^{10}+13dm^{2}<32dm^{10}<\frac{1}{4}\rho(dm^{12})dm^{12}$. By Lemma 2.13,
there is a path $P_{e}^{\prime}$ of length at most $m$ between
$\mathsf{Ext}(Z_{f(x)})$ and $\mathsf{Ext}(Z_{f(y)})$ while avoiding
$W^{*}\cup V(\mathcal{P}_{I})$, and we can easily extend $P_{e}^{\prime}$ into
a path $P_{e}$ of length at most $13m$ connecting $z_{f(x)}$ and $z_{f(y)}$.
Hence, $\\{P_{e}\\}\cup\mathcal{P}_{I}$ yields a contradiction to the
maximality of $\mathcal{P}_{I}$. ∎

In conclusion, the resulting families of paths $\mathcal{Q}$ in the first
round and $\mathcal{P}_{I}$ in the second round form a copy of $TH$ as
desired. ∎

## References

  * [1] N. Alon, P. Seymour, R. Thomas, A separator theorem for graphs with an excluded minor and its applications, in Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, 1990, 293¨C299.
  * [2] N. Alon, M. Krivelevich, B. Sudakov, Turán numbers of bipartite graphs and related Ramsey-type questions, Combinatorics, Probability and Computing, 2003, 12: 477-494.
  * [3] J. Balogh, H. Liu, M. Sharifzadeh, Subdivisions of a large clique in $C_{6}$-free graphs, Journal of Combinatorial Theory, Series B, 2015, 112: 18-35.
  * [4] B. Bollobás, A. Thomason, Highly linked graphs, Combinatorica, 1996, 16(3): 313-320.
  * [5] B. Bollobás, A. Thomason, Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs, European Journal of Combinatorics, 1998, 19: 883-887.
  * [6] P. Catlin, Hajós’ graph-coloring conjecture: variations and counterexamples, Journal of Combinatorial Theory, Series B, 1979, 26: 268-274.
  * [7] E. Csóka, I. Lo, S. Norin, H. Wu, L. Yepremyan, The extremal function for disconnected minors. Journal of Combinatorial Theory, Series B, 2017, 121: 162¨C174.
  * [8] R. Diestel, Graph Theory, Fifth Edition, Springer, 2016.
  * [9] G. Dirac, A property of $4$-chromatic graphs and some remarks on critical graphs, Journal of the London Mathematical Society, 1952, 27: 85-92.
  * [10] Z. Dvořák, S. Norin, Strongly sublinear separators and polynomial expansion, 2015, arXiv:1504.04821.
  * [11] Z. Dvořák, S. Norin, Islands in minor-closed classes. I. Bounded treewidth and separators, 2017, arXiv:1710.02727.
  * [12] K. Edwards, C. Mcdiarmid, New upper bounds on harmonious colorings, Journal of Graph Theory, 1994, 18(3): 257-267.
  * [13] P. Erdős, Problems and results in graph theory and combinatorial analysis, In Graph Theory and related topics, J. A. Bondy, U. S. R. Murty (Editors), Academic Press, New York, 1979, pp: 153-163.
  * [14] P. Erdős, S. Fajtlowicz, On the conjecture of Hajós, Combinatorica, 1981, 1: 141-143.
  * [15] J. Fox, B. Sudakov, Dependent random choice, Random Structures and Algorithms, 2011, 38: 68-99.
  * [16] I. Gil-Fernández, J. Hyde, H. Liu, O. Pikhurko, Z. Wu, Disjoint isomorphic balanced clique subdivisions, Journal of Combinatorial Theory, Series B, 2023, 161: 417-436.
  * [17] J. Haslegrave, J. Kim, H. Liu, Extremal density for sparse minors and subdivisions, International Mathematics Research Notices, 2022, 2022(20): 15505-15548.
  * [18] K. Hendrey, S. Norin, D.R. Wood, Extremal functions for sparse minors, Advances in Combinatorics, 2022, 5: 1-43.
  * [19] P. W. Holland, K. B. Laskey, S. Leinhardt, Stochastic blockmodels: First steps, Social Networks, 1983, 5(2): 109¨C137.
  * [20] S. Im, J. Kim, Y. Kim, H. Liu, Crux, space constraints and subdivisions, arXiv:2207.06653v1, 2022.
  * [21] H. A. Jung, Eine Verallgemeinerung des $n$-fachen Zusammenhangs für Graphen, Mathematische Annalen, 1970, 187: 95-103.
  * [22] K. Kawarabayashi, B. Reed, A separator theorem in minor-closed classes, in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010.
  * [23] J. Kim, H. Liu, M. Sharifzadeh, K. Staden, Proof of Komlós’s conjecture on Hamiltonian subsets, Electronic Notes in Discrete Mathematics, 2017, 61: 727-733.
  * [24] J. Komlós, E. Szemerédi, Topological cliques in graphs, Combinatorics, Probability and Computing, 1994, 3: 247-256.
  * [25] J. Komlós, E. Szemerédi, Topological cliques in graphs II, Combinatorics, Probability and Computing, 1996, 5: 79-90.
  * [26] A. V. Kostochka, Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica, 1984, 4(4): 307¨C316.
  * [27] A. V. Kostochka, N. Prince, On $K_{s,t}$-minors in graphs with given average degree. Discrete Mathematics, 2008, 308(19): 4435¨C4445.
  * [28] T. Kővári, V. T. Sós, P. Turán, On a problem of K. Zarankiewicz, Colloquium Mathematicum, 1954, 3: 50¨C57.
  * [29] D. Kühn, D. Osthus, Topological minors in graphs of large girth, Journal of Combinatorial Theory, Series B, 2002, 86: 364-380.
  * [30] D. Kühn, D. Osthus, Forcing unbalanced complete bipartite minors. European Journal of Combinatorics, 2005, 26(1): 75¨C81.
  * [31] D. Kühn, D. Osthus, Improved bounds for topological cliques in graphs of large girth, SIAM Journal on Discrete Mathematics, 2006, 20: 62-78.
  * [32] K. Kuratowski, Sur le, problème des courbes gauches en topologie, Fundamenta Mathematica, 1930, 15: 271-283.
  * [33] C. Lee, Ramsey numbers of degenerate graphs, Annals of Mathematics, 2017, 185: 791-829.
  * [34] H. Liu, R. Montgomery, A proof of Mader’s conjecture on large clique subdivisions in $C_{4}$-free graphs, Journal of the London Mathematical Society, 2017, 95(2): 203-222.
  * [35] H. Liu, R. Montgomery, A solution to Erdős and Hajnal’s odd cycle problem, Journal of the American Mathematical Society, 2023, 36(4): 1191-1234.
  * [36] B. Luan, Y. Tang, G. Wang, D. Yang, Balanced subdivisions of cliques in graphs, Combinatorica, 2023, 43(5): 885-907.
  * [37] W. Mader, Homomorphieegenschaften und mittlere Kantendichte von Graphen, Mathematische Annalen, 1967, 174: 265-268.
  * [38] W. Mader, Existenz $n$-fach zusammenhängender Teilgraphen in Graphen genügend grosser Kantendichte, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 1972, 37: 86¨C97.
  * [39] W. Mader, An extremal problem for subdivisions of $K^{-}_{5}$, Journal of Graph Theory, 1999, 30: 261-276.
  * [40] E. Szemerédi, Regular Partitions of Graphs. In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Paris: éditions du Centre National de la Recherche Scientifique (CNRS), pp. 399-401, 1978.
  * [41] A. Thomason. An extremal function for contractions of graphs, Mathematical Proceedings of the Cambridge Philosophical Society, 1984, 95(2): 261¨C265.
  * [42] A. Thomason, M. Wales, On the extremal function for graph minors, Journal of Graph Theory, 2022, 95(2): 261-265.
  * [43] C. Thomassen, Subdivisions of graphs with large minimum degree, Journal of Graph Theory, 1984, 8: 23-28.
  * [44] Y. Wang, Balanced subdivisions of a large clique in graphs with high average degree, SIAM Journal on Discrete Mathematics, 2023, 37: 1262-1274.
  * [45] A. T. White, The genus of repeated Cartesian products of bipartite graphs, Transactions of the American Mathematical Society, 1970, 151(2): 393-404.
  * [46] D. R. Wood, Defective and clustered graph colouring, The Electronic Journal of Combinatorics, 2018, DS23.

##  Appendix A Proof of Proposition 2.12 and Lemma 4.8

###### Proof of Proposition 2.12.

Suppose to the contrary that $|B_{G}^{m}(v)|<\frac{n}{2}$. Observe that
$|B_{G}^{1}(v)|\geq d(v)\geq\varepsilon_{2}d$. By the expansion property, we
have

$|B_{G}^{i}(v)|\geq|B_{G}^{i-1}(v)|\big{(}1+\rho(|B_{G}^{i-1}(v)|)\big{)},$

whence

$\frac{n}{2}>|B_{G}^{m}(v)|\geq|B_{G}^{1}(v)|\prod_{j=1}^{m-1}\big{(}1+\rho(|B_{G}^{j}(v)|)\big{)}\geq|B_{G}^{1}(v)|\left(1+\frac{\rho(n)}{2}\right)^{m-1}.$

Then

$m\leq\frac{\log(\frac{n}{\varepsilon_{2}d})}{\log(1+\rho(n))}+1<\log^{3}\frac{n}{d},$

which contradicts to the choice of $m$ (recall that $m$ is the smallest even
integer which is larger than $\log^{4}\frac{n}{d}$). ∎

###### Proof of Lemma 4.8.

Given $\varepsilon_{1},\varepsilon_{2},s,x$ such that $s\geq 8x$, we choose
$\frac{1}{K}\ll c\ll\varepsilon_{1},\varepsilon_{2}$. Let $H$ be an $n$-vertex
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $\delta(H)\geq\frac{d}{2}$,
and $P_{1},\ldots,P_{t}$ be consecutive shortest paths from $v$ in
$B_{H}^{m}(v)$. Let $F=H-(U\backslash\\{v\\})$. We shall show by induction on
$p\geq 1$ that, if $|B_{F}^{p}(v)|\leq dm^{x}$ and $p<m$, then

$|N_{F}(B_{F}^{p}(v))|\geq\frac{1}{2}|B_{F}^{p}(v)|\cdot\rho(|B_{F}^{p}(v)|).$
(5)

Also, we will show that $|B^{1}_{F}(v)|\geq\frac{d}{10}$, which together with
this inductive statement will prove the lemma. Actually, we may take these
conclusions for granted, and assume that $|B_{F}^{p}(v)|\leq dm^{x}$, then for
each $1\leq p<m$, we have

$\displaystyle|N_{F}(B_{F}^{p}(v))|$
$\displaystyle\geq\frac{1}{2}|B_{F}^{p}(v)|\cdot\rho(|B_{F}^{p}(v)|)=\frac{\varepsilon_{1}|B_{F}^{p}(v)|}{2\log^{2}\left(\frac{15|B_{F}^{p}(v)|}{\varepsilon_{2}d}\right)}$
$\displaystyle\geq|B_{F}^{p}(v)|\cdot\frac{\varepsilon_{1}}{2\log^{2}\left(\frac{15dm^{x}}{\varepsilon_{2}d}\right)}\geq\frac{|B_{F}^{p}(v)|}{\log^{3}(m^{x})},$

where we have used that
$|B_{F}^{p}(v)|\geq|B_{F}^{1}(v)|\geq\frac{d}{10}>\frac{\varepsilon_{2}d}{2}$
to apply the expansion property. Hence, we have

$\displaystyle|B_{F}^{m}(v)|$
$\displaystyle>\left(1+\frac{1}{\log^{3}(m^{x})}\right)^{m-1}|B^{1}_{F}(v)|\geq\frac{d}{10}\left(1+\frac{1}{\log^{3}(m^{x})}\right)^{m-1}$
$\displaystyle\geq\frac{d}{10}e^{\frac{m-1}{2\log^{3}(m^{x})}}>de^{\log(m^{x})}=dm^{x},$

where the last inequality follows as $\frac{n}{d}$ and also $m$ are
sufficiently large.

Thus, we only need to prove the inductive statement and
$|B^{1}_{F}(v)|\geq\frac{d}{10}$. As the paths $P_{i}$ are consecutive
shortest paths from $v$ in $B^{m}_{H}(v)$, only the first $p+2$ vertices of
each path $P_{i}$, including $v$, can belong to
$N_{H}(B_{H-\cup_{j<i}(V(P_{j})\backslash\\{v\\})}^{p}(v))$. Hence, if $p<m$,
then only the first $p+2$ vertices of each of the path $P_{i}$, including the
vertex $v$, can belong to $N_{H}(B_{F}^{p}(v))$. On the other hand, as we have
at most $cd$ paths $P_{i}$, if $p<m$, then
$|N_{H}(B_{F}^{p}(v))\cap(U\backslash\\{v\\})|\leq(p+1)cd$, so that

$|N_{H-F}(B_{F}^{p}(v))|\leq(p+1)cd.$ (6)

In particular, when $p=0$, the inequality (6) implies that
$|N_{F}(v)|\geq|N_{H}(v)|-cd\geq\delta(H)-cd\geq\frac{d}{2}-cd\geq\frac{d}{10}$.
Hence, $|B^{1}_{F}(v)|\geq|N_{F}(v)|\geq\frac{d}{10}$.

Next we aim to prove (5). When $p=1$, by (6), we have

$|N_{F}(B_{F}^{1}(v))|\geq|N_{H}(B_{F}^{1}(v))|-2cd.$ (7)

However, by the choice of $c$,
$2cd\leq\frac{1}{2}\rho(\frac{d}{10})\cdot\frac{d}{10}\leq\frac{1}{2}\rho(|B^{1}_{F}(v)|)\cdot|B^{1}_{F}(v)|$.
Thus, (7) becomes

$\displaystyle N_{F}(B_{F}^{1}(v))$
$\displaystyle\geq|N_{H}(B_{F}^{1}(v))|-\frac{1}{2}\rho(|B^{1}_{F}(v)|)\cdot|B^{1}_{F}(v)|$
$\displaystyle>\frac{1}{2}\rho(|B^{1}_{F}(v)|)\cdot|B^{1}_{F}(v)|,$

where the last inequality holds because
$|N_{H}(B_{F}^{1}(v))|>\rho(|B^{1}_{F}(v)|)\cdot|B^{1}_{F}(v)|$. When $p\geq
2$. Suppose that (5) holds for all $1\leq p^{\prime}<p$. Now by (6), it
remains to prove that

$(p+1)cd\leq\frac{1}{2}\rho(|B_{F}^{p}(v)|)\cdot|B_{F}^{p}(v)|.$ (8)

Let $\alpha$ be defined by $|B_{F}^{p}(v)|=\frac{\alpha\varepsilon_{2}d}{15}$
and note that $\alpha\geq 3$. Then
$\rho(|B_{F}^{p}(v)|)=\frac{\varepsilon_{1}}{\log^{2}\alpha}$. By the
induction hypothesis, we have

$\left(1+\frac{\varepsilon_{1}}{2\log^{2}\alpha}\right)^{p-1}\leq\frac{|B_{F}^{p}(v)|}{|B^{1}_{F}(v)|}\leq\frac{\alpha\varepsilon_{2}d}{15}\cdot\frac{10}{d}=\frac{2}{3}\alpha\varepsilon_{2}<\alpha.$

Thus,

$p-1\leq\frac{\log\alpha}{\log\left(1+\frac{\varepsilon_{1}}{2\log^{2}\alpha}\right)}\leq\frac{\log\alpha}{\frac{1}{2}\cdot\frac{\varepsilon_{1}}{2\log^{2}\alpha}}=\frac{4\log^{3}\alpha}{\varepsilon_{1}},$

where the last inequality holds as $\log(1+x)\geq\frac{x}{2}$ for all $0<x<1$.
Note that when $\alpha\geq 3$, $\frac{\log^{5}\alpha}{\alpha}$ is bounded by
some universal constant, say $L$. Therefore

$\displaystyle(p+1)cd$
$\displaystyle\leq\frac{8\log^{3}\alpha}{\varepsilon_{1}}\cdot
cd\leq\frac{8cd}{\varepsilon_{1}}\cdot\frac{L\alpha}{\log^{2}\alpha}=\frac{120cL}{\varepsilon_{1}\varepsilon_{2}}\cdot\frac{\alpha\varepsilon_{2}d}{15\log^{2}\alpha}$
$\displaystyle=\frac{120cL}{\varepsilon_{1}^{2}\varepsilon_{2}}\cdot\rho(|B_{F}^{p}(v)|)\cdot|B_{F}^{p}(v)|\leq\frac{1}{2}\rho(|B_{F}^{p}(v)|)\cdot|B_{F}^{p}(v)|,$

for $c$ sufficiently small depending on $\varepsilon_{1},\varepsilon_{2}$ and
$L$, and so the inequality (8) holds. ∎

##  Appendix B Proof of Lemma 4.5: finding webs

###### Proof of Lemma 4.5.

Recall that $G$ is a $(dm^{x},\frac{d}{2})$-dense bipartite
$(\varepsilon_{1},\varepsilon_{2}d)$-expander, and $W\subseteq V(G)$ with
$|W|\leq 100dm^{x-2y+z-4}$. We first prove that the following holds.

######  Claim B.1.

For any set $X$ of size at most $dm^{x}$, the graph $G-X$ contains a star $S$
with at least $\frac{d}{4}$ leaves. In particular, the center vertex of $S$
lies in $V_{1}$.

###### Proof of Claim B.1.

By the assumption that $G$ is $(dm^{x},\frac{d}{2})$-dense, we have
$d(G-X)\geq\frac{d}{2}$. Let $V^{\prime}_{1}=V_{1}\backslash X$ and
$V^{\prime}_{2}=V_{2}\backslash X$. Since

$\frac{\sum_{v\in
V^{\prime}_{1}}d(v)}{|V^{\prime}_{1}|}=\frac{|E(G-X)|}{|V^{\prime}_{1}|}>\frac{d(G-X)}{2}\geq\frac{d}{4}.$

Hence, $G-X$ contains a star $S$ with $\frac{d}{4}$ leaves, whose center
vertex lies in $V_{1}$. ∎

Recall that our main goal is to construct a web in $G-W$. We shall first build
many vertex-disjoint units as follows.

######  Claim B.2.

The graph $G-W$ contains $100\gamma m^{x-2y+z-3}$ vertex-disjoint
$(2m^{y-z},\frac{dm^{z}}{10\gamma},m+2)$-units.

###### Proof of Claim B.2.

Suppose we have found a collection of units $F_{1},\ldots,F_{t}$ as desired
for some $0\leq t<100\gamma m^{x-2y+z-3}$. Then the set
$X^{\prime}:=\bigcup_{i\in[t]}V(F_{i})$ has size at most $21dm^{x-y+z-3}$ and
$|X^{\prime}\cup W|\leq 22dm^{x-1}<dm^{x}$. By Claim B.1, we can find vertex-
disjoint stars $S_{1},\ldots$, $S_{m^{x-y+z-2}}$, $T_{1},\ldots,$ $T_{\gamma
m^{x-z-1}}$ with centers $u_{1},\ldots,u_{m^{x-y+z-2}}$,
$v_{1},\ldots,v_{\gamma m^{x-z-1}}$, respectively in $G-W-X^{\prime}$ such
that all centers lie in $V_{1}$ and each $S_{i}$ has exactly $\frac{d}{4}$
leaves and each $T_{i}$ has exactly $\frac{dm^{z}}{5\gamma}$ leaves. This can
be done because $|\bigcup_{i\in[m^{x-y+z-2}]}V(S_{i})|+|\bigcup_{i\in[\gamma
m^{x-z-1}]}V(T_{i})|+|W|+|X^{\prime}|\leq dm^{x}$. For simplicity, set
$Z=\\{u_{1},\ldots,u_{m^{x-y+z-2}},$ $v_{1},\ldots,v_{\gamma m^{x-z-1}}\\}$.

Let $\mathcal{P}$ be a maximum collection of internally disjoint paths
$P_{ij}$ in $G-W-X^{\prime}$ satisfying the following rules.

  1. (I1)

Each path $P_{ij}$ in $\mathcal{P}$ is a unique $u_{i},v_{j}$-path of length
at most $m+2$.

  2. (I2)

Each $P_{ij}$ does not contain any vertex in $Z$ as an internal vertex.

Now we claim that there is a center $u_{i}$ connected to at least $2m^{y-z}$
distinct centers $v_{j}$ via the paths in $\mathcal{P}$. Suppose to the
contrary that every $u_{i}$ is connected to less than $2m^{y-z}$ centers
$v_{j}$. Then $|\mathcal{P}|\leq 2m^{x-2}$ and $|V(\mathcal{P})|\leq
2m^{y-z}\cdot(m+2)\cdot m^{x-y+z-2}\leq 4m^{x-1}$. Let

$U:=\left(\bigcup_{i\in[m^{x-y+z-2}]}(S_{i}\backslash\\{u_{i}\\})\right)\backslash
V(\mathcal{P}),$

and $V$ be the set of leaves of all stars $T_{i}$ whose centers are not used
as endpoints of paths in $\mathcal{P}$. Then we have

$|U|\geq\frac{d}{4}\cdot m^{x-y+z-2}-4m^{x-1}>\frac{dm^{x-y+z-2}}{10},$ (9)

and

$|V|\geq\frac{dm^{z}}{5\gamma}\cdot(\gamma
m^{x-z-1}-2m^{x-2})\geq\frac{dm^{z}}{5\gamma}\cdot\frac{1}{2}\gamma
m^{x-z-1}=\frac{dm^{x-1}}{10}>\frac{dm^{x-y+z-2}}{10},$ (10)

where (10) follows as $\gamma\geq m^{z}$ and $y>z$. On the other hand,

$\displaystyle|W|+|X^{\prime}|+|\mathsf{Int}(\mathcal{P})|+|Z|$
$\displaystyle\leq 100dm^{x-2y+z-4}+21dm^{x-y+z-3}+4m^{x-1}+m^{x-y+z-2}+\gamma
m^{x-z-1}$ (11)
$\displaystyle\leq\frac{1}{4}\rho\left(\frac{dm^{x-y+z-2}}{10}\right)\cdot\frac{dm^{x-y+z-2}}{10}.$

The last inequality in (11) holds as $y<z+10$. Hence, applying Lemma 2.13 with
$U,V,W\cup X^{\prime}\cup\mathsf{Int}(\mathcal{P})\cup Z$ playing the roles of
$X_{1},X_{2},W$, respectively, we obtain vertices $x_{k_{1}}\in U,x_{k_{2}}\in
V$ and a path of length at most $m$ connecting $x_{k_{1}}$ and $x_{k_{2}}$
whilst avoiding vertices in $W\cup X^{\prime}\cup\mathsf{Int}(\mathcal{P})\cup
Z$. Denote by $S_{k_{1}},T_{k_{2}}$ the stars which contain
$x_{k_{1}},x_{k_{2}}$ as leaves, respectively. This yields a
$u_{k_{1}},v_{k_{2}}$-path $P_{k_{1},k_{2}}$, which is internally disjoint
from $W\cup X^{\prime}\cup\mathsf{Int}(\mathcal{P})\cup Z$. Hence,
$P_{k_{1},k_{2}}$ satisfies (I1) and (I2), a contradiction to the maximum of
$\mathcal{P}$.

Therefore, there exists a center $u_{i}$ connected to $2m^{y-z}$ distinct
centers $v_{j}$, say $v_{1},\ldots v_{2m^{y-z}}$, which correspond to stars
$T_{1},\ldots T_{2m^{y-z}}$. Recall that all stars in $\\{T_{1},\ldots
T_{2m^{y-z}}\\}$ are vertex-disjoint and the number of vertices in all
$P_{i,j}$ $(j\in[2m^{y-z}])$ is at most
$2m^{y-z}(m+2)<\frac{dm^{z}}{10\gamma}\leq\frac{1}{2}e(T_{i})$ (as $y<2z+9$
and $\gamma<\frac{d}{m^{10}}$). Hence, every $T_{j}$ $(j\in[2m^{y-z}])$ has at
least $\frac{dm^{z}}{10\gamma}$ leaves that are not used in $P_{i,j}$ for any
$j\in[2m^{y-z}]$. These stars, together with the corresponding paths to
$u_{i}$, form a desired unit in $G-W-X^{\prime}$. Thus, we can greedily pick
vertex-disjoint units as above. ∎

Applying Claim B.2, we get pairwise vertex-disjoint
$(2m^{y-z},\frac{dm^{z}}{10\gamma},m+2)$-units $F_{1},\ldots,$ $F_{t}$ with
$t=100\gamma m^{x-2y+z-3}$, and denoted by $u_{i}$ the core vertex of $F_{i}$.
Let $Y=\bigcup_{i\in[t]}V(F_{i})$ and
$Y^{\prime}=\bigcup_{i\in[t]}\mathsf{Int}(F_{i})$. Since
$m^{z}\leq\gamma<\frac{d}{m^{10}}$, we have

$\displaystyle|Y|$ $\displaystyle\leq 100\gamma
m^{x-2y+z-3}\left(2m^{y-z}(m+2+\frac{dm^{z}}{10\gamma})\right)$
$\displaystyle=200\gamma m^{x-y-3}(m+2)+20dm^{x-y+z-3}$ $\displaystyle\leq
21dm^{x-y+z-3},$

and

$|Y^{\prime}|\leq 100\gamma m^{x-2y+z-3}\cdot 2m^{y-z}=200\gamma m^{x-y-3}.$

By Claim B.1, we can greedily find $m^{x-2y+z-3}$ disjoint stars
$S_{1},\ldots,S_{m^{x-2y+z-3}}$ which are disjoint from $W\cup Y$, where each
$S_{i}$ has exactly $\frac{d}{4}$ leaves and its center vertex, say $v_{i}$,
lies in $V_{1}$. For simplicity, let
$Z=\\{v_{1},\ldots,v_{m^{x-2y+z-3}},u_{1},\ldots,u_{t}\\}$.

Let $\mathcal{Q}$ be a maximum collection of internally disjoint paths
$Q_{ij}$ satisfying the following rules.

  1. (J1)

Each path $Q_{ij}$ in $\mathcal{Q}$ is a unique $v_{i},u_{j}$-path of length
at most $4m$.

  2. (J2)

Each $Q_{ij}$ does not contain any vertex in $W\cup
Z\cup(Y^{\prime}\backslash(\mathsf{Int}(F_{i})\cup\mathsf{Int}(F_{j})))$ as an
internal vertex.

######  Claim B.3.

There is a center $v_{i}$ connected to at least $44\gamma$ distinct centers
$u_{j}$ via the paths in $\mathcal{Q}$.

###### Proof of Claim B.3.

Suppose to the contrary that each $v_{i}$ is connected to less than $44\gamma$
centers $u_{j}$. Then $|\mathcal{Q}|\leq 44\gamma m^{x-2y+z-3}$ and
$|V(\mathcal{Q})|\leq 44\gamma m^{x-2y+z-3}\cdot 4m=176\gamma m^{x-2y+z-2}$.
Let

$V:=\left(\bigcup_{i\in[m^{x-2y+z-3}]}(S_{i}\backslash\\{v_{i}\\})\right)\backslash
V(\mathcal{Q})$

and $U$ be the set of exteriors of all units $F_{i}$ whose centers are not
used as endpoints of path $Q_{ij}$ in $\mathcal{Q}$. Then we have

$|V|=\frac{dm^{x-2y+z-3}}{4}-176\gamma m^{x-2y+z-2}>\frac{dm^{x-2y+z-3}}{10},$

and

$|U|\geq 2m^{y-z}\cdot\frac{dm^{z}}{10\gamma}\cdot(100\gamma
m^{x-2y+z-3}-44\gamma m^{x-2y+z-3})>\frac{dm^{x-2y+z-3}}{10}.$

On the other hand,

$\displaystyle|W|+|\mathsf{Int}(\mathcal{Q})|+|Y^{\prime}|+|Z|$
$\displaystyle\leq 100dm^{x-2y+z-4}+176\gamma m^{x-2y+z-2}+200\gamma
m^{x-y-3}+m^{x-2y+z-3}+100\gamma m^{x-2y+z-3}$
$\displaystyle\leq\frac{1}{4}\rho\left(\frac{dm^{x-2y+z-3}}{10}\right)\cdot\frac{dm^{x-2y+z-3}}{10}.$

Hence, applying Lemma 2.13 with $V,U,W\cup\mathsf{Int}(\mathcal{Q})\cup Z$
playing the roles of $X_{1},X_{2},W$, respectively, we obtain vertices
$y_{k_{1}}\in V,y_{k_{2}}\in U$ and a path of length at most $m$ connecting
$y_{k_{1}}$ and $y_{k_{2}}$ whilst avoiding vertices in
$W\cup\mathsf{Int}(\mathcal{Q})\cup Z$. Denote by $S_{k_{1}}$ the star which
contains $y_{k_{1}}$ as a leave and $F_{k_{2}}$ the unit such that
$y_{k_{2}}\in\mathsf{Ext}(F_{k_{2}})$. This yields a
$v_{k_{1}},u_{k_{2}}$-path, denoted as $Q_{k_{1},k_{2}}$, which is internally
disjoint from $W\cup\mathsf{Int}(\mathcal{Q})\cup
Z\cup(Y^{\prime}\backslash\mathsf{Int}(F_{k_{2}}))$. Hence, $Q_{k_{1},k_{2}}$
satisfies (J1) and (J2), a contradiction to the maximum of $\mathcal{Q}$. ∎

By Claim B.3, there is a center $v_{i}$ connected to $44\gamma$ distinct
centers $u_{j}$, say $u_{1},\ldots u_{44\gamma}$, which is corresponding to
units $F_{1},\ldots F_{44\gamma}$. Let $\mathcal{Q}^{\prime}$ be the family of
all the paths $Q_{ij}$, where $j\in[44\gamma]$. A pendent star $S$ in a unit
$F_{i}$ $(i\in[44\gamma])$ is _overused_ if at least $\frac{dm^{z}}{20\gamma}$
leaves of $S$ is used in $V(\mathcal{Q^{\prime}})$, and a unit $F_{i}$ is
_bad_ if at least $m^{y-z}$ stars are overused. Note that the number of bad
units is at most

$\frac{|V(\mathcal{Q}^{\prime})|}{m^{y-z}\cdot\frac{dm^{z}}{20\gamma}}\leq\frac{176\gamma
m}{m^{y-z}\cdot\frac{dm^{z}}{20\gamma}}<22\gamma.$

Hence, there are at least $22\gamma$ units among $F_{1},\ldots F_{44\gamma}$,
where each pendent star has at least $\frac{dm^{z}}{20\gamma}$ leaves that are
not used in $V(\mathcal{Q}^{\prime})$. For each of these units, we take a sub-
unit by including the branches each attached with a pendant star that is not
overused to form a desired $(22\gamma,m^{y-z},\frac{dm^{z}}{20\gamma},4m)$-web
in $G-W$. ∎

##  Appendix C Proof of Lemmas 4.10 and 4.11

###### Proof of Lemma 4.11.

Given $\varepsilon_{1},\varepsilon_{2},s,x$ such that $s\geq 8x$, we choose
$\frac{1}{K}\ll c\ll\varepsilon_{1},\varepsilon_{2}$, and let $G$ be an
$n$-vertex $(dm^{x},\frac{d}{2})$-dense
$(\varepsilon_{1},\varepsilon_{2}d)$-expander with $\delta(G)\geq d$. For any
$W\subseteq V(G)$ with $|W|\leq Dm^{-\frac{3}{4}}$. Let $Z_{1},Z_{2}\subseteq
V(G)\backslash W$ be two vertex-disjoint sets and each of size at least $D$.
For each $j\in[2]$, let $I_{j}\subseteq V(G)\backslash(W\cup Z_{1}\cup Z_{2})$
be an $(D,m)$-expansion centered at $v_{j}$. Notice that
$|W|\leq\frac{D}{m^{\frac{3}{4}}}\leq\frac{\rho(2D)2D}{4}$, $|Z_{1}\cup
Z_{2}|\geq 2D$, and $|I_{1}\cup I_{2}|=2D$. Thus, there is a path
$P^{\prime}_{1}$ of length at most $m$ avoiding $W$ from $Z_{1}\cup Z_{2}$ to
$I_{1}\cup I_{2}$ by Lemma 2.13, say $P^{\prime}_{1}$ is a
$z^{\prime}_{1},v^{\prime}_{1}$-path, where $z^{\prime}_{1}\in Z_{1}$,
$v^{\prime}_{1}\in I_{1}$. Since $I_{1}$ is a $(D,m)$-expansion centered at
$v_{1}$, $P^{\prime}_{1}$ can be extended to a $z^{\prime}_{1},v_{1}$-path $P$
of length at most $2m$. Now denote by $W^{\prime}:=W\cup V(P)$, and
$|W^{\prime}|\leq 2Dm^{-\frac{3}{4}}$.

######  Claim C.1.

There is a $u,v_{2}$-path in $G-W^{\prime}$ for some $u\in Z_{2}$ of length
between $\ell$ and $\ell+16m$ for any $\ell\leq dm^{y-2}$.

###### Proof of Claim C.1.

Let $(P^{*},v^{*},F_{1})$ be a triple such that $\ell(P^{*})$ is maximised and
satisfying the following rules.

  1. (K1)

$F_{1}$ is a $(D,3m)$-expansion centered at $v^{*}$ in $G-W$.

  2. (K2)

$P^{*}$ is a $v_{2},v^{*}$-path in $G-W$ and $V(F_{1})\cap
V(P^{*})=\\{v^{*}\\}$.

  3. (K3)

$\ell(P^{*})\leq\ell+12m$.

Note that such a triple exists because of the basic case when $F_{1}:=I_{2}$,
$v^{*}:=v_{2}$, $P=G[\\{v^{*}\\}]$. We first claim that $\ell(P^{*})\geq\ell$.
Otherwise we denote $W_{1}:=W\cup V(P^{*})\cup V(F_{1})$, and then
$|W_{1}|\leq 2Dm^{-\frac{3}{4}}+\ell+D\leq 2D$. By Lemma 4.5, $G-W_{1}$
contains a $(22\gamma,m^{y-z},\frac{dm^{z}}{20\gamma},4m)$-web $F^{\prime}$
with core vertex $v$. However, $|W\cup V(P^{*})|\leq
2Dm^{-\frac{3}{4}}+\ell\leq
3Dm^{-\frac{3}{4}}\leq\frac{1}{4}\rho(n)D\leq\frac{1}{4}\rho(D)D$, and
$|F^{\prime}|\geq 22dm^{y}\geq D$, $|F_{1}|\geq D$ also hold. Thus, by Lemma
2.13, there is a $u^{\prime}_{1},u^{\prime}_{2}$-path $Q^{\prime}$ of length
at most $m-1$, where $u^{\prime}_{1}\in V(F_{1})$ and $u^{\prime}_{2}\in
V(F^{\prime})$, and so $Q^{\prime}$ can be extended to a $v,v^{*}$-path $Q$ of
length at most $3m+m-1+8m+1=12m$. By the property of the web $F^{\prime}$, we
know that there exists a $F_{2}\subseteq(F^{\prime}\backslash
V(Q))\cup\\{v\\}$ which is a $(D,9m)$-expansion centered at $v$. Now let
$P^{\prime}=P^{*}\cup Q$ which is a $v,v_{2}$-path with
$\ell(P^{*})+1\leq\ell(P^{\prime})\leq\ell(P^{*})+12m<\ell+12m$. Thus, we find
a triple $(P^{\prime},v_{2},F_{2})$ satisfying three conditions (K1)-(K3) with
$\ell(P^{\prime})>\ell(P^{*})$, a contradiction to the maximality of
$\ell(P^{*})$. Hence, $\ell(P^{*})\geq\ell$, as claimed.

Note that $|W\cup V(P^{*})|\leq 2Dm^{-\frac{3}{4}}+\ell+12m\leq
3Dm^{-\frac{3}{4}}\leq\frac{1}{4}\rho(n)D\leq\frac{1}{4}\rho(D)D$,
$|F_{1}|\geq D$ and $|Z_{2}|\geq D$. By Lemma 2.13, there is a
$r_{1},r_{2}$-path $Q_{1}$ of length at most $m$ avoiding $W\cup V(P^{*})$,
where $r_{1}\in Z_{2}$ and $r_{2}\in F_{1}$. Let $Q_{2}$ be a
$v^{*},r_{2}$-path. Thus, $Q_{1}\cup Q_{2}\cup P$ is a $v_{2},r_{1}$-path in
$G-W$ satisfying $\ell\leq\ell(Q_{1}\cup Q_{2}\cup
P^{*})\leq\ell(P^{*})+3m+m\leq\ell+16m$. Finally, take $u:=r_{1}$, the claim
holds. ∎

By Claim C.1, we can find a $u,v_{2}$-path $Q$ satisfying
$\ell\leq\ell(Q)\leq\ell+16m$ while avoiding $W^{\prime}$, where $u\in Z_{2}$.
Therefore, $\ell\leq\ell(P)+\ell(Q)\leq\ell+18m$, and such $P,Q$ are as
desired. ∎

We now turn to Lemma 4.10. We need the following simple fact about expansions.

######  Proposition C.2 ([36]).

Let $D,D^{\prime},m\in\mathbb{N}$ and $1\leq D^{\prime}\leq D$. Then any graph
$F$ which is a $(D,m)$-expansion centered at $v$ contains a subgraph which is
a $(D^{\prime},m)$-expansion centered at $v$.

The following definition is essential to find a large adjuster.

######  Definition C.3 ([36]).