# Forbidden subgraphs generating a finite set of graphs with minimum degree
three and large girth

Yoshimi Egawa1 Michitaka<EMAIL_ADDRESS>
1Department of Applied Mathematics,
Tokyo University of Science,
1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan
2College of Liberal Arts and Sciences,
Kitasato University,
1-15-1 Kitasato, Minami-ku, Sagamihara, Kanagawa 252-0373, Japan

###### Abstract

For a family $\mathcal{H}$ of graphs, a graph $G$ is said to be
$\mathcal{H}$-free if $G$ contains no member of $\mathcal{H}$ as an induced
subgraph. We let $\tilde{\mathcal{G}}_{3}(\mathcal{H})$ denote the family of
connected $\mathcal{H}$-free graphs having minimum degree at least $3$. In
this paper, we characterize the non-caterpillar trees $T$ having diameter at
least $7$ such that $\tilde{\mathcal{G}}_{3}(\\{C_{3},C_{4},T\\})$ is a finite
family, where $C_{n}$ is a cycle of order $n$.

Key words and phrases. forbidden subgraph, forbidden triple, chromatic number.

AMS 2020 Mathematics Subject Classification. 05C75, 05C15.

##  1 Introduction

All graphs considered in this paper are finite, simple, and undirected. Let
$G$ be a graph. We let $V(G)$ and $E(G)$ denote the vertex set and the edge
set of $G$, respectively. For a vertex $u\in V(G)$, we let $N_{G}(u)$ and
$d_{G}(u)$ denote the neighborhood and the degree of $u$, respectively; thus
$N_{G}(u)=\\{v\in V(G):uv\in E(G)\\}$ and $d_{G}(u)=|N_{G}(u)|$. We let
$\delta(G)$ and $\Delta(G)$ denote the minimum degree and the maximum degree
of $G$, respectively. For a subset $U$ of $V(G)$, we set
$N_{G}(U)=\bigcup_{u\in U}N_{G}(u)$, and let $G[U]$ denote the subgraph of $G$
induced by $U$. For two subsets $U$ and $U^{\prime}$ of $V(G)$, we let
$E_{G}(U,U^{\prime})$ be the set of edges $uu^{\prime}$ of $G$ with $u\in U$
and $u^{\prime}\in U^{\prime}$. For $u,v\in V(G)$, let ${\rm dist}_{G}(u,v)$
denote the length of a shortest $u$-$v$ path of $G$. We let ${\rm diam}(G)$
denote the maximum of ${\rm dist}_{G}(u,v)$ as $u$ and $v$ range over $V(G)$.
We let $P_{n}$ and $C_{n}$ denote the path and the cycle of order $n$,
respectively. For two positive integers $s$ and $t$, the Ramsey number
$R(s,t)$ is the minimum positive integer $R$ such that any graph of order at
least $R$ contains a clique of cardinality $s$ or an independent set of
cardinality $t$. For terms and symbols not defined in this paper, we refer the
reader to [7].

For two graphs $G$ and $H$, we write $H\prec G$ if $G$ contains an induced
copy of $H$, and $G$ is said to be $H$-free if $H\not\prec G$. For a family
${\mathcal{H}}$ of graphs, a graph $G$ is said to be ${\mathcal{H}}$-free if
$G$ is $H$-free for every $H\in{\mathcal{H}}$. In this context, the members of
${\mathcal{H}}$ are called forbidden subgraphs. For an integer $k\geq 1$ and a
family ${\mathcal{H}}$ of graphs, let
$\tilde{{\mathcal{G}}}_{k}({\mathcal{H}})$ denote the family of connected
${\mathcal{H}}$-free graphs with minimum degree at least $k$. In this paper,
we focus on the finiteness of
$\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$, where $T$ is a tree having
large diameter.

A tree $T$ is a caterpillar if there exists a path $P$ of $T$ such that
$T-V(P)$ has no edges. For an integer $n\geq 4$, let $T_{n}$ be the graph
obtained from a path $u_{1}u_{2}\cdots u_{n}$ of order $n$ by adding two
vertices $v_{3},v^{\prime}_{3}$ and edges $u_{3}v_{3},v_{3}v^{\prime}_{3}$
(see the left graph in Figure 1). Let $T_{8}^{(1)}$ and $T_{8}^{(2)}$ be the
graphs depicted in the center and the right in Figure 1, respectively. The
following is our main theorem.

$T_{8}^{(1)}$$T_{8}^{(2)}$$T_{n}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{n}$$v_{3}$$v^{\prime}_{3}$
Figure 1: Graphs $T_{n}$, $T_{8}^{(1)}$ and $T_{8}^{(2)}$

###### Theorem 1.1

Let $T$ be a tree with ${\rm diam}(T)\geq 7$, and suppose that $T$ is not a
caterpillar. Then $\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$ is a finite
family if and only if $T$ is a subgraph of one of $T_{8}^{(1)}$, $T_{8}^{(2)}$
and $T_{9}$.

As for the “only if” part of Theorem 1.1, we prove the following theorem in
Section 2.

###### Theorem 1.2

Let $T$ be a tree with ${\rm diam}(T)\geq 7$, and suppose that $T$ is not a
caterpillar. If $\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$ is a finite
family, then $T$ is a subgraph of one of $T_{8}^{(1)}$, $T_{8}^{(2)}$ and
$T_{9}$.

Note that a connected graph $G$ with ${\rm diam}(G)\geq 3$ satisfies
$|V(G)|\leq\Delta(G)^{{\rm diam}(G)}$ (see, for example, [3]). Thus we divide
the “if” part of Theorem 1.1 into two assertions as follows.

###### Theorem 1.3

Let $G$ be a connected $\\{C_{3},C_{4}\\}$-free graph with $\delta(G)\geq 3$.
Then the following hold.

  1. (i)

If ${\rm diam}(G)\geq 20$, then $T_{8}^{(1)}\prec G$.

  2. (ii)

If ${\rm diam}(G)\geq 16$, then $T_{8}^{(2)}\prec G$.

  3. (iii)

If ${\rm diam}(G)\geq 12$, then $T_{9}\prec G$.

###### Theorem 1.4

Let $G$ be a connected $\\{C_{3},C_{4}\\}$-free graph with $\delta(G)\geq 3$.
Then the following hold.

  1. (i)

If $\Delta(G)\geq 943218$, then $T_{8}^{(1)}\prec G$.

  2. (ii)

If $\Delta(G)\geq 190375$, then $T_{8}^{(2)}\prec G$.

  3. (iii)

If $\Delta(G)\geq 197433$, then $T_{9}\prec G$.

Theorem 1.3 is proved in Section 3. In Section 4, we prepare some lemmas for
the proof of Theorem 1.4, and using them, we prove Theorem 1.4 in Section 5.

###  1.1 Motivations and applications of Theorem 1.1

Our motivation of Theorem 1.1 derives from several different lines of
research. The first one is characterization of families ${\mathcal{H}}$ of
connected graphs satisfying the condition that

the number of $k$-connected ${\mathcal{H}}$-free graphs is finite. (1.1)

If a family ${\mathcal{H}}$ satisfies (1.1), then for any property $P$ on
graphs, although the proposition that

all $k$-connected ${\mathcal{H}}$-free graphs satisfy $P$ with finite
exceptions (1.2)

holds, the proposition gives no information about $P$. Thus it is important to
identify families ${\mathcal{H}}$ satisfying (1.1) in advance. Having such a
motivation, Fujisawa, Plummer and Saito [8] started a study of ${\mathcal{H}}$
satisfying (1.1), and they determined the families ${\mathcal{H}}$ satisfying
(1.1) for the case where $1\leq k\leq 6$ and $|{\mathcal{H}}|\leq 2$. In [3,
4, 6], the research was continued by analyzing families ${\mathcal{H}}$
satisfying (1.1) for the case where $k=3$ and $|{\mathcal{H}}|=3$. However, at
present, the state of research is far from complete characterization of
${\mathcal{H}}$ for this case. Theorem 1.1 concerned with the corresponding
problem for graphs with minimum degree at least $3$. In view of the fact that
connectivity conditions can often be replaced by minimum degree conditions in
propositions like (1.2), it is natural to consider connected graphs with
minimum degree at least $3$ in place of $3$-connected graphs. In fact, the
authors [5] recently characterized the families ${\mathcal{H}}$ with
$|{\mathcal{H}}|=3$ and $\\{C_{3},C_{4}\\}\not\subseteq{\mathcal{H}}$ such
that $\tilde{{\mathcal{G}}}_{3}({\mathcal{H}})$ is finite. Thus for the
finiteness problem on $\tilde{{\mathcal{G}}}_{3}({\mathcal{H}})$ with
$|{\mathcal{H}}|=3$, it remains to consider the case where
$\\{C_{3},C_{4}\\}\subseteq{\mathcal{H}}$. Moreover, research done in [3, 4,
6] has revealed that caterpillars and trees with small diameter are easy to
handle in the study of forbidden subgraphs. Thus Theorem 1.1 solves the most
difficult case of the finiteness problem on
$\tilde{{\mathcal{G}}}_{3}({\mathcal{H}})$ with $|{\mathcal{H}}|=3$ (we plan
to discuss other cases in a subsequent paper).

Our second motivation is a coloring problem. For a graph $G$, let $\chi(G)$
denote the chromatic number of $G$, that is, the minimum number of $k$ such
that there exists a function $c:V(G)\rightarrow\\{1,\ldots,k\\}$ with
$c(u)\neq c(v)$ for any adjacent vertices $u$ and $v$ of $G$. In recent years,
there have been remarkable progress in the study of the relationship between
the chromatic number and forbidden subgraphs (see a survey [12]). Most
notably, Chudnovsky and Stacho [2] focused on $3$-colorability of $P_{8}$-free
graphs, and showed that every $\\{C_{3},C_{4},P_{8}\\}$-free graph is
$3$-colorable. They indeed proved the following stronger theorem which
immediately assures us the $3$-colorability of $\\{C_{3},C_{4},P_{8}\\}$-free
graphs (with induction argument).

######  Theorem A (Chudnovsky and Stacho [2])

Let $G$ be a connected $\\{C_{3},C_{4},P_{8}\\}$-free graph with
$\delta(G)\geq 3$. Then $G$ is the Petersen graph, the Heawood graph, or the
graph obtained from the Heawood graph by contracting one edge. In particular,
$\chi(G)\leq 3$.

Since there is a polynomial-time algorithm (with respect to $|V(G)|$) to judge
whether a given graph $G$ is bipartite or not, we can calculate the chromatic
number of $\\{C_{3},C_{4},P_{8}\\}$-free graphs in polynomial time based on
Theorem A. Here a natural question arises: What forbidden subgraph conditions
(similar to $\\{C_{3},C_{4},P_{8}\\}$-freeness) can yield a polynomial-time
algorithm to determine the chromatic number? In view of Theorem A,
$\\{C_{3},C_{4},T\\}$-freeness for a tree $T$ with large diameter appears to
be a condition worth considering. Our main result provides us with examples of
such conditions which give a desired algorithm as follows.

We let $T$ be an induced subgraph of one of $T_{8}^{(1)}$, $T_{8}^{(2)}$ and
$T_{9}$, and determine the chromatic number of a $\\{C_{3},C_{4},T\\}$-free
graph $G$. By Theorem 1.1, there exists a constant number $s=s(T)$ such that
every connected $\\{C_{3},C_{4},T\\}$-free graph with minimum degree at least
$3$ has at most $s$ vertices. We first judge whether $G$ is bipartite or not
in polynomial time. We may assume that $G$ is judged to be a non-bipartite
graph, i.e., $\chi(G)\geq 3$. Next we find a maximal sequence
$u_{1},u_{2},\ldots,u_{m}$ of vertices of $G$ such that the degree of $u_{i}$
in $G-\\{u_{1},\ldots,u_{i-1}\\}$ is at most $2$ (in polynomial time). Since
$\chi(G)\geq 3$, we have
$\chi(G)=\max\\{\chi(G-\\{u_{1},\ldots,u_{i}\\}),3\\}$ for all $i~{}(1\leq
i\leq m)$ by induction on $i$. In particular,
$\chi(G)=\max\\{\chi(G-\\{u_{1},\ldots,u_{m}\\}),3\\}$. If
$G-\\{u_{1},\ldots,u_{m}\\}$ is an empty graph, then $\chi(G)=3$. Thus we may
assume that $G-\\{u_{1},\ldots,u_{m}\\}$ is non-empty. Let
$G_{1},\ldots,G_{p}$ be the components of $G-\\{u_{1},\ldots,u_{m}\\}$. Then
$G_{i}$ is a connected $\\{C_{3},C_{4},T\\}$-free graph with
$\delta(G_{i})\geq 3$, and hence $|V(G_{i})|\leq s$. Since $s$ does not depend
on the order of $G$, we can determine the chromatic number of $G_{i}$ in
constant time (here the constant is $O(2^{s}s)$ [1]). Since $p\leq|V(G)|$, we
calculate the value $\max\\{\chi(G_{i}):1\leq i\leq
p\\}~{}(=\chi(G-\\{u_{1},\ldots,u_{m}\\}))$ in linear time. Therefore we can
determine the value $\chi(G)$ in a polynomial time with respect to $|V(G)|$.
Note that the finiteness of $\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$
is effectively used in the above strategy.

##  2 Proof of Theorem 1.2

In this section, we prove Theorem 1.2.

For an integer $n\geq 6$, let $T^{*}_{n}$ be the graph obtained from $T_{n}$
by adding two vertices $w_{n-2},w^{\prime}_{n-2}$ and edges
$u_{n-2}w_{n-2},w_{n-2}w^{\prime}_{n-2}$ (see the left graph in Figure 2). For
integers $n\geq 5$ and $p_{4},\ldots,p_{n-1}\in\\{0,1\\}$, let
$S_{n}(p_{4},\ldots,p_{n-1})$ be the graph obtained from $T_{n}$ by adding
$\sum_{4\leq i\leq n-1}p_{i}$ vertices $w_{i}$ and edges $u_{i}w_{i}$ with
$4\leq i\leq n-1$ and $p_{i}=1$ (see the center graph and the right graph in
Figure 2). Note that $T_{n}(0,\ldots,0)=T_{n}$, $S_{8}(0,1,1,0)\simeq
T_{8}^{(1)}$ and $S_{8}(1,0,0,0)\simeq T_{8}^{(2)}$. Let $S_{8}^{(1)}$ and
$S_{8}^{(2)}$ be the graphs depicted in Figure 3.

$T^{*}_{n}$$S_{7}(1,0,1)$$S_{8}(1,1,1,0)$$w_{n-2}$$w^{\prime}_{n-2}$$u_{4}$$u_{5}$$u_{6}$$w_{4}$$w_{6}$$w_{4}$$w_{5}$$w_{6}$$u_{5}$$u_{6}$$u_{7}$$u_{4}$$u_{n-2}$
Figure 2: Graphs $T^{*}_{n}$, $S_{7}(1,0,1)$ and $S_{8}(1,1,1,0)$
$S_{8}^{(1)}$$S_{8}^{(2)}$ Figure 3: Graphs $S_{8}^{(1)}$ and $S_{8}^{(2)}$

We start with several lemmas. The following lemma was proved in [10].

######  Lemma 2.1 (Kochol [10])

For every integer $g\geq 3$, there exist infinitely many $3$-connected
$3$-regular graphs with girth at least $g$.

For an integer $s\geq 1$, we let $H^{(1)}_{s}$ be the graph obtained from $s$
pairwise vertex-disjoint cycles $D_{i}=u^{(i)}_{1}u^{(i)}_{2}\cdots
u^{(i)}_{6}u^{(i)}_{1}~{}(1\leq i\leq s)$ by adding three vertices
$v_{1},v_{2},v_{3}$ and the set of edges

$\\{u^{(i)}_{j}v_{h}:1\leq i\leq s,~{}1\leq j\leq 6,~{}1\leq h\leq
3,~{}j\equiv h~{}({\rm mod~{}}3)\\}$

(see Figure 4).

$u^{(1)}_{1}$$u^{(1)}_{3}$$u^{(1)}_{5}$$u^{(1)}_{6}$$u^{(1)}_{4}$$u^{(1)}_{2}$$u^{(s)}_{1}$$u^{(s)}_{3}$$u^{(s)}_{5}$$u^{(s)}_{6}$$u^{(s)}_{4}$$u^{(s)}_{2}$$v_{2}$$v_{3}$$v_{1}$
Figure 4: Graph $H^{(1)}_{s}$

###### Lemma 2.2

Let $s\geq 5$ be an integer, and let $T$ be an induced subtree of
$H^{(1)}_{s}$ with $\Delta(T)\leq 3$ which is not a caterpillar. Then the
following holds.

  1. (i)

The graph $H^{(1)}_{s}$ is $P_{10}$-free. In particular, ${\rm diam}(T)\leq
8$.

  2. (ii)

If ${\rm diam}(T)=8$, then $T$ is a subgraph of $T^{*}_{9}$.

  3. (iii)

If ${\rm diam}(T)=7$, then $T$ is a subgraph of $S_{8}(0,0,0,1)$ or
$S_{8}^{(1)}$.

###### Proof.

Let $P$ be an induced subpath of $H^{(1)}_{s}$ having $9$ vertices. Then we
see that either $P$ contains all of $v_{1},v_{2},v_{3}$ or, by the symmetry of
vertices of $H^{(1)}_{s}$, we may assume that $P$ is equal to

$Q_{1}=u^{(1)}_{6}u^{(1)}_{1}v_{1}u^{(2)}_{1}u^{(2)}_{6}u^{(2)}_{5}v_{2}u^{(3)}_{2}u^{(3)}_{3}.$

In either case, $P$ is a maximal induced subpath of $H^{(1)}_{s}$, which
implies that $H^{(1)}_{s}$ contains no induced copy of $P_{10}$. This proves
(i).

Suppose that ${\rm diam}(T)=8$, and let $P^{\prime}$ be a path of $T$ having
$9$ vertices. If $P^{\prime}$ contains all of $v_{1},v_{2},v_{3}$, then any
induced subtree of $H^{(1)}_{s}$ containing all vertices of $P^{\prime}$ is a
caterpillar, which is a contradiction. Thus we may assume that
$P^{\prime}=Q_{1}$. Then $T$ does not contain $v_{3}$, and contains no three
consecutive vertices of $D_{j}~{}(1\leq j\leq s)$ except for
$u_{1}^{(2)}u_{6}^{(2)}u_{5}^{(2)}$. This together with the assumption that
$\Delta(T)\leq 3$ implies that $T$ is an induced subgraph of $T^{*}_{9}$ (for
example, the subgraph of $H^{(1)}_{s}$ induced by
$\\{u^{(1)}_{6},u^{(1)}_{1},v_{1},u^{(4)}_{6},u^{(4)}_{1},u^{(2)}_{1},u^{(2)}_{6},u^{(2)}_{5},v_{2},u^{(5)}_{3},u^{(5)}_{2},u^{(3)}_{2},u^{(3)}_{3}\\}$
is isomorphic to $T^{*}_{9}$), which proves (ii).

Suppose that ${\rm diam}(T)=7$, and let $P^{\prime\prime}$ be a path of $T$
having $8$ vertices. By the symmetry of vertices of $H^{(1)}_{s}$, we may
assume that one of the following holds.

  1. $\bullet$

$P^{\prime\prime}$ contains all of $v_{1},v_{2},v_{3}$;

  2. $\bullet$

$P^{\prime\prime}$ is equal to $Q_{1}-u^{(3)}_{3}$, which is a subpath of
$Q_{1}$; or

  3. $\bullet$

$P^{\prime\prime}$ is equal to
$Q_{2}=u^{(1)}_{6}u^{(1)}_{1}v_{1}u^{(2)}_{1}u^{(2)}_{2}v_{2}u^{(3)}_{2}u^{(3)}_{3}$.

Now we focus on an induced tree $T^{\prime}$ containing all vertices of
$P^{\prime\prime}$ which is maximal under the condition that ${\rm
diam}(T^{\prime})=7$ and $\Delta(T^{\prime})\leq 3$. Then we see that

  1. $\bullet$

if $P^{\prime\prime}$ contains all of $v_{1},v_{2},v_{3}$, then $T^{\prime}$
is a caterpillar;

  2. $\bullet$

if $P^{\prime\prime}=Q_{1}-u^{(3)}_{3}$ or $P^{\prime\prime}=Q_{2}$, then
$T^{\prime}$ does not contain $v_{3}$;

  3. $\bullet$

if $P^{\prime\prime}=Q_{1}-u^{(3)}_{3}$ or $P^{\prime\prime}=Q_{2}$, then
$T^{\prime}$ contains no three consecutive vertices of $D_{j}~{}(1\leq j\leq
s)$ except for vertices of $D_{2}$; and

  4. $\bullet$

from the above facts, it follows that the following hold:

    1. $\circ$

if $P^{\prime\prime}=Q_{1}-u^{(3)}_{3}$, then $T^{\prime}$ is an induced copy
of $S_{8}(0,0,0,1)$ (for example, the subgraph of $H^{(1)}_{s}$ induced by
$\\{u^{(1)}_{6},u^{(1)}_{1},v_{1},u^{(4)}_{6},u^{(4)}_{1},u^{(2)}_{1},u^{(2)}_{6},u^{(2)}_{5},v_{2},u^{(3)}_{2},u^{(3)}_{5}\\}$
is isomorphic to $S_{8}(0,0,0,1)$); and

    2. $\circ$

if $P^{\prime\prime}=Q_{2}$, then $T^{\prime}$ is an induced copy of
$S_{8}^{(1)}$ (for example, the subgraph of $H^{(1)}_{s}$ induced by
$\\{u^{(1)}_{6},u^{(1)}_{1},v_{1},u^{(4)}_{6},u^{(4)}_{1},u^{(2)}_{1},u^{(2)}_{6},u^{(2)}_{2},u^{(2)}_{3},v_{2},u^{(3)}_{3},u^{(3)}_{2},u^{(5)}_{2},u^{(5)}_{3}\\}$
is isomorphic to $S_{8}^{(1)}$).

Since $T$ is a tree with ${\rm diam}(T)=7$ and $\Delta(T)\leq 3$ and not a
caterpillar, this implies that $T\prec S_{8}(0,0,0,1)$ or $T\prec
S_{8}^{(1)}$, which proves (iii). ∎

Let $A$ be the graph obtained from two vertex-disjoint cycles
$u_{1}u_{2}\cdots u_{5}u_{1}$ and $v_{1}v_{2}\cdots v_{5}v_{1}$ by adding five
vertices $w_{1},\ldots,w_{5}$ and edges $u_{j}w_{j},v_{j}w_{j}~{}(1\leq j\leq
5)$. For an integer $s\geq 3$, we let $H^{(2)}_{s}$ be the graph obtained from
$s$ pairwise vertex-disjoint copies $A_{1},\ldots,A_{s}$ of $A$ such that
$V(A_{i})=\\{u^{(i)}_{j},v^{(i)}_{j},w^{(i)}_{j}:1\leq j\leq 5\\}$ where
$u^{(i)}_{j}$, $v^{(i)}_{j}$ and $w^{(i)}_{j}$ respectively correspond to
$u_{j}$, $v_{j}$ and $w_{j}$, by adding a new vertex $z$ and edges
$zw^{(i)}_{j}~{}(1\leq i\leq s,~{}1\leq j\leq 5)$ (see Figure 5).

$u^{(1)}_{1}$$u^{(1)}_{3}$$u^{(1)}_{5}$$u^{(1)}_{4}$$u^{(1)}_{2}$$v^{(1)}_{1}$$v^{(1)}_{3}$$v^{(1)}_{5}$$v^{(1)}_{4}$$v^{(1)}_{2}$$u^{(s)}_{1}$$u^{(s)}_{3}$$u^{(s)}_{5}$$u^{(s)}_{4}$$u^{(s)}_{2}$$v^{(s)}_{1}$$v^{(s)}_{3}$$v^{(s)}_{5}$$v^{(s)}_{4}$$v^{(s)}_{2}$$w^{(1)}_{1}$$w^{(1)}_{3}$$w^{(1)}_{5}$$w^{(1)}_{4}$$w^{(1)}_{2}$$w^{(s)}_{1}$$w^{(s)}_{3}$$w^{(s)}_{5}$$w^{(s)}_{4}$$w^{(s)}_{2}$$z$
Figure 5: Graph $H^{(2)}_{s}$

###### Lemma 2.3

For an integer $s\geq 3$, $H^{(2)}_{s}$ is
$\\{S_{8}(0,0,0,1),T^{*}_{8}\\}$-free.

###### Proof.

Let $T$ be an induced subgraph of $H^{(2)}_{s}$ isomorphic to $T_{8}$. It
suffices to show that

no induced subgraph of $H^{(2)}_{s}$ isomorphic to $S_{8}(0,0,0,1)$ or
$T^{*}_{8}$ contains all vertices of $T$. (2.1)

Let $x$ be the unique vertex of $T$ with $d_{T}(x)=3$. Without loss of
generality, we may assume that $x\in\\{u^{(1)}_{1},w^{(1)}_{1},z\\}$.

We first assume that $x=u^{(1)}_{1}$. Then we easily verify that
$N_{T}(u^{(1)}_{1})\cap\\{w^{(1)}_{j}:1\leq j\leq 5\\}\neq\emptyset$ and
$N_{T}(N_{T}(u^{(1)}_{1}))\cap\\{w^{(1)}_{j}:1\leq j\leq 5\\}\neq\emptyset$,
and hence $z\notin V(T)$, i.e., $V(T)\subseteq V(A_{1})$, and by the symmetry
of vertices of $A_{1}$, we may assume that $T$ is a subgraph of $A_{1}$
induced by

  1. $\bullet$

$\\{w^{(1)}_{2},u^{(1)}_{2},u^{(1)}_{1},u^{(1)}_{4},u^{(1)}_{5},w^{(1)}_{1},v^{(1)}_{1},v^{(1)}_{5},v^{(1)}_{4},v^{(1)}_{3}\\}$;
or

  2. $\bullet$

$\\{w^{(1)}_{2},u^{(1)}_{2},u^{(1)}_{1},v^{(1)}_{1},w^{(1)}_{1},u^{(1)}_{5},u^{(1)}_{4},w^{(1)}_{4},v^{(1)}_{4},v^{(1)}_{3}\\}$.

In either case, (2.1) holds.

Next we assume that $x=w^{(1)}_{1}$. Since $d_{T}(x)=3$, we have $z\in V(T)$.
Furthermore, we see that the path $P$ of $T$ with an end $w^{(1)}_{1}$ having
length $5$ intersects with $\bigcup_{2\leq i\leq s}V(A_{i})$. By the symmetry
of indices $2,3,\ldots,s$, we may assume that $V(P)\cap V(A_{2})\neq\emptyset$
and, by the symmetry of vertices of $A_{2}$, we may further assume that
$P=w^{(1)}_{1}zw^{(2)}_{1}u^{(2)}_{1}u^{(2)}_{2}u^{(2)}_{3}$. Suppose that
there is an induced subgraph $S$ of $H^{(2)}_{s}$ isomorphic to
$S_{8}(0,0,0,1)$ or $T^{*}_{8}$ containing all vertices of $T$. Note that
$N_{H^{(2)}_{s}}(u^{(2)}_{2})-V(T)=\\{w^{(2)}_{2}\\}$,
$N_{H^{(2)}_{s}}(u^{(2)}_{1})-V(T)=\\{u^{(2)}_{5}\\}$ and
$N_{H^{(2)}_{s}}(u^{(2)}_{5})-V(T)=\\{u^{(2)}_{4},w^{(2)}_{5}\\}$. Hence

  1. $\bullet$

if $S\simeq S_{8}(0,0,0,1)$, then $w^{(2)}_{2}\in V(S)$; and

  2. $\bullet$

if $S\simeq T^{*}_{8}$, then we have $\\{u^{(2)}_{5},u^{(2)}_{4}\\}\subseteq
V(S)$ or $\\{u^{(2)}_{5},w^{(2)}_{5}\\}\subseteq V(S)$.

In either case, $S$ contains a cycle. This contradicts the fact that $S$ is a
tree, which shows that (2.1) holds.

Finally we assume that $x=z$. Let $P$ be the path of $T$ with an end $z$
having length $5$. Then by the symmetry of vertices of $H^{(2)}_{s}$, we may
assume that $P=zw^{(1)}_{1}u^{(1)}_{1}u^{(1)}_{2}u^{(1)}_{3}u^{(1)}_{4}$.
Since $N_{H^{(2)}_{s}}(u^{(1)}_{j})-V(T)=\\{w^{(1)}_{j}\\}$ for each
$j\in\\{2,3\\}$,

  1. $\bullet$

if an induced subgraph $S$ of $H^{(2)}_{s}$ isomorphic to $S_{8}(0,0,0,1)$
contains all vertices of $T$, then $w^{(1)}_{3}\in V(S)$; and

  2. $\bullet$

if an induced subgraph $S$ of $H^{(2)}_{s}$ isomorphic to $T^{*}_{8}$ contains
all vertices of $T$, then $w^{(1)}_{2}\in V(S)$.

In either case, $S$ contains a cycle, which is a contradiction. This leads to
(2.1). ∎

Let $A^{\prime}$ be the graph depicted in Figure 6. For an integer $s\geq 4$,
we let $H^{(3)}_{s}$ be the graph obtained from $s$ pairwise vertex-disjoint
copies $A^{\prime}_{1},\ldots,A^{\prime}_{s}$ of $A^{\prime}$ such that
$V(A^{\prime}_{i})=\\{u^{(i)}_{j},v^{(i)}_{j,h},w^{(i)}_{j,h^{\prime}}:1\leq
j\leq 2,~{}1\leq h\leq 2,~{}1\leq h^{\prime}\leq 4\\}$ where $u^{(i)}_{j}$,
$v^{(i)}_{j,h}$ and $w^{(i)}_{j,h^{\prime}}$ respectively correspond to
$u_{j}$, $v_{j,h}$ and $w_{j,h^{\prime}}$, by adding edges
$u^{(i)}_{2}u^{(i+1)}_{1}$ (indices are to be read modulo $s$).

$u_{1}$$u_{2}$$v_{1,1}$$v_{1,2}$$v_{2,2}$$v_{2,1}$$w_{1,1}$$w_{1,2}$$w_{1,3}$$w_{1,4}$$w_{2,4}$$w_{2,3}$$w_{2,2}$$w_{2,1}$
Figure 6: Graph $A^{\prime}$

###### Lemma 2.4

For an integer $s\geq 4$, $H^{(3)}_{s}$ is $S_{7}(1,0,1)$-free.

###### Proof.

Suppose that $H^{(3)}_{s}$ contains an induced subgraph $T$ which is
isomorphic to $S_{7}(1,0,1)$. Let $S$ be the subtree of $T$ which is
isomorphic to $S_{7}(1,0,0)$. Let $x$ be the unique vertex of $S$ with
$d_{S}(x)=3$ such that no leaf of $S$ is adjacent to $x$. Without loss of
generality, we may assume that
$x\in\\{w^{(1)}_{1,1},v^{(1)}_{1,1},u^{(1)}_{1}\\}$.

We show that $x\neq w^{(1)}_{1,1}$. Let $S^{\prime}$ be an induced subtree of
$H^{(3)}_{s}$ isomorphic to $T_{5}$ such that $w^{(1)}_{1,1}$ is the unique
vertex of $S^{\prime}$ having degree $3$. Then we see that $S^{\prime}$ is
equal to either

$H^{(3)}_{s}[\\{u^{(1)}_{1},v^{(1)}_{1,1},w^{(1)}_{1,1},w^{(1)}_{2,2},w^{(1)}_{1,3},w^{(1)}_{2,1},w^{(1)}_{2,3}\\}]\mbox{~{}~{}or~{}~{}}H^{(3)}_{s}[\\{w^{(1)}_{1,2},v^{(1)}_{1,1},w^{(1)}_{1,1},v^{(1)}_{1,2},w^{(1)}_{1,3},w^{(1)}_{2,1},v^{(1)}_{2,1}\\}].$

In either case, we can verify that no induced subgraph of $H^{(3)}_{s}$
isomorphic to $S_{5}(1)$ contains all vertices of $S^{\prime}$. Since
$S_{5}(1)\prec S_{7}(1,0,0)$, this implies $x\neq w^{(1)}_{1,1}$. Thus
$x\in\\{v^{(1)}_{1,1},u^{(1)}_{1}\\}$.

We make the following two observations.

  1. $\bullet$

Assume that $x=v^{(1)}_{1,1}$. Then by the symmetry of vertices of
$A^{\prime}_{1}$, we may assume that

$S=H^{(3)}_{s}[\\{u^{(s)}_{2},u^{(1)}_{1},v^{(1)}_{1,1},w^{(1)}_{1,3},w^{(1)}_{1,1},w^{(1)}_{1,2},w^{(1)}_{1,4},w^{(1)}_{2,3},v^{(1)}_{2,2},u^{(1)}_{2}\\}].$

Note that $N_{H^{(3)}_{s}}(v^{(1)}_{2,2})-V(S)=\\{w^{(1)}_{2,4}\\}$.

  2. $\bullet$

Assume that $x=u^{(1)}_{1}$. Then by the symmetry of vertices of
$A^{\prime}_{1}$ and the symmetry of vertices of $A^{\prime}_{s}$, we may
assume that

$S=H^{(3)}_{s}[\\{w^{(1)}_{1,1},v^{(1)}_{1,1},u^{(1)}_{1},w^{(1)}_{1,4},v^{(1)}_{1,2},u^{(s)}_{2},v^{(s)}_{2,2},v^{(s)}_{2,1},w^{(s)}_{2,1},w^{(s)}_{1,1}\\}].$

Note that $N_{H^{(3)}_{s}}(w^{(s)}_{2,1})-V(S)=\\{w^{(s)}_{2,3}\\}$.

If $x=v^{(1)}_{1,1}$, let $y=w^{(1)}_{2,4}$; if $x=u^{(1)}_{1}$, let
$y=w^{(s)}_{2,3}$. Then in either case, it follows from the above observations
that $V(T)-V(S)=\\{y\\}$, which forces $T$ to contain a cycle, a
contradiction. ∎

For an integer $s\geq 3$, we let $H^{(4)}_{s}$ be the graph obtained from $s$
pairwise vertex-disjoint copies $B_{1},\ldots,B_{s}$ of $H^{(1)}_{1}$ such
that $V(B_{i})=\\{\tilde{u}^{(i)}_{j},v^{(i)}_{h}:1\leq j\leq 6,~{}1\leq h\leq
3\\}$ where $\tilde{u}^{(i)}_{j}$ and $v^{(i)}_{h}$ respectively correspond to
$u^{(1)}_{j}$ and $v_{h}$, by adding a new vertex $z$ and edges
$zv^{(i)}_{h}~{}(1\leq i\leq s,~{}1\leq h\leq 3)$ (see Figure 7).

$\tilde{u}^{(1)}_{1}$$\tilde{u}^{(1)}_{3}$$\tilde{u}^{(1)}_{5}$$\tilde{u}^{(1)}_{6}$$\tilde{u}^{(1)}_{4}$$\tilde{u}^{(1)}_{2}$$\tilde{u}^{(s)}_{1}$$\tilde{u}^{(s)}_{3}$$\tilde{u}^{(s)}_{5}$$\tilde{u}^{(s)}_{6}$$\tilde{u}^{(s)}_{4}$$\tilde{u}^{(s)}_{2}$$v^{(1)}_{1}$$v^{(1)}_{3}$$v^{(1)}_{2}$$v^{(s)}_{1}$$v^{(s)}_{3}$$v^{(s)}_{2}$$z$
Figure 7: Graph $H^{(4)}_{s}$

###### Lemma 2.5

For an integer $s\geq 3$, $H^{(4)}_{s}$ is $S_{8}^{(2)}$-free.

###### Proof.

Note that the subgraph of $H^{(4)}_{s}$ induced by $V(B_{i})\cup\\{z\\}$ is
isomorphic to the Petersen graph. Let $P$ be an induced path of $H^{(4)}_{s}$
having $8$ vertices. Since the Petersen graph is $P_{6}$-free, it follows from
the symmetry of vertices of $H^{(4)}_{s}$ that we may assume that
$P=\tilde{u}^{(1)}_{3}\tilde{u}^{(1)}_{2}\tilde{u}^{(1)}_{1}v^{(1)}_{1}zv^{(2)}_{1}\tilde{u}^{(2)}_{1}\tilde{u}^{(2)}_{2}$.
Then $N_{H^{(4)}_{s}}(v^{(1)}_{1})-V(P)=\\{\tilde{u}^{(1)}_{4}\\}$. Since the
subgraph of $H^{(4)}_{s}$ induced by $V(P)\cup\\{\tilde{u}^{(1)}_{4}\\}$
contains a cycle, no induced subgraph of $H_{s}^{(4)}$ isomorphic to
$S_{8}^{(2)}$ contains all vertices of $P$. This implies that $H^{(4)}_{s}$ is
$S_{8}^{(2)}$-free. ∎

Proof of Theorem 1.2. Let $T$ be a tree with ${\rm diam}(T)\geq 7$ which is
not a caterpillar, and suppose that
$\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$ is a finite family. By Lemma
2.1, there exist infinitely many connected $3$-regular graphs with girth at
least $5$. Since $\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$ is finite,
there exists a connected $3$-regular graph containing an induced subgraph
isomorphic to $T$. This implies that $\Delta(T)\leq 3$.

For each $s\geq 5$, $H^{(1)}_{s}$ is a connected $\\{C_{3},C_{4}\\}$-free
graph with $\delta(H^{(1)}_{s})\geq 3$. Since
$\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$ is finite, there exists
$s_{1}\geq 5$ such that $T\prec H^{(1)}_{s_{1}}$. By Lemma 2.2(i), we have
${\rm diam}(T)\leq 8$. Furthermore, it follows from Lemma 2.2(ii)(iii) that

if ${\rm diam}(T)=8$, then $T\prec T^{*}_{9}$; and (2.2) if ${\rm diam}(T)=7$,
then $T\prec S_{8}(0,0,0,1)$ or $T\prec S_{8}^{(1)}$. (2.3)

For each $s\geq 3$, $H^{(2)}_{s}$ is a connected $\\{C_{3},C_{4}\\}$-free
graph with $\delta(H^{(2)}_{s})\geq 3$. Since
$\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$ is finite, there exists
$s_{2}\geq 3$ such that $T\prec H^{(2)}_{s_{2}}$. Then by Lemma 2.3,

$\displaystyle S_{8}(0,0,0,1)\not\prec T;\mbox{ and}$ (2.4) $\displaystyle
T^{*}_{8}\not\prec T.$ (2.5)

Since $T$ is not a caterpillar, it follows from (2.2) and (2.4) that if ${\rm
diam}(T)=8$, then $T$ is isomorphic to $T_{9}$, as desired. Thus we may assume
that ${\rm diam}(T)=7$. Note that if a tree $S$ with ${\rm diam}(S)=7$ is not
a caterpillar and satisfies $S_{8}(0,0,0,1)\not\prec S\prec S_{8}(0,0,0,1)$,
then $S\simeq T_{8}~{}(\prec S_{8}^{(1)})$. Hence by (2.3) and (2.4), we have
$T\prec S_{8}^{(1)}$. This together with (2.5) implies that

$\displaystyle T\prec S_{8}(1,1,1,0).$ (2.6)

For each $s\geq 4$, $H^{(3)}_{s}$ is a connected $\\{C_{3},C_{4}\\}$-free
graph with $\delta(H^{(3)}_{s})\geq 3$. Since
$\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$ is finite, there exists
$s_{3}\geq 4$ such that $T\prec H^{(3)}_{s_{3}}$. Then by Lemma 2.4,
$S_{7}(1,0,1)\not\prec T$. This together with (2.6) leads to $T\prec
S_{8}(1,1,0,0)$ or $T\prec S_{8}(0,1,1,0)$. Since $S_{8}(0,1,1,0)\simeq
T_{8}^{(1)}$, the latter case leads to the desired conclusion. Thus we may
assume that

$\displaystyle S_{8}(1,0,0,0)\prec T\prec S_{8}(1,1,0,0).$ (2.7)

For each $s\geq 3$, $H^{(4)}_{s}$ is a connected $\\{C_{3},C_{4}\\}$-free
graph with $\delta(H^{(4)}_{s})\geq 3$. Since
$\tilde{{\mathcal{G}}}_{3}(\\{C_{3},C_{4},T\\})$ is finite, there exists
$s_{4}\geq 3$ such that $T\prec H^{(4)}_{s_{4}}$. Then by Lemma 2.5,
$S_{8}^{(2)}\not\prec T$. This together with (2.7) leads to $T\simeq
S_{8}(1,0,0,0)~{}(\simeq T_{8}^{(2)})$, as desired. ∎

##  3 Proof of Theorem 1.3

In the remainder of this paper, we fix a connected $\\{C_{3},C_{4}\\}$-free
graph $G$ with $\delta(G)\geq 3$. We implicitly use the fact that $N_{G}(u)$
is an independent set of $G$ and $|N_{G}(u)\cap N_{G}(v)|\leq 1$ for any
$u,v\in V(G)$ with $u\neq v$. For $u\in V(G)$ and $U\subseteq V(G)$, we write
$N(u)$ and $N(U)$ for $N_{G}(u)$ and $N_{G}(U)$, respectively. Furthermore, in
this section, we fix two vertices $u,v\in V(G)$ with ${\rm dist}_{G}(u,v)={\rm
diam}(G)$ and a shortest $u$-$v$ path $P=u_{0}u_{1}\cdots u_{d}$ of $G$ where
$d={\rm diam}(G)$, $u_{0}=u$ and $u_{d}=v$. For each $i~{}(0\leq i\leq d)$, we
fix a vertex $a_{i}\in N(u_{i})-V(P)$.

###### Lemma 3.1

  1. (i)

For $y\in V(G)-V(P)$, $|N(y)\cap V(P)|\leq 1$. In particular, $N(a_{i})\cap
V(P)=\\{u_{i}\\}$ for $0\leq i\leq d$, and $a_{i}\neq a_{i^{\prime}}$ for
$0\leq i<i^{\prime}\leq d$.

  2. (ii)

For $0\leq i<i^{\prime}\leq d$, if $a_{i}a_{i^{\prime}}\in E(G)$, then $2\leq
i^{\prime}-i\leq 3$.

###### Proof.

We first prove (i). Let $y\in V(G)-V(P)$, and suppose that there exist
integers $i$ and $i^{\prime}$ with $0\leq i<i^{\prime}\leq d$ such that
$yu_{i},yu_{i^{\prime}}\in E(G)$. Since $G$ is $\\{C_{3},C_{4}\\}$-free,
$i^{\prime}-i\geq 3$. Then $u_{0}u_{1}\cdots
u_{i}yu_{i^{\prime}}u_{i^{\prime}+1}\cdots u_{d}$ is a $u$-$v$ path of $G$
having length $i+2+(d-i^{\prime})~{}(\leq d-1)$, which contradicts the fact
that ${\rm dist}_{G}(u,v)=d$.

Next we prove (ii). Since $G$ is $C_{4}$-free, we have $i^{\prime}-i\geq 2$.
If $i^{\prime}-i\geq 4$, then $u_{0}u_{1}\cdots
u_{i}a_{i}a_{i^{\prime}}u_{i^{\prime}}u_{i^{\prime}+1}\cdots u_{d}$ is a
$u$-$v$ path of $G$ having length $i+3+(d-i^{\prime})~{}(\leq d-1)$, which
contradicts the fact that ${\rm dist}_{G}(u,v)=d$. ∎

Proof of Theorem 1.3. We first prove (iii). Suppose that ${\rm diam}(G)\geq
12$. We show that $T_{9}\prec G$. Take a vertex $y\in N(a_{6})-\\{u_{6}\\}$.
By Lemma 3.1, we have $y\notin V(P)$, $|N(y)\cap V(P)|\leq 1$ and $N(y)\cap
V(P)\subseteq\\{u_{3},u_{4},u_{8},u_{9}\\}$. We may assume that
$yu_{8},yu_{9}\notin E(G)$. Then $N(y)\cap\\{a_{6},u_{i}:5\leq i\leq
12\\}=\\{a_{6}\\}$. Since $|N(y)\cap N(u_{5})|\leq 1$, we can take a vertex
$z\in\\{u_{4},a_{5}\\}-N(y)$. Considering Lemma 3.1, we have
$N(z)\cap\\{y,a_{6},u_{i}:5\leq i\leq 12\\}=\\{u_{5}\\}$. Hence
$\\{z,u_{5},u_{6},y,a_{6},u_{7},\ldots,u_{12}\\}$ induces a copy of $T_{9}$ in
$G$, which proves (iii).

Next we prove (i) and (ii). Let $d_{1}=20$, $d_{2}=16$ and $p\in\\{1,2\\}$. We
suppose that ${\rm diam}(G)\geq d_{p}$, and show that $T_{8}^{(p)}\prec G$.

###### Claim 3.1

Let $i$ be an integer with $5\leq i\leq d-5$, and suppose that there exists a
vertex $y\in N(a_{i})-\\{u_{i}\\}$ such that $yu_{j}\in E(G)$ for some $0\leq
j\leq d$ with $|i-j|\geq 3$. Then $T_{8}^{(1)}\prec G$ and $T_{8}^{(2)}\prec
G$.

###### Proof.

Without loss of generality, we may assume that $i-j\geq 3$ and $y=a_{j}$. Then
by Lemma 3.1(ii), $j=i-3$, i.e., $a_{i}a_{i-3}\in E(G)$. If
$E_{G}(\\{a_{i-3},a_{i}\\},\\{a_{i+1},a_{i+2},a_{i+3}\\})\neq\emptyset$, then
it follows from Lemma 3.1(ii) that $a_{i}a_{h}\in E(G)$ for some
$h\in\\{i+2,i+3\\}$, and hence $u_{0}u_{1}\cdots
u_{i-3}a_{i-3}a_{i}a_{h}u_{h}u_{h+1}\cdots u_{d}$ is a $u$-$v$ path of $G$
having length $(i-3)+4+(d-h)~{}(=d+i-h+1\leq d-1)$, which contradicts the fact
that ${\rm dist}_{G}(u,v)=d$. Thus
$E_{G}(\\{a_{i-3},a_{i}\\},\\{a_{i+1},a_{i+2},a_{i+3}\\})=\emptyset$. Since
$a_{i+2}a_{i+3}\notin E(G)$ by Lemma 3.1(ii),
$\\{u_{i-2},u_{i-1},u_{i},a_{i-3},a_{i},u_{i+1},u_{i+2},a_{i+2},u_{i+3},a_{i+3},u_{i+4},u_{i+5}\\}$
induces a copy of $T_{8}^{(1)}$ in $G$. Furthermore,
$\\{u_{i-2},u_{i-1},u_{i},a_{i-3},a_{i},u_{i+1},a_{i},u_{i+1},\ldots,u_{i+5}\\}$
induces a copy of $T_{8}^{(2)}$ in $G$. ∎

###### Claim 3.2

Let $i$ be an integer with $5\leq i\leq d-5$, and suppose that
$a_{i}a_{i+h}\in E(G)$ for some $h\in\\{2,-2\\}$.

  1. (a)

If $a_{i}a_{i-h}\notin E(G)$, then $T_{8}^{(1)}\prec G$.

  2. (b)

If $a_{i-1}a_{i+1}\notin E(G)$, then $T_{8}^{(2)}\prec G$.

###### Proof.

We may assume that $h=-2$, i.e., $a_{i}a_{i-2}\in E(G)$. In view of Lemma
3.1(ii) and Claim 3.1, we may assume that $E(G[\\{a_{j}:i-2\leq j\leq
i+3\\}])\subseteq\\{a_{j}a_{j+2}:i-2\leq j\leq i+1\\}$. This implies that if
$a_{i}a_{i+2}\notin E(G)$, then
$\\{a_{i-1},u_{i-1},u_{i},a_{i-2},a_{i},u_{i+1},u_{i+2},a_{i+2},u_{i+3},a_{i+3},u_{i+4},u_{i+5}\\}$
induces a copy of $T_{8}^{(1)}$ in $G$; if $a_{i-1}a_{i+1}\notin E(G)$, then
$\\{a_{i-1},u_{i-1},u_{i},a_{i-2},a_{i},u_{i+1},a_{i+1},u_{i+2},\ldots,u_{i+5}\\}$
induces a copy of $T_{8}^{(2)}$ in $G$. Thus we obtain the desired
conclusions. ∎

###### Claim 3.3

Let $i$ be an integer with $6+p\leq j\leq d-(6+p)$, and let $y\in
N(a_{j})-\\{u_{j}\\}$. If $N(y)\cap V(P)\neq\emptyset$, then $T_{8}^{(p)}\prec
G$.

###### Proof.

By way of contradiction, suppose that $yu_{j^{\prime}}\in E(G)$ for some
$0\leq j^{\prime}\leq d$ with $j^{\prime}\neq j$ and $G$ is
$T_{8}^{(p)}$-free. We may assume that $y=a_{j^{\prime}}$. Then by Lemma
3.1(ii) and Claim 3.1, we have $|j-j^{\prime}|=2$. We may assume that
$j-j^{\prime}=2$, i.e., $a_{j}a_{j-2}\in E(G)$.

Now we claim that

$\displaystyle a_{j}a_{j+2},a_{j+2}a_{j+4}\in E(G).$ (3.1)

If $p=1$, then $7\leq j<j+2\leq d-5$, and hence applying Claim 3.2(a) with
$(i,h)=(j,-2)$ and then with $(i,h)=(j+2,-2)$, we get
$a_{j}a_{j+2},a_{j+2}a_{j+4}\in E(G)$, as desired; if $p=2$, then $8\leq
j<j+3\leq d-5$, and hence applying Claim 3.2(b) with $(i,h)=(j+\alpha,-2)$ for
$0\leq\alpha\leq 3$, we obtain
$a_{j-1}a_{j+1},a_{j}a_{j+2},a_{j+1}a_{j+3},a_{j+2}a_{j+4}\in E(G)$, which
implies (3.1).

By the fact that $a_{j}a_{j-2}\in E(G)$ and (3.1), $u_{0}u_{1}\cdots
u_{j-2}a_{j-2}a_{j}a_{j+2}a_{j+4}u_{j+4}u_{j+5}\cdots u_{d}$ is a $u$-$v$ path
of $G$ having length $(j-2)+5+(d-(j+4))~{}(=d-1)$, which contradicts the fact
that ${\rm dist}_{G}(u,v)=d$. ∎

###### Claim 3.4

There exists an integer $i_{0}\in\\{7,10,13\\}$ such that $N(a_{i_{0}})\cap
N(a_{i_{0}+3})=\emptyset$.

###### Proof.

If $N(a_{i})\cap N(a_{i+3})\neq\emptyset$ for all $i\in\\{7,10,13\\}$, then
there exists an $a_{7}$-$a_{16}$ path $Q$ of $G-V(P)$ having length at most
$6$, and hence $u_{0}u_{1}\cdots u_{7}a_{7}Qa_{16}u_{16}u_{17}\cdots u_{d}$ is
a $u$-$v$ path of length at most $7+8+(d-16)~{}(=d-1)$, which contradicts the
fact that ${\rm dist}_{G}(u,v)=d$. ∎

Now we complete the proof of the theorem. We first consider the case where
$p=1$. Let $i_{0}\in\\{7,10,13\\}$ be as in Claim 3.4. Since
$|N(a_{i_{0}})\cap N(a_{i_{0}+2})|\leq 1$, there exists a vertex $y\in
N(a_{i_{0}})-(\\{u_{i_{0}}\\}\cup N(a_{i_{0}+2}))$. By Claim 3.3, we may
assume that $N(y)\cap V(P)=\emptyset$ and
$\\{a_{i_{0}},a_{i_{0}+2},a_{i_{0}+3}\\}$ is an independent set of $G$. In
particular, $y\notin\\{a_{i_{0}+2},a_{i_{0}+3}\\}$. Furthermore, it follows
from the definition of $i_{0}$ and $y$ that $\\{y,a_{i_{0}+2},a_{i_{0}+3}\\}$
is also an independent set of $G$. Consequently,
$\\{u_{i_{0}-2},u_{i_{0}-1},u_{i_{0}},y,a_{i_{0}},u_{i_{0}+1},u_{i_{0}+2},a_{i_{0}+2},u_{i_{0}+3},a_{i_{0}+3},u_{i_{0}+4},u_{i_{0}+5}\\}$
induces a copy of $T_{8}^{(1)}$ in $G$.

Finally we consider the case where $p=2$. Recall that $a_{8}\neq a_{9}$ and
$a_{8}a_{9}\notin E(G)$. Since $|N(a_{8})\cap N(a_{9})|\leq 1$, there exists a
vertex $y^{\prime}\in N(a_{8})-(\\{u_{8}\\}\cup N(a_{9}))$. By Claim 3.3, we
may assume that $N(y^{\prime})\cap V(P)=\emptyset$. Consequently,
$\\{u_{6},u_{7},u_{8},y^{\prime},a_{8},u_{9},a_{9},u_{10},\ldots,u_{13}\\}$
induces a copy of $T_{8}^{(2)}$ in $G$.

This completes the proof of Theorem 1.3. ∎

##  4 Paths between two vertices and the existence of induced trees

For an integer $k\geq 4$ and two non-adjacent vertices $v$ and $w$ of $G$, an
induced $v$-$w$ path $P$ of $G$ with $|V(P)|=k$ is called a $(v,w;k)$-path.
Let

$M_{k}^{w}(v)=\\{x\in V(G):\mbox{there exists a $(v,w;k)$-path $P$ such that
$N(v)\cap V(P)=\\{x\\}$}\\}.$

###### Lemma 4.1

Let $k\geq 4$ be an integer, and let $v$ and $w$ be non-adjacent vertices of
$G$. For $i\in\\{1,2\\}$, let $Q_{i}=u^{(i)}_{1}u^{(i)}_{2}\cdots u^{(i)}_{k}$
be a $(v,w;k)$-path where $u^{(i)}_{1}=v$ and $u^{(i)}_{k}=w$, and suppose
that $u^{(1)}_{2}\neq u^{(2)}_{2}$. Then the following hold.

  1. (i)

We have
$\\{u^{(1)}_{2},u^{(1)}_{3}\\}\cap\\{u^{(2)}_{2},u^{(2)}_{3}\\}=\emptyset$.

  2. (ii)

If $k=5$,
$\\{u^{(1)}_{2},u^{(1)}_{3},u^{(1)}_{4}\\}\cap\\{u^{(2)}_{2},u^{(2)}_{3}\\}=\emptyset$.

  3. (iii)

If $k=4$, then
$E_{G}(\\{u^{(1)}_{2},u^{(1)}_{3}\\},\\{u^{(2)}_{2},u^{(2)}_{3}\\})=\emptyset$.

  4. (iv)

If $k=5$ and $u^{(1)}_{4}\neq u^{(2)}_{4}$, then
$E_{G}(\\{u^{(1)}_{2},u^{(1)}_{3},u^{(1)}_{4}\\},\\{u^{(2)}_{2},u^{(2)}_{3},u^{(2)}_{4}\\})\subseteq\\{u^{(1)}_{2}u^{(2)}_{4},u^{(1)}_{3}u^{(2)}_{3},u^{(1)}_{4}u^{(2)}_{2}\\}$.

  5. (v)

If $k=5$, $u^{(1)}_{4}\neq u^{(2)}_{4}$ and $u^{(1)}_{2}\notin M_{4}^{w}(v)$,
then
$E_{G}(\\{u^{(1)}_{2},u^{(1)}_{3},u^{(1)}_{4}\\},\\{u^{(2)}_{2},u^{(2)}_{3},u^{(1)}_{4}\\})\subseteq\\{u^{(1)}_{3}u^{(2)}_{3},u^{(1)}_{4}u^{(2)}_{2}\\}$.

###### Proof.

Since $G$ is $\\{C_{3},C_{4}\\}$-free, we see that (i) and (iii) hold. If
$k=5$ and $u^{(1)}_{4}\in\\{u^{(2)}_{2},u^{(2)}_{3}\\}$, then
$N(w)\cap\\{u^{(2)}_{2},u^{(2)}_{3}\\}\neq\emptyset$, and hence $Q_{2}$ is not
an induced path, which is a contradiction. Thus we obtain (ii). By the
$\\{C_{3},C_{4}\\}$-freeness of $G$ and (ii), we get (iv). If $k=5$ and
$u^{(1)}_{2}u^{(2)}_{4}\in E(G)$, then $vu^{(1)}_{2}u^{(2)}_{4}w$ is a
$(v,w;4)$-path. This together with (iv) leads to (v). ∎

For integers $p_{1},p_{2}\geq 1$, let $T_{8}^{*}(p_{1},p_{2})$ be the tree of
order $2p_{1}+2p_{2}+6$ depicted in Figure 8. Note that $T_{8}^{*}(1,2)\simeq
T_{8}^{(1)}$ and $T_{8}^{(2)}\prec T_{8}^{*}(2,1)$.

$\underbrace{\hskip 36.98857pt}_{p_{1}}$$\underbrace{\hskip
36.98857pt}_{p_{2}}$ Figure 8: Graph $T_{8}^{*}(p_{1},p_{2})$

###### Lemma 4.2

Let $p_{1},p_{2}\geq 1$ be integers, and let
$n=2R(3,p_{1}+2)+3R(3,p_{2})+2p_{2}(p_{1}+p_{2}+1)+3$. Let $v$ and $w$ be non-
adjacent vertices of $G$. If $|M_{4}^{w}(v)|\geq n$, then
$T_{8}^{*}(p_{1},p_{2})\prec G$.

###### Proof.

Let $n_{1}=R(3,p_{1}+2)+p_{2}(p_{1}+p_{2}+1)$ and $n_{2}=R(3,p_{2})+1$. Note
that $n=2n_{1}+3n_{2}$. Let $a_{1},\ldots,a_{n}$ be distinct vertices in
$M_{4}^{w}(v)$. Then for each $i~{}(1\leq i\leq n)$, there exists a vertex
$b_{i}\in V(G)$ such that $Q_{i}=va_{i}b_{i}w$ is a $(v,w;4)$-path. By Lemma
4.1(i)(iii), $\\{a_{i},b_{i}\\}\cap\\{a_{j},b_{j}\\}=\emptyset$ and
$E_{G}(\\{a_{i},b_{i}\\},\\{a_{j},b_{j}\\})=\emptyset$ for $1\leq i<j\leq n$.
For $i~{}(1\leq i\leq n_{1}+n_{2})$, take $x_{i}\in N(a_{i})-\\{v,b_{i}\\}$.
Then by Lemma 4.1(iii), $\\{x_{i}:1\leq i\leq
n_{1}+n_{2}\\}\cap\\{v,w,a_{i},b_{i}:1\leq i\leq n\\}=\emptyset$. Since $G$ is
$\\{C_{3},C_{4}\\}$-free, $N(x_{i})\cap\\{v,w,a_{j}:1\leq j\leq n,~{}j\neq
i\\}=\emptyset$ for each $i~{}(1\leq i\leq n_{1}+n_{2})$ and, in particular,
$x_{1},\ldots,x_{n_{1}+n_{2}}$ are distinct. Since
$|N(x_{i})\cap\\{b_{j}:1\leq j\leq n\\}|\leq|N(x_{i})\cap N(w)|\leq 1$, we
have $|N(\\{x_{i}:1\leq i\leq n_{1}+n_{2}\\})\cap\\{b_{i}:n_{1}+n_{2}+1\leq
i\leq n\\}|\leq n_{1}+n_{2}$. Since $n-(n_{1}+n_{2})=n_{1}+2n_{2}$, we may
assume that $N(\\{x_{i}:1\leq i\leq
n_{1}+n_{2}\\})\cap\\{b_{i}:n_{1}+n_{2}+1\leq i\leq
n_{1}+2n_{2}\\}=\emptyset$. For each $i~{}(n_{1}+n_{2}+1\leq i\leq
n_{1}+2n_{2})$, take $y_{i}\in N(b_{i})-\\{w,a_{i}\\}$. Set
$Y=\\{y_{i}:n_{1}+n_{2}+1\leq i\leq n_{1}+2n_{2}\\}$. Then by Lemma 4.1(iii),
$Y\cap\\{v,w,a_{i},b_{i}:1\leq i\leq n_{1}+n_{2}\\}=\emptyset$. Since $G$ is
$\\{C_{3},C_{4}\\}$-free, $N(y_{i})\cap\\{v,w,b_{j}:1\leq j\leq
n_{1}+2n_{2},~{}j\neq i\\}=\emptyset$ for each $i~{}(n_{1}+n_{2}+1\leq i\leq
n_{1}+2n_{2})$ and, in particular, $y_{n_{1}+n_{2}+1},\ldots,y_{n_{1}+2n_{2}}$
are distinct. Since $N(\\{x_{i}:1\leq i\leq
n_{1}+n_{2}\\})\cap\\{b_{i}:n_{1}+n_{2}+1\leq i\leq
n_{1}+2n_{2}\\}=\emptyset$, we also have $Y\cap\\{x_{i}:1\leq i\leq
n_{1}+n_{2}\\}=\emptyset$. Since $|Y|=n_{2}$ and $|N(y_{i})\cap\\{a_{j}:1\leq
j\leq n_{1}+n_{2}\\}|\leq|N(y_{i})\cap N(v)|\leq 1$ for each
$i~{}(n_{1}+n_{2}+1\leq i\leq n_{1}+2n_{2})$, we may assume that
$N(Y)\cap\\{a_{i}:1\leq i\leq n_{1}\\}=\emptyset$. Set $X=\\{x_{i}:1\leq i\leq
n_{1}\\}$. We have the following:

$\displaystyle
x_{1},\ldots,x_{n_{1}},y_{n_{1}+n_{2}+1},\ldots,y_{n_{1}+2n_{2}}\mbox{ are
distinct};$ (4.1) $\displaystyle(X\cup Y)\cap\left(\bigcup_{1\leq i\leq
n_{1}+2n_{2}}V(Q_{i})\right)=\emptyset;$ (4.2) $\displaystyle
N(x_{i})\cap\left(\bigcup_{n_{1}+n_{2}+1\leq j\leq
n_{1}+2n_{2}}V(Q_{j})\right)=\emptyset\mbox{ for }1\leq i\leq n_{1};$ (4.3)
$\displaystyle N(x_{i})\cap\\{a_{j}:1\leq j\leq n_{1},~{}j\neq
i\\}=\emptyset\mbox{ for }1\leq i\leq n_{1};$ (4.4) $\displaystyle
N(y_{i})\cap\left(\bigcup_{1\leq j\leq n_{1}}V(Q_{j})\right)=\emptyset\mbox{
for }n_{1}+n_{2}+1\leq i\leq n_{1}+2n_{2};\mbox{ and}$ (4.5) $\displaystyle
N(y_{i})\cap\\{b_{j}:n_{1}+n_{2}+1\leq j\leq n_{1}+2n_{2},~{}j\neq
i\\}=\emptyset\mbox{ for }n_{1}+n_{2}+1\leq i\leq n_{1}+2n_{2}.$ (4.6)

###### Claim 4.1

There exists $X_{0}\subseteq X$ and there exists $Y_{0}\subseteq Y$ with
$|X_{0}|=p_{1}+2$ and $|Y_{0}|=p_{2}$ such that $X_{0}\cup Y_{0}$ is an
independent set of $G$.

###### Proof.

We first assume that there exists $u_{0}\in Y$ such that $|N(u_{0})\cap X|\geq
p_{1}+p_{2}+2$. Note that $N(u_{0})\cap X$ is an independent set of $G$. Since
$G$ is $C_{3}$-free and $|Y-\\{u_{0}\\}|=n_{2}-1=R(3,p_{2})$, there exists an
independent set $Y_{0}\subseteq Y-\\{u_{0}\\}$ of $G$ with $|Y_{0}|=p_{2}$. We
have $|N(u_{0})\cap X\cap N(y)|\leq|N(u_{0})\cap N(y)|\leq 1$ for each $y\in
Y_{0}$. In particular, $|(N(u_{0})\cap
X)-N(Y_{0})|\geq(p_{1}+p_{2}+2)-p_{2}=p_{1}+2$. Take
$X_{0}\subseteq(N(u_{0})\cap X)-N(Y_{0})$ with $|X_{0}|=p_{1}+2$. Then
$X_{0}\cup Y_{0}$ is an independent set of $G$, as desired. Thus we may assume
that

$|N(y)\cap X|\leq p_{1}+p_{2}+1$ for all $y\in Y$. (4.7)

Since $G$ is $C_{3}$-free and $|Y|>R(3,p_{2})$, there exists an independent
set $Y_{0}\subseteq Y$ of $G$ with $|Y_{0}|=p_{2}$. By (4.7),

$\displaystyle|X-N(Y_{0})|$ $\displaystyle\geq n_{1}-\sum_{y\in
Y_{0}}|N(y)\cap X|$
$\displaystyle\geq(R(3,p_{1}+2)+p_{2}(p_{1}+p_{2}+1))-p_{2}(p_{1}+p_{2}+1)$
$\displaystyle=R(3,p_{1}+2).$

Since $G$ is $C_{3}$-free, there exists an independent set $X_{0}\subseteq
X-N(Y_{0})$ of $G$ with $|X_{0}|=p_{1}+2$. Then $X_{0}\cup Y_{0}$ is an
independent set of $G$. ∎

By Claim 4.1, we may assume that

$\displaystyle\\{x_{1},\ldots,x_{p_{1}+2},y_{n_{1}+n_{2}+1},\ldots,y_{n_{1}+n_{2}+p_{2}}\\}\mbox{
is an independent set of }G.$ (4.8)

For each $i~{}(1\leq i\leq p_{1}+2)$, let $I_{i}=\\{j:1\leq j\leq
p_{1}+2,~{}x_{j}b_{i}\in E(G)\\}$. For $1\leq j\leq p_{1}+2$, since
$|N(x_{j})\cap N(w)|\leq 1$, $j$ belongs to at most one of
$I_{1},\ldots,I_{p_{1}+2}$. In particular, $I_{1},\ldots,I_{p_{1}+2}$ are
pairwise disjoint. Consequently, $\sum_{1\leq i\leq
p_{1}+2}|I_{i}|=|\bigcup_{1\leq i\leq p_{1}+2}I_{i}|\leq p_{1}+2$. This
implies that there exists $i_{0}$ with $1\leq i_{0}\leq p_{1}+2$ such that
$|I_{i_{0}}|\leq 1$. We may assume that $i_{0}=1$ and $2,\ldots,p_{1}+1\notin
I_{1}$, that is,

$\displaystyle N(b_{1})\cap\\{x_{j}:2\leq j\leq p_{1}+1\\}=\emptyset.$ (4.9)

Since $b_{1}x_{1}\notin E(G)$ by the $C_{3}$-freeness of $G$, it follows from
(4.1)–(4.6), (4.8) and (4.9) that

$\\{a_{i},x_{i}:1\leq i\leq
p_{1}+1\\}\cup\\{v,a_{p_{1}+2},b_{1},w\\}\cup\\{b_{i},y_{i}:n_{1}+n_{2}+1\leq
i\leq n_{1}+n_{2}+p_{2}\\}$

induces a copy of $T_{8}^{*}(p_{1},p_{2})$ in $G$ (see Figure 9). ∎

$w$$v$$a_{1}$$a_{2}$$a_{p_{1}+1}$$a_{p_{1}+2}$$a_{n_{1}+n_{2}+1}$$a_{n_{1}+n_{2}+p_{2}}$$x_{1}$$x_{p_{1}+1}$$y_{n_{1}+n_{2}+1}$$y_{n_{1}+n_{2}+p_{2}}$$b_{1}$$b_{2}$$b_{p_{1}+1}$$b_{p_{1}+2}$$b_{n_{1}+n_{2}+1}$$b_{n_{1}+n_{2}+p_{2}}$$x_{2}$
Figure 9: An induced copy of $T_{8}^{*}(p_{1},p_{2})$ in Lemma 4.2

Recall that $T_{8}^{*}(1,2)\simeq T_{8}^{(1)}$ and $T_{8}^{(2)}\prec
T_{8}^{*}(2,1)$. Since $R(3,1)=1$, $R(3,2)=3$, $R(3,3)=6$ and $R(3,4)=9$ (see
[11]), we obtain the following as a corollary of Lemma 4.2.

###### Lemma 4.3

Let $v$ and $w$ be non-adjacent vertices of $G$.

  1. (i)

If $|M_{4}^{w}(v)|\geq 40$, then $T_{8}^{(1)}\prec G$.

  2. (ii)

If $|M_{4}^{w}(v)|\geq 32$, then $T_{8}^{(2)}\prec G$.

###### Lemma 4.4

Let $v$ and $w$ be non-adjacent vertices of $G$.

  1. (i)

If $|M_{4}^{w}(v)\cup M_{5}^{w}(v)|\geq 4837$, then $T_{8}^{(1)}\prec G$.

  2. (ii)

If $|M_{4}^{w}(v)\cup M_{5}^{w}(v)|\geq 2047$, then $T_{8}^{(2)}\prec G$.

###### Proof.

Let $h_{1}=40$, $m_{1}=124$, $h_{2}=32$ and $m_{2}=66$. Note that
$h_{1}m_{1}-m_{1}+1=4837$ and $h_{2}m_{2}-m_{2}+1=2047$. Let $p\in\\{1,2\\}$,
and suppose that $|M_{4}^{w}(v)\cup M_{5}^{w}(v)|\geq h_{p}m_{p}-m_{p}+1$. It
suffices to show that $T_{8}^{(p)}\prec G$.

By Lemma 4.3, we may assume that $|M_{4}^{w}(v)|\leq h_{p}-1$. Then
$|M_{5}^{w}(v)-M_{4}^{w}(v)|\geq
h_{p}m_{p}-m_{p}+1-(h_{p}-1)=(h_{p}-1)(m_{p}-1)+1$. Take
$(h_{p}-1)(m_{p}-1)+1$ distinct vertices
$a_{1},\ldots,a_{(h_{p}-1)(m_{p}-1)+1}$ in $M_{5}^{w}(v)-M_{4}^{w}(v)$. Then
for $i~{}(1\leq i\leq(h_{p}-1)(m_{p}-1)+1)$, there exists a $(v,w;5)$-path
$Q_{i}=va_{i}b_{i}c_{i}w$ of $G$. If $|\\{c_{i}:1\leq
i\leq(h_{p}-1)(m_{p}-1)+1\\}|\leq m_{p}-1$, then there exists a vertex
$w^{\prime}$ of $G$ such that

$|M_{4}^{w^{\prime}}(v)|\geq|\\{a_{i}:1\leq
i\leq(h_{p}-1)(m_{p}-1)+1,~{}c_{i}=w^{\prime}\\}|\geq\left\lceil\frac{(h_{p}-1)(m_{p}-1)+1}{m_{p}-1}\right\rceil~{}(=h_{p}),$

and hence by Lemma 4.3, we have $T_{8}^{(p)}\prec G$. Thus we may assume that
$|\\{c_{i}:1\leq i\leq(h_{p}-1)(m_{p}-1)+1\\}|\geq m_{p}$. Relabeling the
paths $Q_{i}$, we may also assume that $c_{i}\neq c_{j}$ for $1\leq i<j\leq
m_{p}$. By Lemma 4.1(ii), $Q_{1},\ldots,Q_{m_{p}}$ are pairwise internally
disjoint. Furthermore, by Lemma 4.1(v), we have

$\displaystyle E\left(G\left[\bigcup_{1\leq i\leq
m_{p}}V(Q_{i})\right]\right)-\left(\bigcup_{1\leq i\leq
m_{p}}E(Q_{i})\right)=E(G[\\{b_{i}:1\leq i\leq m_{p}\\}]).$ (4.10)

Case 1: $p=1$, i.e., $m_{p}=124$.

Take $x_{1}\in N(a_{1})-\\{v,b_{1}\\}$ and $y_{1}\in
N(b_{1})-\\{a_{1},c_{1}\\}$. Since $G$ is $\\{C_{3},C_{4}\\}$-free, we have
$x_{1}\neq y_{1}$. By (4.10), $x_{1}\notin\\{w,c_{1},a_{i},b_{i},c_{i}:2\leq
i\leq 124\\}$ and $y_{1}\notin\\{v,w,a_{i},c_{i}:2\leq i\leq 124\\}$. Since
$b_{1},\ldots,b_{124}$ are distinct vertices, we may assume that
$y_{1}\notin\\{b_{i}:1\leq i\leq 123\\}$. Consequently,

$\displaystyle x_{1}\neq y_{1}\mbox{ and
}\\{x_{1},y_{1}\\}\cap\left(\bigcup_{1\leq i\leq
123}V(Q_{i})\right)=\emptyset.$ (4.11)

If $x_{1}w\in E(G)$, then $va_{1}x_{1}w$ is a $(v,w;4)$-path, and hence
$a_{1}\in M_{4}^{w}(v)$, which is a contradiction. This together with the fact
that $G$ is $\\{C_{3},C_{4}\\}$-free implies that

$\displaystyle N(x_{1})\cap\\{v,w,y_{1},b_{1},c_{1},a_{i}:2\leq i\leq
123\\}=\emptyset\mbox{ and }N(y_{1})\cap\\{v,w,a_{1},c_{1}\\}=\emptyset.$
(4.12)

By (4.12) and the fact that $b_{1}w\notin E(G)$, the set $M_{4}^{w}(u)$ is
well-defined for $u\in\\{b_{1},x_{1},y_{1}\\}$. Considering Lemma 4.3(i), we
may assume that

$\displaystyle|N(u)\cap\\{b_{i}:2\leq i\leq 123\\}|\leq|M_{4}^{w}(u)|\leq
39\mbox{ for }u\in\\{b_{1},x_{1},y_{1}\\}.$ (4.13)

By (4.10), we have

$\displaystyle N(b_{1})\cap\\{c_{i}:2\leq i\leq 123\\}=\emptyset.$ (4.14)

Furthermore, we have

$\displaystyle|N(u)\cap\\{c_{i}:2\leq i\leq 123\\}|\leq|N(u)\cap N(w)|\leq
1\mbox{ for }u\in\\{x_{1},y_{1}\\}.$ (4.15)

By (4.13)–(4.15),

$|N(\\{b_{1},x_{1},y_{1}\\})\cap\\{b_{i},c_{i}:2\leq i\leq
123\\}|\leq\sum_{u\in\\{b_{1},x_{1},y_{1}\\}}|N(u)\cap\\{b_{i},c_{i}:2\leq
i\leq 123\\}|\leq 3\cdot 39+2.$

We may assume that $E_{G}(\\{b_{1},x_{1},y_{1}\\},\\{b_{i},c_{i}:2\leq i\leq
4\\})=\emptyset$. By (4.12), we have

$\displaystyle N(x_{1})\cap\\{v,w,y_{1},b_{1},c_{1},a_{i},b_{i},c_{i}:2\leq
i\leq 4\\}=\emptyset\mbox{ and
}N(y_{1})\cap\\{v,w,a_{1},c_{1},b_{i},c_{i}:2\leq i\leq 4\\}=\emptyset.$
(4.16)

Since $G[\\{b_{2},b_{3},b_{4}\\}]$ is not complete, we may assume that
$b_{2}b_{3}\notin E(G)$, which implies that

$\displaystyle\\{b_{1},b_{2},b_{3}\\}\mbox{ is an independent set of }G.$
(4.17)

Since $|N(y_{1})\cap\\{a_{5},a_{6}\\}|\leq|N(y_{1})\cap N(v)|\leq 1$, we may
assume that

$\displaystyle y_{1}a_{5}\notin E(G).$ (4.18)

Consequently, it follows from (4.10), (4.11) and (4.16)–(4.18) that
$\\{b_{2},c_{2},w,b_{3},c_{3},c_{1},b_{1},y_{1},a_{1},x_{1},v,a_{5}\\}$
induces a copy of $T_{8}^{(1)}$ in $G$ (see the left graph in Figure 10).

$w$$v$$b_{1}$$b_{2}$$b_{3}$$b_{5}$$a_{1}$$a_{2}$$a_{3}$$a_{5}$$c_{5}$$c_{3}$$c_{2}$$c_{1}$$x_{1}$$y_{1}$$w$$v$$b_{1}$$b_{2}$$b_{3}$$b_{5}$$a_{1}$$a_{2}$$a_{3}$$a_{5}$$c_{5}$$c_{3}$$c_{2}$$c_{1}$$z_{1}$
Figure 10: Induced copies of $T_{8}^{(1)}$ and $T_{8}^{(2)}$ in Lemma 4.4

Case 2: $p=2$, i.e., $m_{p}=66$.

For $i~{}(1\leq i\leq 66)$, take $z_{i}\in N(c_{i})-\\{w,b_{i}\\}$. Since $G$
is $\\{C_{3},C_{4}\\}$-free, $z_{1},\ldots,z_{66}$ are distinct. By (4.10), we
have

$\displaystyle\\{z_{i}:1\leq i\leq 66\\}\cap\left(\bigcup_{1\leq i\leq
66}V(Q_{i})\right)=\emptyset.$ (4.19)

If $\\{z_{i}:1\leq i\leq 66\\}\subseteq N(v)$, then $|M_{4}^{w}(v)|\geq 66>32$
because $vz_{i}c_{i}w~{}(1\leq i\leq 66)$ are distinct $(v,w;4)$-paths of $G$,
which contradicts the assumption in the second paragraph of the proof. Thus,
without loss of generality, we may assume that $vz_{1}\notin E(G)$. This
together with the $\\{C_{3},C_{4}\\}$-freeness of $G$ implies that

$\displaystyle N(z_{1})\cap\\{v,w,a_{1},b_{1},c_{i}:2\leq i\leq
66\\}=\emptyset.$ (4.20)

By (4.20) and the fact that $b_{1}w\notin E(G)$, the set $M_{4}^{w}(u)$ is
well-defined for $u\in\\{b_{1},z_{1}\\}$. Considering Lemma 4.3(ii), we may
assume that

$\displaystyle|N(u)\cap\\{b_{i}:2\leq i\leq 66\\}|\leq|M_{4}^{w}(u)|\leq
31\mbox{ for }u\in\\{b_{1},z_{1}\\}.$ (4.21)

By (4.21),

$|N(\\{b_{1},z_{1}\\})\cap\\{b_{i}:2\leq i\leq 66\\}|\leq 2\cdot 31.$

We may assume that $N(\\{b_{1},z_{1}\\})\cap\\{b_{i}:2\leq i\leq
4\\}=\emptyset$. This together with (4.10) and (4.20) leads to

$\displaystyle N(b_{1})\cap\\{v,w,a_{i},b_{i},c_{i}:2\leq i\leq
4\\}=\emptyset\mbox{ and }N(z_{1})\cap\\{v,w,a_{1},b_{1},b_{i},c_{i}:2\leq
i\leq 4\\}=\emptyset.$ (4.22)

Since $G[\\{b_{2},b_{3},b_{4}\\}]\not\simeq C_{3}$, we may assume that

$\displaystyle b_{2}b_{3}\notin E(G).$ (4.23)

Since $|N(z_{1})\cap\\{a_{5},a_{6}\\}|\leq|N(z_{1})\cap N(v)|\leq 1$, we may
assume that

$\displaystyle z_{1}a_{5}\notin E(G).$ (4.24)

Consequently, it follows from (4.10), (4.19) and (4.22)–(4.24) that
$\\{b_{2},c_{2},w,b_{3},c_{3},c_{1},z_{1},b_{1},a_{1},v,a_{4}\\}$ induces a
copy of $T_{8}^{(2)}$ in $G$ (see the right graph in Figure 10). ∎

###### Lemma 4.5

Let $v$ and $w$ be non-adjacent vertices of $G$. If there are $25$ pairwise
internally disjoint $(v,w;5)$-paths of $G$, then $T_{9}\prec G$.

###### Proof.

Let $Q_{i}=va_{i}b_{i}c_{i}w~{}(1\leq i\leq 25)$ be $25$ pairwise internally
disjoint $(v,w;5)$-paths of $G$. Then by Lemma 4.1(iv), we have

$\displaystyle E\left(G\left[\bigcup_{1\leq i\leq 25}V(Q_{i})\right]\right)$
$\displaystyle-\left(\bigcup_{1\leq i\leq 25}E(Q_{i})\right)$
$\displaystyle=E(G[\\{b_{i}:1\leq i\leq 25\\}])\cup E_{G}(\\{a_{i}:1\leq i\leq
25\\},\\{c_{i}:1\leq i\leq 25\\}).$ (4.25)

Now we define a graph $H$ on $\\{1,\ldots,25\\}$ by joining $i$ and $j$ with
$i\neq j$ if and only if $a_{i}c_{j}\in E(G)$ or $a_{j}c_{i}\in E(G)$. Since
$|N(a_{i})\cap\\{c_{j}:1\leq j\leq 25\\}|\leq|N(a_{i})\cap N(w)|\leq 1$ and
$|N(c_{i})\cap\\{a_{j}:1\leq j\leq 25\\}|\leq|N(c_{i})\cap N(v)|\leq 1$ for
all $1\leq i\leq 25$, we have $\Delta(H)\leq 2$. Hence there exists an
independent set $I\subseteq\\{1,\ldots,25\\}$ of $H$ with
$|I|=\lceil\frac{25}{3}\rceil=9$. Then $a_{i}c_{j}\notin E(G)$ for all $i,j\in
I$. Since $G$ is $C_{3}$-free and $R(3,4)=9$, there exists
$I^{\prime}\subseteq I$ with $|I^{\prime}|=4$ such that $\\{b_{i}:i\in
I^{\prime}\\}$ is an independent set of $G$. We may assume that
$I^{\prime}=\\{1,2,3,4\\}$. Then it follows from (4.25) that
$E(G[\bigcup_{1\leq i\leq 4}V(Q_{i})])=\bigcup_{1\leq i\leq 4}E(Q_{i})$, and
hence $\\{b_{1},a_{1},v,b_{2},a_{2},a_{3},b_{3},c_{3},w,c_{4},b_{4}\\}$
induces a copy of $T_{9}$ in $G$ (see Figure 11). ∎

$w$$v$$a_{1}$$b_{1}$$c_{1}$$a_{2}$$b_{2}$$c_{2}$$c_{3}$$b_{3}$$a_{3}$$a_{4}$$b_{4}$$c_{4}$
Figure 11: An induced copy of $T_{9}$ in Lemma 4.5 and Lemma 4.7

###### Lemma 4.6

Let $v$ and $w$ be non-adjacent vertices of $G$. If $|M_{4}^{w}(v)|\geq 75$,
then $T_{9}\prec G$.

###### Proof.

Let $a_{1},\ldots,a_{75}$ be distinct vertices in $M_{4}^{w}(v)$. Then for
each $i~{}(1\leq i\leq 75)$, there exists a vertex $b_{i}\in V(G)$ such that
$Q_{i}=ua_{i}b_{i}v$ is a $(v,w;4)$-path. By Lemma 4.1(i)(iii),
$\\{a_{i},b_{i}\\}\cap\\{a_{j},b_{j}\\}=\emptyset$ and
$E_{G}(\\{a_{i},b_{i}\\},\\{a_{j},b_{j}\\})=\emptyset$ for $1\leq i<j\leq 75$.
For $i~{}(1\leq i\leq 13)$, take $x_{i}\in N(a_{i})-\\{v,b_{i}\\}$. Then

$|N(\\{x_{i}:1\leq i\leq 13\\})\cap\\{b_{i}:14\leq i\leq 75\\}|\leq\sum_{1\leq
i\leq 13}|N(x_{i})\cap N(w)|\leq 13.$

We may assume that

$\displaystyle N(\\{x_{i}:1\leq i\leq 13\\})\cap\\{b_{i}:14\leq i\leq
62\\}=\emptyset.$ (4.26)

For each $i~{}(14\leq i\leq 62)$, take $y_{i}\in N(b_{i})-\\{w,a_{i}\\}$. By
Lemma 4.1(i)(iii), (4.26) and the $\\{C_{3},C_{4}\\}$-freeness of $G$,

$\displaystyle x_{1},\ldots,x_{13},y_{14},\ldots,y_{62}\mbox{ are distinct};$
(4.27) $\displaystyle(\\{x_{i}:1\leq i\leq 13\\}\cup\\{y_{i}:14\leq i\leq
62\\})\cap\left(\bigcup_{1\leq i\leq 62}V(Q_{i})\right)=\emptyset;$ (4.28)
$\displaystyle N(x_{i})\cap\\{v,w,a_{j}:1\leq j\leq 62,~{}j\neq
i\\}=\emptyset\mbox{ for }1\leq i\leq 13;\mbox{ and }$ (4.29) $\displaystyle
N(y_{i})\cap\\{v,w,b_{j}:1\leq j\leq 62,~{}j\neq i\\}=\emptyset\mbox{ for
}14\leq i\leq 62.$ (4.30)

For $i~{}(14\leq i\leq 62)$, since $|N(y_{i})\cap N(v)|\leq 1$, there exists a
vertex $z_{i}\in N(y_{i})-(\\{b_{i}\\}\cup N(v))$. Then $\\{z_{i}:14\leq i\leq
62\\}\cap\\{a_{i}:1\leq i\leq 62\\}=\emptyset$. Since $N(y_{i})\cap
N(w)=\\{b_{i}\\}$, we have $z_{i}\notin N(w)$, and hence $\\{z_{i}:14\leq
i\leq 62\\}\cap\\{b_{i}:1\leq i\leq 62\\}=\emptyset$. By (4.30), we have
$z_{i}\notin\\{v,w\\}$ for $14\leq i\leq 62$. Consequently,

$\displaystyle\\{z_{i}:14\leq i\leq 62\\}\cap\left(\bigcup_{1\leq i\leq
62}V(Q_{i})\right)=\emptyset.$ (4.31)

By the choice of $z_{i}$ and the $\\{C_{3},C_{4}\\}$-freeness of $G$, we have

$\displaystyle N(z_{i})\cap\\{v,w,b_{i}\\}=\emptyset\mbox{ for }14\leq i\leq
62.$ (4.32)

Assume for the moment that $|\\{z_{i}:14\leq i\leq 62\\}|\leq 2$. Then there
exists a vertex $z$ of $G$ such that $|\\{i:14\leq i\leq
62,~{}z_{i}=z\\}|\geq\lceil\frac{49}{2}\rceil=25$. We may assume that
$z_{i}=z$ for all $i~{}(14\leq i\leq 38)$. Then the paths
$va_{i}b_{i}y_{i}z~{}(14\leq i\leq 38)$ are $25$ pairwise internally disjoint
$(v,z;5)$-paths of $G$, and hence it follows from Lemma 4.6 that $T_{9}\prec
G$. Thus we may assume that $|\\{z_{i}:14\leq i\leq 62\\}|\geq 3$. We may
assume that $z_{14},z_{15},z_{16}$ are distinct.

###### Claim 4.2

There exist $i,j\in\\{14,15,16\\}$ with $i\neq j$ such that
$\\{y_{i},z_{i}\\}\cap\\{y_{j},z_{j}\\}=\emptyset$.

###### Proof.

By (4.27), $y_{14},y_{15},y_{16}$ are distinct. Since
$G[\\{y_{14},y_{15},y_{16}\\}]\not\simeq C_{3}$, there exist $14\leq i<j\leq
16$ such that $y_{i}y_{j}\notin E(G)$. This implies that $z_{i}\neq y_{j}$ and
$z_{j}\neq y_{i}$. From $y_{i}\neq y_{j}$ and $z_{i}\neq z_{j}$, it follows
that $\\{y_{i},z_{i}\\}\cap\\{y_{j},z_{j}\\}=\emptyset$. ∎

By Claim 4.2, we may assume that

$\displaystyle\\{y_{14},z_{14}\\}\cap\\{y_{15},z_{15}\\}=\emptyset.$ (4.33)

Since $|N(u)\cap\\{a_{i}:1\leq i\leq 13\\}|\leq|N(u)\cap N(v)|\leq 1$ for all
$u\in\\{y_{14},y_{15},z_{14},z_{15}\\}$, we may assume that

$\displaystyle N(\\{y_{14},y_{15},z_{14},z_{15}\\})\cap\\{a_{i}:1\leq i\leq
9\\}=\emptyset.$ (4.34)

This together with (4.27) and (4.33) implies that

$\displaystyle x_{1},\ldots,x_{9},y_{14},y_{15},z_{14},z_{15}\mbox{ are
distinct}.$ (4.35)

###### Claim 4.3

There exists $i_{0}\in\\{14,15\\}$ and there exists
$J\subseteq\\{1,\ldots,9\\}$ with $|J|=3$ such that
$N(\\{y_{i_{0}},z_{i_{0}}\\})\cap\\{x_{j}:j\in J\\}=\emptyset$.

###### Proof.

Suppose that $|N(\\{y_{i},z_{i}\\})\cap\\{x_{j}:1\leq j\leq 9\\}|\geq 7$ for
each $i\in\\{14,15\\}$. Then $|N(\\{y_{14},z_{14}\\})\cap
N(\\{y_{15},z_{15}\\})\cap\\{x_{j}:1\leq j\leq 9\\}|\geq 5$. Hence for some
$u\in\\{y_{14},z_{14}\\}$ and some $u^{\prime}\in\\{y_{15},z_{15}\\}$,
$|N(u)\cap N(u^{\prime})|\geq|N(u)\cap N(u^{\prime})\cap\\{x_{j}:1\leq j\leq
9\\}|\geq 2$, which is a contradiction. Thus for some $i_{0}\in\\{14,15\\}$,
we have $|N(\\{y_{i_{0}},z_{i_{0}}\\})\cap\\{x_{j}:1\leq j\leq 9\\}|\leq 6$.
This implies that $|\\{j:1\leq j\leq 9,~{}x_{j}\notin
N(\\{y_{i_{0}},z_{i_{0}}\\})\\}|\geq 3$. Hence $i_{0}$ and a set
$J\subseteq\\{j:1\leq j\leq 9,~{}x_{j}\notin N(\\{y_{i_{0}},z_{i_{0}}\\})\\}$
with $|J|=3$ satisfy the desired property. ∎

Let $i_{0}$ and $J$ be as in Claim 4.3. We may assume that $i_{0}=14$ and
$J=\\{1,2,3\\}$. Then it follows from (4.30) and (4.34) that

$\displaystyle
N(y_{14})\cap\left(\\{x_{1},x_{2},x_{3}\\}\cup\left(\bigcup_{1\leq i\leq
9}V(Q_{i})\right)\right)=\emptyset\mbox{ and
}N(z_{14})\cap\\{x_{1},x_{2},x_{3}\\}=\emptyset.$ (4.36)

Since $G[\\{x_{1},x_{2},x_{3}\\}]\not\simeq C_{3}$, we may assume that

$\displaystyle x_{1}x_{2}\notin E(G).$ (4.37)

Since $|N(\\{x_{1},x_{2},z_{14}\\})\cap\\{b_{i}:4\leq i\leq
7\\}|\leq\sum_{u\in\\{x_{1},x_{2},z_{14}\\}}|N(u)\cap N(w)|\leq 3$, we may
assume that

$\displaystyle ub_{4}\notin E(G)\mbox{ for }u\in\\{x_{1},x_{2},z_{14}\\}.$
(4.38)

By (4.26), (4.29) and (4.36)–(4.38),

$\displaystyle
N(x_{i})\cap\\{v,w,a_{3-i},a_{4},b_{4},b_{14},x_{3-i},y_{14},z_{14}\\}=\emptyset\mbox{
for }i\in\\{1,2\\}.$ (4.39)

By (4.32), (4.34), (4.36) and (4.38),

$\displaystyle
N(z_{14})\cap\\{v,w,a_{1},a_{2},a_{4},b_{4},b_{14},x_{1},x_{2}\\}=\emptyset.$
(4.40)

Consequently, it follows from (4.28), (4.31), (4.35), (4.36), (4.39) and
(4.40) that

$\\{x_{1},a_{1},v,x_{2},a_{2},a_{4},b_{4},w,b_{14},y_{14},z_{14}\\}$

induces a copy of $T_{9}$ in $G$ (see Figure 12). ∎

$w$$v$$a_{1}$$a_{2}$$x_{1}$$x_{2}$$b_{1}$$b_{2}$$a_{4}$$b_{4}$$a_{14}$$b_{14}$$y_{14}$$z_{14}$
Figure 12: An induced copy of $T_{9}$ in Lemma 4.6

###### Lemma 4.7

Let $v$ and $w$ be non-adjacent vertices of $G$. If $|M_{4}^{w}(v)\cup
M_{5}^{w}(v)|\geq 667$, then $T_{9}\prec G$.

###### Proof.

Suppose that $|M_{4}^{w}(v)\cup M_{5}^{w}(v)|\geq 667$. By Lemma 4.6, we may
assume that $|M_{4}^{w}(v)|\leq 74$. Then $|M_{5}^{w}(v)-M_{4}^{w}(v)|\geq
667-74=593$. Take $593$ distinct vertices $a_{1},\ldots,a_{593}$ in
$M_{5}^{w}(v)-M_{4}^{w}(v)$. Then for each $i~{}(1\leq i\leq 593)$, there
exists a $(v,w;5)$-path $Q_{i}=va_{i}b_{i}c_{i}w$ of $G$. If $|\\{c_{i}:1\leq
i\leq 593\\}|\leq 8$, then there exists a vertex $w^{\prime}$ of $G$ such that

$|M_{4}^{w^{\prime}}(v)|\geq|\\{a_{i}:1\leq i\leq
593,~{}c_{i}=w^{\prime}\\}|\geq\left\lceil\frac{593}{8}\right\rceil=75,$

and hence by Lemma 4.6, we have $T_{9}\prec G$. Thus we may assume that
$|\\{c_{i}:1\leq i\leq 593\\}|\geq 9$. We may assume that $c_{i}\neq c_{j}$
for $1\leq i<j\leq 9$. By Lemma 4.1(ii), $Q_{1},\ldots,Q_{9}$ are pairwise
internally disjoint. Furthermore, by Lemma 4.1(v), we have

$\displaystyle E\left(G\left[\bigcup_{1\leq i\leq
9}V(Q_{i})\right]\right)-\left(\bigcup_{1\leq i\leq
9}E(Q_{i})\right)=E(G[\\{b_{i}:1\leq i\leq 9\\}]).$ (4.41)

Since $G$ is $C_{3}$-free and $R(3,4)=9$, there exists an independent set
$X\subseteq\\{b_{i}:1\leq i\leq 9\\}$ of $G$ with $|X|=4$. We may assume that
$X=\\{b_{i}:1\leq i\leq 4\\}$. Then it follows from (4.41) that
$\\{b_{1},a_{1},v,b_{2},a_{2},a_{3},b_{3},c_{3},w,c_{4},b_{4}\\}$ induces a
copy of $T_{9}$ in $G$ (see Figure 11). ∎

##  5 Proof of Theorem 1.4

Recall that we have fixed a connected $\\{C_{3},C_{4}\\}$-free graph $G$ with
$\delta(G)\geq 3$. For a vertex $u$ of $G$ and a non-negative integer $d$, let
$N_{d}(u)$ be the set of vertices $v$ of $G$ such that ${\rm
dist}_{G}(u,v)=d$, and let $N_{\leq d}(u)=\bigcup_{0\leq i\leq d}N_{i}(u)$ and
$N_{\geq d}(u)=\bigcup_{i\geq d}N_{i}(u)$. Note that $N_{0}(u)=\\{u\\}$ and
$N_{1}(u)=N(u)$. We further fix a vertex $w$ of $G$ with $d_{G}(w)=\Delta(G)$.
For a subset $U$ of $V(G)$, let $L(U)$ be the set of vertices $v\in
N_{2}(w)\cup N_{3}(w)$ such that there exists a $v$-$w$ path $Q$ of $G$ with
$V(Q)\cap U=\emptyset$ having order $4$.

###### Lemma 5.1

Let $X$ be a subset of $N_{\geq 2}(w)$. Let $Y_{1}=(X\cup N(X))\cap N_{2}(w)$,
$Y_{2}=N(Y_{1})\cap N(w)$, $Z_{1}=N(X)\cap L(X)$, $Z_{2}=(X\cup N(Z_{1}\cup
X))\cap N_{2}(w)$ and $Z_{3}=N(Z_{2})\cap N(w)$. Then the following hold.

  1. (i)

For $a\in N(w)-Y_{2}$, $E_{G}(X,N_{\leq 1}(a))=\emptyset$. In particular,
$E_{G}(X,N(w)-Y_{2})=\emptyset$.

  2. (ii)

For $a\in N(w)-Z_{3}$, $E_{G}(X,N_{\leq 2}(a)-Z_{3})=\emptyset$. In
particular, $E_{G}(X,N(w)-Z_{3})=\emptyset$.

###### Proof.

Since $X\subseteq N_{\geq 2}(w)$, a vertex $x\in X$ satisfies $N(x)\cap
N(w)\neq\emptyset$ if and only if $x\in N_{2}(w)$. This implies that $N(X)\cap
N(w)=N(X\cap N_{2}(w))\cap N(w)$. Since $X\cap N_{2}(w)\subseteq Y_{1}$,

$\displaystyle N(X)\cap N(w)=N(X\cap N_{2}(w))\cap N(w)\subseteq N(Y_{1})\cap
N(w)=Y_{2}.$ (5.1)

Since $Y_{1}=(X\cup N(X))\cap N_{2}(w)\subseteq(X\cup N(Z_{1}\cup X))\cap
N_{2}(w)=Z_{2}$, we have

$\displaystyle Y_{2}=N(Y_{1})\cap N(w)\subseteq N(Z_{2})\cap N(w)=Z_{3}.$
(5.2)

We first prove (i). Suppose that there exists $a\in N(w)-Y_{2}$ such that
$E_{G}(X,N_{\leq 1}(a))\neq\emptyset$. Then there exists a vertex $y\in
N(X)\cap N_{\leq 1}(a)$. Clearly $y\neq w$. If $y=a$, then by (5.1), $a\in
N(X)\cap N(w)\subseteq Y_{2}$; if $y\in N(a)-\\{w\\}$, then $y\in N(X)\cap
N_{2}(w)\subseteq Y_{1}$, and hence $a\in N(y)\cap N(w)\subseteq N(Y_{1})\cap
N(w)=Y_{2}$. In either case, we obtain $a\in Y_{2}$, which is a contradiction.
Therefore (i) holds.

Next we prove (ii). Suppose that there exists $a^{\prime}\in N(w)-Z_{3}$ such
that $E_{G}(X,N_{\leq 2}(a^{\prime})-Z_{3})\neq\emptyset$. Then there exists a
vertex $y^{\prime}\in N(X)\cap(N_{\leq 2}(a^{\prime})-Z_{3})$. By (5.2), we
have $a^{\prime}\in N(w)-Z_{3}\subseteq N(w)-Y_{2}$. This together with (i)
implies that

$\displaystyle E_{G}(X,N_{\leq 1}(a^{\prime})\cup(N(w)-Z_{3}))=\emptyset.$
(5.3)

Hence $y^{\prime}\in N_{2}(a^{\prime})-N(w)$. Then there exists a vertex
$a^{\prime\prime}\in N(y^{\prime})\cap N(a^{\prime})$. Note that
$a^{\prime\prime}\in N_{2}(w)$ and $y^{\prime}\in N_{2}(w)\cup N_{3}(w)$. We
clearly have $a^{\prime}\notin X$ and, since $a^{\prime},a^{\prime\prime}\in
N_{\leq 1}(a^{\prime})$, it follows from (5.3) that
$a^{\prime\prime},y^{\prime}\notin X$. Considering a $y^{\prime}$-$w$ path
$y^{\prime}a^{\prime\prime}a^{\prime}w$ of $G$, this leads to $y^{\prime}\in
N(X)\cap L(X)=Z_{1}$, and hence

$a^{\prime\prime}\in N(y^{\prime})\cap N_{2}(w)\subseteq N(Z_{1}\cup X)\cap
N_{2}(w)\subseteq Z_{2}.$

Consequently,

$a^{\prime}\in N(a^{\prime\prime})\cap N(w)\subseteq N(Z_{2})\cap N(w)=Z_{3},$

which is a contradiction. Therefore (ii) holds. ∎

###### Lemma 5.2

Let $X$ be a subset of $N_{\geq 2}(w)$. Then $N(X)\cap
N_{2}(w)\subseteq\bigcup_{x\in X}M_{4}^{w}(x)$ and $N(X)\cap
L(X)\subseteq\bigcup_{x\in X}M_{5}^{w}(x)$.

###### Proof.

Let $a\in N(X)\cap N_{2}(w)$, and take $y\in X\cap N(a)$ and $a^{\prime}\in
N(a)\cap N(w)$. Then $yaa^{\prime}w$ is a $(y,w;4)$-path of $G$, and hence
$a\in M_{4}^{w}(y)\subseteq\bigcup_{x\in X}M_{4}^{w}(x)$. Since $a$ is
arbitrary, we get $N(X)\cap N_{2}(w)\subseteq\bigcup_{x\in X}M_{4}^{w}(x)$.

Let $b\in N(X)\cap L(X)$, and take $z\in X\cap N(b)$. Since $b\in L(X)$, there
exists a $b$-$w$ path $Q=bb^{\prime}b^{\prime\prime}w$ with $V(Q)\cap
X=\emptyset$. In particular, $z\notin V(Q)$. By the definition of $L(X)$,
$b\in L(X)\subseteq N_{2}(w)\cup N_{3}(w)$. Since $bz\in E(G)$ and $z\in
N_{\geq 2}(w)$, the $\\{C_{3},C_{4}\\}$-freeness of $G$ assures us $N(z)\cap
V(Q)=\\{b\\}$. Hence $zbb^{\prime}b^{\prime\prime}w$ is a $(z,w;5)$-path of
$G$. Consequently, $b\in M_{5}^{w}(z)\subseteq\bigcup_{x\in X}M_{5}^{w}(x)$.
Since $b$ is arbitrary, we get $N(X)\cap L(X)\subseteq\bigcup_{x\in
X}M_{5}^{w}(x)$. ∎

###### Lemma 5.3

Let $X$ be a subset of $N_{\geq 2}(w)$ with $|X|\geq 2$ such that $G[X]$ is
connected. Let $Y_{1}$, $Y_{2}$, $Z_{1}$, $Z_{2}$ and $Z_{3}$ be the sets
obtained from $X$ as in Lemma 5.1. Then

  1. (i)

$|Y_{2}|\leq|Y_{1}|\leq\sum_{x\in X}|M_{4}^{w}(x)|$,

  2. (ii)

$|Z_{1}|\leq\sum_{x\in X}|M_{5}^{w}(x)|$, and

  3. (iii)

$|Z_{3}|\leq|Z_{2}|\leq\sum_{x\in Z_{1}\cup X}|M_{4}^{w}(x)|$.

###### Proof.

Since $|X|\geq 2$ and $G[X]$ is connected, we have $X\subseteq N(X)$, and
hence $Y_{1}=N(X)\cap N_{2}(w)$ and $Z_{2}=N(Z_{1}\cup X)\cap N_{2}(w)$. By
Lemma 5.2, $|Y_{1}|=|N(X)\cap N_{2}(w)|\leq|\bigcup_{x\in
X}M_{4}^{w}(x)|\leq\sum_{x\in X}|M_{4}^{w}(x)|$. Since $|N(y)\cap N(w)|=1$ for
each $y\in Y_{1}~{}(\subseteq N_{2}(w))$, we also have $|Y_{2}|=|N(Y_{1})\cap
N(w)|\leq\sum_{y\in Y_{1}}|N(y)\cap N(w)|=|Y_{1}|$, which proves (i).

By Lemma 5.2, $|Z_{1}|=|N(X)\cap L(X)|\leq|\bigcup_{x\in
X}M_{5}^{w}(x)|\leq\sum_{x\in X}|M_{5}^{w}(x)|$, which proves (ii).

Since $Z_{1}=N(X)\cap L(X)\subseteq N(X)\cap(N_{2}(w)\cup N_{3}(w))$, we have
$Z_{1}\cup X\subseteq N_{\geq 2}(w)$. Applying Lemma 5.2 to $Z_{1}\cup X$, we
get $|Z_{2}|=|N(Z_{1}\cup X)\cap N_{2}(w)|\leq|\bigcup_{x\in Z_{1}\cup
X}M_{4}^{w}(x)|\leq\sum_{x\in Z_{1}\cup X}|M_{4}^{w}(x)|$. Since $|N(z)\cap
N(w)|=1$ for each $z\in Z_{2}~{}(\subseteq N_{2}(w))$, we also have
$|Z_{3}|=|N(Z_{2})\cap N(w)|\leq\sum_{z\in Z_{2}}|N(z)\cap N(w)|=|Z_{2}|$,
which proves (iii). ∎

Now we prove Theorem 1.4. First we prove Theorem 1.4(i).

###### Proposition 5.4

If $\Delta(G)\geq 943218$, then $T_{8}^{(1)}\prec G$.

###### Proof.

Note that $d_{G}(w)\geq 943218$. We start with three claims.

###### Claim 5.1

If $G[N_{\geq 2}(w)]$ has an induced path
$a_{4}a_{3}a_{2}a^{\prime}_{3}a^{\prime}_{4}$ with $a_{2}\in N_{2}(w)$, then
$T_{8}^{(1)}\prec G$.

###### Proof.

Take $a_{1}\in N(a_{2})\cap N(w)$. By Lemmas 4.3(i) and 4.4(i), we may assume
that

$\displaystyle|M_{4}^{w}(x)|\leq 39\mbox{ and }|M_{5}^{w}(x)|\leq 4836\mbox{
for all }x\in N_{\geq 2}(w).$ (5.4)

Set $X=\\{a_{2},a_{3},a_{4},a^{\prime}_{3},a^{\prime}_{4}\\}$, and let
$Z_{1}$, $Z_{2}$ and $Z_{3}$ be the sets obtained from $X$ as in Lemma 5.1.
Then by Lemma 5.3(ii)(iii) and (5.4),

$\displaystyle|Z_{1}|$ $\displaystyle\leq\sum_{x\in X}|M_{5}^{w}(x)|\leq
5\cdot 4836=24180,\mbox{ and}$ $\displaystyle|Z_{3}|$
$\displaystyle\leq|Z_{2}|\leq\sum_{x\in Z_{1}\cup
X}|M_{4}^{w}(x)|\leq(24180+5)\cdot 39=943215.$

Since $|N(w)-Z_{3}|=d_{G}(w)-|Z_{3}|\geq 943218-943215>0$, there exists a
vertex $b_{1}\in N(w)-Z_{3}$. Take $b_{2},b^{\prime}_{2}\in N(b_{1})-\\{w\\}$
with $b_{2}\neq b^{\prime}_{2}$. Since $|N(a_{1})\cap N(b_{2})|\leq 1$, there
exists a vertex $b_{3}\in N(b_{2})-(\\{b_{1}\\}\cup N(a_{1}))$. Note that
$b_{3}\in N_{\geq 2}(w)$. Since $|N(w)\cap N(b_{3})|\leq 1$,
$|N(w)-(Z_{3}\cup\\{b_{1}\\}\cup N(b_{3}))|\geq d_{G}(w)-|Z_{3}|-2>0$. Let
$c_{1}\in N(w)-(Z_{3}\cup\\{b_{1}\\}\cup N(b_{3}))$. Since $a_{1}b_{3}\notin
E(G)$ and $G$ is $\\{C_{3},C_{4}\\}$-free,

$E(G[\\{w,a_{1},b_{1},b_{2},b_{3},b^{\prime}_{2},c_{1}\\}])=\\{wa_{1},wb_{1},b_{1}b_{2},b_{2}b_{3},b_{1}b^{\prime}_{2},wc_{1}\\}.$

Since $\\{b_{1},b_{2},b_{3},b^{\prime}_{2}\\}\subseteq N_{\leq
2}(b_{1})-Z_{3}$ and $c_{1}\in N(w)-Z_{3}$, it follows from Lemma 5.1(ii) that
$E_{G}(X,\\{b_{1},b_{2},b_{3},b^{\prime}_{2},c_{1}\\})=\emptyset$.
Consequently,
$\\{a_{4},a_{3},a_{2},a^{\prime}_{4},a^{\prime}_{3},a_{1},w,c_{1},b_{1},b^{\prime}_{2},b_{2},b_{3}\\}$
induces a copy of $T_{8}^{(1)}$ in $G$ (see Figure 13). ∎

$w$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a^{\prime}_{4}$$a^{\prime}_{3}$$b_{3}$$b_{2}$$b^{\prime}_{2}$$b_{1}$$c_{1}$$N(w)$$N_{\geq
2}(w)$ Figure 13: An induced copy of $T_{8}^{(1)}$ in Claim 5.1

###### Claim 5.2

If $N_{\geq 3}(w)\neq\emptyset$ or $G[N_{2}(w)]$ is not $2$-regular, then
$T_{8}^{(1)}\prec G$.

###### Proof.

Suppose that $N_{\geq 3}(w)\neq\emptyset$ or $G[N_{2}(w)]$ is not $2$-regular.
Since $|N(u)\cap N(w)|=1$ for $u\in N_{2}(w)$ and $N(u^{\prime})\cap
N(w)=\emptyset$ for $u^{\prime}\in N_{3}(w)$, there exists $a_{3}\in N_{\geq
2}(w)$ such that $N(a_{3})\cap N_{2}(w)\neq\emptyset$ and $|N(a_{3})\cap
N_{\geq 2}(w)|\geq 3$. Take $a_{2}\in N(a_{3})\cap N_{2}(w)$. Since
$|N(a_{2})\cap N(w)|=1$, there exists a vertex $a^{\prime}_{3}\in
N(a_{2})-(\\{a_{3}\\}\cup N(w))$. Since $|N(a^{\prime}_{3})\cap N(w)|\leq 1$,
there exists a vertex $a^{\prime}_{4}\in N(a^{\prime}_{3})-(\\{a_{2}\\}\cup
N(w))$. Since $G$ is $\\{C_{3},C_{4}\\}$-free, $a^{\prime}_{4}\neq a_{3}$ and
$a_{3}a_{2}a^{\prime}_{3}a^{\prime}_{4}$ is an induced path of $G$. Since
$|(N(a_{3})\cap N_{\geq 2}(w))-\\{a_{2}\\}|\geq 2$ and $|N(a_{3})\cap
N(a_{4})|\leq 1$, we can choose $a_{4}\in(N(a_{3})\cap N_{\geq
2}(w))-\\{a_{2}\\}$ so that $a_{4}a^{\prime}_{4}\notin E(G)$. Then $a_{4}\neq
a^{\prime}_{4}$ and the path $a_{4}a_{3}a_{2}a^{\prime}_{3}a^{\prime}_{4}$
satisfies the assumption of Claim 5.1, and hence $T_{8}^{(1)}\prec G$. ∎

###### Claim 5.3

If there exists a component $C$ of $G[N_{2}(w)]$ with $C\not\simeq C_{5}$,
then $T_{8}^{(1)}\prec G$.

###### Proof.

Suppose that there exists a component $C$ of $G[N_{2}(w)]$ with $C\not\simeq
C_{5}$. By Claim 5.2, we may assume that $C$ is a cycle. Since $G$ is
$\\{C_{3},C_{4}\\}$-free, $C$ is a cycle of order at least $6$. Then $C$
contains an induced path of order $5$, and hence $T_{8}^{(1)}\prec G$ by Claim
5.1. ∎

By Claims 5.2 and 5.3, we may assume that $N_{\geq 3}(w)=\emptyset$ and every
component of $G[N_{2}(w)]$ is a cycle of order $5$. Take $a_{1}\in N(w)$ and
$a_{2},a^{\prime}_{2}\in N(a_{1})-\\{w\\}$ with $a_{2}\neq a^{\prime}_{2}$.
Note that $a_{2},a^{\prime}_{2}\in N_{2}(w)$. Let $C$ and $C^{\prime}$ be the
components of $G[N_{2}(w)]$ containing $a_{2}$ and $a^{\prime}_{2}$,
respectively. Since $G$ is $\\{C_{3},C_{4}\\}$-free, we see that $C\neq
C^{\prime}$, $N(a_{1})\cap V(C)=\\{a_{2}\\}$ and $N(a_{1})\cap
V(C^{\prime})=\\{a^{\prime}_{2}\\}$. Since $C$ is a cycle of order $5$, $C$
contains an induced path $a_{4}a_{3}a_{2}a^{\prime}_{3}$.

Since $|N(V(C)\cup V(C^{\prime}))\cap N(w)|\leq\sum_{x\in V(C)\cup
V(C^{\prime})}|N(x)\cap N(w)|=10$, $|N(w)-N(V(C)\cup V(C^{\prime}))|\geq
943218-10>0$. Take $b_{1}\in N(w)-N(V(C)\cup V(C^{\prime}))$ and
$b_{2},b^{\prime}_{2}\in N(b_{1})-\\{w\\}$ with $b_{2}\neq b^{\prime}_{2}$.
Note that $b_{2},b^{\prime}_{2}\in N_{2}(w)$. Let $D$ and $D^{\prime}$ be the
components of $G[N_{2}(w)]$ containing $b_{2}$ and $b^{\prime}_{2}$,
respectively. Then $C,C^{\prime},D,D^{\prime}$ are pairwise distinct and there
is no edge between any two of $C,C^{\prime},D,D^{\prime}$. Since $G$ is
$C_{4}$-free, $a_{1}b_{2},a_{1}b^{\prime}_{2}\notin E(G)$. Furthermore, since
$|N(b_{2})\cap N(a_{1})|\leq 1$ and $|N(b^{\prime}_{2})\cap N(a_{1})|\leq 1$,
there exist vertices $b_{3}\in N_{D}(b_{2})-N(a_{1})$ and $b^{\prime}_{3}\in
N_{D^{\prime}}(b^{\prime}_{2})-N(a_{1})$. Then
$\\{b_{3},b_{2},b_{1},b^{\prime}_{3},b^{\prime}_{2},w,a_{1},a^{\prime}_{2},a_{2},a^{\prime}_{3},a_{3},a_{4}\\}$
induces a copy of $T_{8}^{(1)}$ in $G$ (see Figure 14). ∎

$w$$N(w)$$N_{2}(w)$$a_{1}$$b_{1}$$a_{2}$$a_{3}$$a_{4}$$a^{\prime}_{3}$$a^{\prime}_{2}$$b_{2}$$b^{\prime}_{2}$$b^{\prime}_{3}$$b_{3}$
Figure 14: An induced copy of $T_{8}^{(1)}$ in Proposition 5.4

Next we prove Theorem 1.4(ii).

###### Proposition 5.5

If $\Delta(G)\geq 190375$, then $T_{8}^{(2)}\prec G$.

###### Proof.

Note that $d_{G}(w)\geq 190375$. By Lemmas 4.3(ii) and 4.4(ii), we may assume
that

$\displaystyle|M_{4}^{w}(x)|\leq 31\mbox{ and }|M_{5}^{w}(x)|\leq 2046\mbox{
for all }x\in N_{\geq 2}(w).$ (5.5)

Take a vertex $a_{1}\in N(w)$ which attains the minimum of
$|N(x)-\\{w\\}|~{}(=d_{G}(x)-1)$ as $x$ ranges over $N(w)$, and take $a_{2}\in
N(a_{1})-\\{w\\}$ and $a_{3}\in N(a_{2})-\\{a_{1}\\}$. Note that $a_{2}\in
N_{2}(w)$. Since $N(a_{2})\cap N(w)=\\{a_{1}\\}$, we have $a_{3}\in N_{\geq
2}(w)$. Since $|N(a_{3})\cap N(w)|\leq 1$, there exists a vertex $a_{4}\in
N(a_{3})-(\\{a_{2}\\}\cup N(w))$. Since $G$ is $\\{C_{3},C_{4}\\}$-free,
$a_{1}a_{2}a_{3}a_{4}$ is an induced path of $G[N_{\geq 2}(w)]$.

Set $X=\\{a_{2},a_{3},a_{4}\\}$, and let $Z_{1}$, $Z_{2}$ and $Z_{3}$ be the
sets obtained from $X$ as in Lemma 5.1. Then by Lemma 5.3(ii)(iii) and (5.5),

$\displaystyle|Z_{1}|$ $\displaystyle\leq\sum_{x\in X}|M_{5}^{w}(x)|\leq
3\cdot 2046=6138,\mbox{ and}$ $\displaystyle|Z_{3}|$
$\displaystyle\leq|Z_{2}|\leq\sum_{x\in Z_{1}\cup
X}|M_{4}^{w}(x)|\leq(6138+3)\cdot 31=190371.$

Since $|N(w)-Z_{3}|=d_{G}(w)-|Z_{3}|\geq 190375-190371>0$, there exists a
vertex $b_{1}\in N(w)-Z_{3}$.

Since $G$ is $\\{C_{3},C_{4}\\}$-free, $N(x)\cap N(x^{\prime})\cap
N_{2}(w)=\emptyset$ for any $x,x^{\prime}\in N(b_{1})-\\{w\\}$ with $x\neq
x^{\prime}$, and hence

$\displaystyle\sum_{x\in N(b_{1})-\\{w\\}}|N(x)\cap N(a_{1})\cap
N_{2}(w)|=|N(N(b_{1})-\\{w\\})\cap N(a_{1})\cap N_{2}(w)|.$ (5.6)

Since $N(b_{1})-\\{w\\}\subseteq N_{\leq 2}(b_{1})-Z_{3}$, it follows from
Lemma 5.1(ii) that $N(X)\cap(N(b_{1})-\\{w\\})=\emptyset$. In particular,
$N(a_{2})\cap(N(b_{1})-\\{w\\})=\emptyset$, that is,

$\displaystyle N(N(b_{1})-\\{w\\})\subseteq V(G)-\\{a_{2}\\}.$ (5.7)

By (5.6), (5.7) and the minimality of $|N(a_{1})-\\{w\\}|$, we have

$\displaystyle\sum_{x\in N(b_{1})-\\{w\\}}|N(x)\cap N(a_{1})\cap N_{2}(w)|$
$\displaystyle=|N(N(b_{1})-\\{w\\})\cap N(a_{1})\cap N_{2}(w)|$
$\displaystyle\leq|(N(a_{1})\cap N_{2}(w))-\\{a_{2}\\}|$
$\displaystyle=|N(a_{1})-\\{w\\}|-1$ $\displaystyle\leq|N(b_{1})-\\{w\\}|-1.$

This inequality assures us the existence of $b_{2}\in N(b_{1})-\\{w\\}$ such
that $N(b_{2})\cap N(a_{1})\cap N_{2}(w)=\emptyset$. Take $b^{\prime}_{2}\in
N(b_{1})-\\{w,b_{2}\\}$. Note that $b^{\prime}_{2}\in N_{2}(w)$. Since
$|N(b^{\prime}_{2})\cap N(a_{1})|\leq 1$, there exists a vertex
$b^{\prime}_{3}\in N(b^{\prime}_{2})-(\\{b_{1}\\}\cup N(a_{1}))$. Since
$|N(b_{2})\cap N(b^{\prime}_{3})|\leq 1$, there exists a vertex $b_{3}\in
N(b_{2})-(\\{b_{1}\\}\cup N(b^{\prime}_{3}))$. Note that $b_{3}\in
N_{2}(w)\cup N_{3}(w)$. Since $N(b_{2})\cap N(a_{1})\cap N_{2}(w)=\emptyset$
and $a_{1}\in N(w)$, it follows that $b_{3}a_{1}\notin E(G)$. Consequently,
$N(a_{1})\cap\\{b_{1},b_{2},b_{3},b^{\prime}_{2},b^{\prime}_{3}\\}=\emptyset$.
Since $|N(b_{3})\cap N(w)|\leq 1$ and $|N(b^{\prime}_{3})\cap N(w)|\leq 1$, we
have $|N(w)-(Z_{3}\cup\\{b_{1}\\}\cup N(\\{b_{3},b^{\prime}_{3}\\}))|\geq
190375-(190371+1+2)>0$. Take $c_{1}\in N(w)-(Z_{3}\cup\\{b_{1}\\}\cup
N(\\{b_{3},b^{\prime}_{3}\\}))$. Then

$E(G[\\{w,a_{1},b_{1},b_{2},b_{3},b^{\prime}_{2},b^{\prime}_{3},c_{1}\\}])=\\{wa_{1},wb_{1},b_{1}b_{2},b_{2}b_{3},b_{1}b^{\prime}_{2},b^{\prime}_{2}b^{\prime}_{3},wc_{1}\\}.$

Recall that $a_{1}a_{2}a_{3}a_{4}$ is an induced path of $G$.

Since $\\{b_{1},b_{2},b_{3},b^{\prime}_{2},b^{\prime}_{3}\\}\subseteq N_{\leq
2}(b_{1})-Z_{3}$ and $c_{1}\in N(w)-Z_{3}$, it follows from Lemma 5.1(ii) that
$E_{G}(X,\\{b_{1},b_{2},b_{3},b^{\prime}_{2},b^{\prime}_{3},c_{1}\\})=\emptyset$.
Consequently,
$\\{b_{3},b_{2},b_{1},b^{\prime}_{3},b^{\prime}_{2},w,c_{1},a_{1},a_{2},a_{3},a_{4}\\}$
induces a copy of $T_{8}^{(2)}$ in $G$ (see Figure 15). ∎

$w$$a_{1}$$b_{3}$$b_{2}$$b^{\prime}_{2}$$b_{1}$$c_{1}$$N(w)$$N_{\geq
2}(w)$$b^{\prime}_{3}$$a_{2}$$a_{3}$$a_{4}$ Figure 15: An induced copy of
$T_{8}^{(2)}$ in Proposition 5.5

Finally we prove Theorem 1.4(iii).

###### Proposition 5.6

If $\Delta(G)\geq 197433$, then $T_{9}\prec G$.

###### Proof.

Note that $d_{G}(w)\geq 197433$. By Lemmas 4.6 and 4.7, we may assume that

$\displaystyle|M_{4}^{w}(x)|\leq 74\mbox{ and }|M_{5}^{w}(x)|\leq 666\mbox{
for all }x\in N_{\geq 2}(w).$ (5.8)

Set

$k_{0}=\max\\{k:\mbox{there is an induced path }a_{1}a_{2}\cdots a_{k}\mbox{
with }a_{1}\in N(w)\mbox{ and }\\{a_{2},\ldots,a_{k}\\}\subseteq N_{\geq
2}(w)\\}.$

Case 1: $k_{0}\geq 6$.

Let $a_{1}a_{2}\cdots a_{6}$ be an induced path with $a_{1}\in N(w)$ and
$\\{a_{2},\ldots,a_{6}\\}\subseteq N_{\geq 2}(w)$. Set
$X=\\{a_{2},\ldots,a_{6}\\}$, and let $Y_{1}$ and $Y_{2}$ be the sets obtained
from $X$ as in Lemma 5.1. Then by Lemma 5.3(i) and (5.8),

$|Y_{2}|\leq|Y_{1}|\leq\sum_{x\in X}|M_{4}^{w}(x)|\leq 5\cdot 74=370.$

Since $|N(w)-Y_{2}|=d_{G}(w)-|Y_{2}|\geq 197433-370>1$, there exist vertices
$b_{1},c_{1}\in N(w)-Y_{2}$ with $b_{1}\neq c_{1}$. Take $b_{2}\in
N(b_{1})-\\{w\\}$. Since $|N(c_{1})\cap N(b_{2})|\leq 1$, there exists a
vertex $c_{2}\in N(c_{1})-(\\{w\\}\cup N(b_{2}))$. Then $b_{2},c_{2}\in
N_{2}(w)$, $b_{2}\neq c_{2}$ and
$b_{2}a_{1},b_{2}c_{1},c_{2}a_{1},c_{2}b_{1}\notin E(G)$, and hence

$E(G[\\{w,a_{1},b_{1},b_{2},c_{1},c_{2}\\}])=\\{wa_{1},wb_{1},b_{1}b_{2},wc_{1},c_{1}c_{2}\\}.$

Since $\\{b_{1},b_{2}\\}\subseteq N_{\leq 1}(b_{1})$ and
$\\{c_{1},c_{2}\\}\subseteq N_{\leq 1}(c_{1})$, it follows from Lemma 5.1(i)
that $E_{G}(X,\\{w,b_{1},b_{2},c_{1},c_{2}\\})=\emptyset$. Consequently,
$\\{b_{2},b_{1},w,c_{2},c_{1},a_{1},\ldots,a_{6}\\}$ induces a copy of $T_{9}$
in $G$ (see Figure 16).

$w$$a_{1}$$b_{2}$$b_{1}$$c_{1}$$N(w)$$N_{\geq 2}(w)$$a_{2}$$a_{6}$$c_{2}$
Figure 16: An induced copy of $T_{9}$ in Case 1 of Proposition 5.6

Case 2: $k_{0}=5$.

Let $a_{1}a_{2}\cdots a_{5}$ be an induced path with $a_{1}\in N(w)$ and
$\\{a_{2},\ldots,a_{5}\\}\subseteq N_{\geq 2}(w)$. Set
$X=\\{a_{2},\ldots,a_{5}\\}$, and let $Z_{1}$, $Z_{2}$ and $Z_{3}$ be the sets
obtained from $X$ as in Lemma 5.1. Then by Lemma 5.3(ii)(iii) and (5.8),

$\displaystyle|Z_{1}|$ $\displaystyle\leq\sum_{x\in X}|M_{5}^{w}(x)|\leq
4\cdot 666=2664,\mbox{ and}$ $\displaystyle|Z_{3}|$
$\displaystyle\leq|Z_{2}|\leq\sum_{x\in Z_{1}\cup
X}|M_{4}^{w}(x)|\leq(2664+4)\cdot 74=197432.$

Since $|N(w)-Z_{3}|=d_{G}(w)-|Z_{3}|\geq 197433-197432>0$, there exists a
vertex $b_{1}\in N(w)-Z_{3}$. Take $b_{2},b^{\prime}_{2}\in N(b_{1})-\\{w\\}$
with $b_{2}\neq b^{\prime}_{2}$. Then $b_{2},b^{\prime}_{2}\in N_{2}(w)$.

###### Claim 5.4

There exist $b_{3}\in N(b_{2})-\\{b_{1}\\}$ and $b^{\prime}_{3}\in
N(b^{\prime}_{2})-\\{b_{1}\\}$ such that $b_{3},b^{\prime}_{3}\in N_{\geq
2}(w)$, $b_{3}b^{\prime}_{3}\notin E(G)$ and
$N(a_{1})\cap\\{b_{3},b^{\prime}_{3}\\}=\emptyset$.

###### Proof.

We first consider the case where $b_{2}$ or $b^{\prime}_{2}$, say
$b^{\prime}_{2}$, satisfies $N(a_{1})\cap N(b^{\prime}_{2})=\emptyset$. Since
$|N(b_{2})\cap N(a_{1})|\leq 1$, there exists a vertex $b_{3}\in
N(b_{2})-(\\{b_{1}\\}\cap N(a_{1}))$. Since $|N(b^{\prime}_{2})\cap
N(b_{3})|\leq 1$, there exists a vertex $b^{\prime}_{3}\in
N(b^{\prime}_{2})-(\\{b_{1}\\}\cap N(b_{3}))$. Then $b_{3},b^{\prime}_{3}\in
N_{\geq 2}(w)$ and $b_{3}b^{\prime}_{3}\notin E(G)$. By the assumption that
$N(a_{1})\cap N(b^{\prime}_{2})=\emptyset$, we have $b^{\prime}_{3}a_{1}\notin
E(G)$. Consequently, $b_{3}$ and $b^{\prime}_{3}$ satisfy the desired
properties. Thus we may assume that $N(a_{1})\cap N(b)\neq\emptyset$ for each
$b\in\\{b_{2},b^{\prime}_{2}\\}$. Write $N(a_{1})\cap N(b_{2})=\\{u_{2}\\}$
and $N(a_{1})\cap N(b^{\prime}_{2})=\\{u^{\prime}_{2}\\}$. Note that
$u_{2},u^{\prime}_{2}\in N_{2}(w)$. Since $N(b_{2})\cap
N(b^{\prime}_{2})=\\{b_{1}\\}$, $u_{2}b^{\prime}_{2}\notin E(G)$. Take
$b_{3}\in N(b_{2})-\\{b_{1},u_{2}\\}$ and $b^{\prime}_{3}\in
N(b^{\prime}_{2})-\\{b_{1},u^{\prime}_{2}\\}$. Then $b_{3}\neq b^{\prime}_{3}$
and $b_{3},b^{\prime}_{3}\in N_{\geq 2}(w)$. Since $N(a_{1})\cap
N(b_{2})=\\{u_{2}\\}$ and $N(a_{1})\cap
N(b^{\prime}_{2})=\\{u^{\prime}_{2}\\}$, we have
$N(a_{1})\cap\\{b_{3},b^{\prime}_{3}\\}=\emptyset$. If $b_{3}b^{\prime}_{3}\in
E(G)$, then $a_{1}u_{2}b_{2}b_{3}b^{\prime}_{3}b^{\prime}_{2}$ is an induced
path, which contradicts the assumption of Case 2 (see Figure 17). Thus
$b_{3}b^{\prime}_{3}\notin E(G)$. Hence $b_{3}$ and $b^{\prime}_{3}$ satisfy
the desired properties. ∎

$w$$a_{1}$$b_{2}$$b_{1}$$N(w)$$N_{\geq
2}(w)$$a_{2}$$a_{5}$$u_{2}$$u^{\prime}_{2}$$b_{3}$$b^{\prime}_{3}$$b^{\prime}_{2}$
Figure 17: An induced path of order $6$ in Claim 5.4

Let $b_{3}$ and $b^{\prime}_{3}$ be as in Claim 5.4. Since $N(b_{2})\cap
N(b^{\prime}_{2})=\\{b_{1}\\}$, $b_{3}\neq b^{\prime}_{3}$. Hence

$E(G[\\{w,a_{1},b_{1},b_{2},b_{3},b^{\prime}_{2},b^{\prime}_{3}\\}])=\\{wa_{1},wb_{1},b_{1}b_{2},b_{2}b_{3},b_{1}b^{\prime}_{2},b^{\prime}_{2}b^{\prime}_{3}\\}.$

Since $\\{b_{1},b_{2},b_{3},b^{\prime}_{2},b^{\prime}_{3}\\}\subseteq N_{\leq
2}(b_{1})-Z_{3}$, it follows from Lemma 5.1(ii) that
$E_{G}(X,\\{b_{1},b_{2},b_{3},b^{\prime}_{2},b^{\prime}_{3}\\})=\emptyset$.
Consequently,
$\\{b_{3},b_{2},b_{1},b^{\prime}_{3},b^{\prime}_{2},w,a_{1},\ldots,a_{5}\\}$
induces a copy of $T_{9}$ in $G$ (see Figure 18).

$w$$a_{1}$$b_{1}$$N(w)$$N_{\geq
2}(w)$$a_{2}$$a_{5}$$b^{\prime}_{2}$$b_{2}$$b_{3}$$b^{\prime}_{3}$ Figure 18:
An induced copy of $T_{9}$ in Case 2 of Proposition 5.6

Case 3: $k_{0}\leq 4$.

###### Claim 5.5

We have $N_{\geq 3}(w)=\emptyset$, and $G[N_{2}(w)]$ is $2$-regular.

###### Proof.

Suppose that $N_{\geq 3}(w)\neq\emptyset$ or $G[N_{2}(w)]$ is not $2$-regular.
Since $|N(u)\cap N(w)|=1$ for $u\in N_{2}(w)$ and $N(u^{\prime})\cap
N(w)=\emptyset$ for $u^{\prime}\in N_{3}(w)$, there exists $a_{3}\in N_{\geq
2}(w)$ such that $N(a_{3})\cap N_{2}(w)\neq\emptyset$ and $|N(a_{3})\cap
N_{\geq 2}(w)|\geq 3$. Take $a_{2}\in N(a_{3})\cap N_{2}(w)$, and write
$N(a_{2})\cap N(w)=\\{a_{1}\\}$. Take $a_{4},a^{\prime}_{4}\in(N(a_{3})\cap
N_{\geq 2}(w))-\\{a_{2}\\}$ with $a_{4}\neq a^{\prime}_{4}$.

Suppose that one of $a_{4}$ and $a^{\prime}_{4}$ belongs to $N_{\geq 3}(w)$,
say $a_{4}\in N_{\geq 3}(w)$. Since $|N(a_{4})\cap N(a_{1})|\leq 1$, there
exists a vertex $a_{5}\in N(a_{4})-(\\{a_{3}\\}\cup N(a_{1}))$. Then $a_{5}\in
N_{\geq 2}(w)$. Since $G$ is $\\{C_{3},C_{4}\\}$-free,
$a_{1}a_{2}a_{3}a_{4}a_{5}$ is an induced path of $G$, which contradicts the
assumption of Case 3. Thus $a_{4},a^{\prime}_{4}\in N_{2}(w)$. Write
$N(a_{4})\cap N(w)=\\{b_{1}\\}$ and $N(a^{\prime}_{4})\cap
N(w)=\\{b^{\prime}_{1}\\}$. Since $N(a_{3})\cap N(a_{1})=\\{a_{2}\\}$ and
$N(a_{4})\cap N(a^{\prime}_{4})=\\{a_{3}\\}$, three vertices
$a_{1},b_{1},b^{\prime}_{1}$ are distinct. Take $a^{\prime}_{3}\in
N(a_{2})-\\{a_{1},a_{3}\\}$. Note that $a^{\prime}_{3}\in N_{\geq 2}(w)$.
Since
$|N(a^{\prime}_{3})\cap\\{b_{1},b^{\prime}_{1}\\}|\leq|N(a^{\prime}_{3})\cap
N(w)|\leq 1$, we may assume that $a^{\prime}_{3}b_{1}\notin E(G)$. Then
$b_{1}a_{4}a_{3}a_{2}a^{\prime}_{3}$ is an induced path of $G$, which
contradicts the assumption of Case 3. ∎

###### Claim 5.6

Let $C$ be a component of $G[N_{2}(w)]$. Then $C$ is a cycle with
$|V(C)|\equiv 0~{}({\rm mod~{}}3)$ and $|N(V(C))\cap N(w)|=3$. Further, if we
write $C=b_{1}b_{2}\cdots b_{3k}b_{1}~{}(|V(C)|=3k)$, then $N(b_{i})\cap
N(w)=N(b_{j})\cap N(w)$ for any $i$ and $j$ with $i\equiv j~{}({\rm
mod~{}}3)$.

###### Proof.

By Claim 5.5, $C$ is a cycle. Let $l=|V(C)|$, and write $C=b_{1}b_{2}\cdots
b_{l}b_{1}$ (indices are to be read modulo $l$). Let $1\leq i\leq l$, and
write $N(b_{i})\cap N(w)=\\{a\\}$. Since $G$ is $\\{C_{3},C_{4}\\}$-free,
$l\geq 5$, and hence $b_{i}b_{i+1}b_{i+2}b_{i+3}$ is an induced path of $G$.
On the other hand, $ab_{i}b_{i+1}b_{i+2}b_{i+3}$ is not an induced path by the
assumption of Case 3. This forces $ab_{i+3}\in E(G)$, i.e., $N(b_{i+3})\cap
N(w)=\\{a\\}$. Since $i$ is arbitrary, we obtain the desired conclusion. ∎

By Claim 5.6, $|N(V(C))\cap N(w)|=3$ for every component $C$ of $G[N_{2}(w)]$.
Since $d_{G}(w)>3$, there are two components $D$ and $D^{\prime}$ of
$G[N_{2}(w)]$ such that $N(V(D))\cap N(w)\neq N(V(D^{\prime}))\cap N(w)$, and
we can take $a\in(N(V(D))-N(V(D^{\prime})))\cap N(w)$ and
$a^{\prime}\in(N(V(D^{\prime}))-N(V(D)))\cap N(w)$. Take $b_{1}\in N(a)\cap
V(D)$ and $b^{\prime}_{1}\in N(a^{\prime})\cap V(D^{\prime})$, and write
$D=b_{1}b_{2}\cdots b_{3k}b_{1}$ and
$D^{\prime}=b^{\prime}_{1}b^{\prime}_{2}\cdots
b^{\prime}_{3k^{\prime}}b^{\prime}_{1}$. In view of Claim 5.6,
$\\{b_{3},b_{2},b_{1},b_{3k-1},b_{3k},a,w,a^{\prime},b^{\prime}_{1},b^{\prime}_{2},b^{\prime}_{3}\\}$
induces a copy of $T_{9}$ in $G$ (see Figure 19). ∎

$w$$N(w)$$N_{2}(w)$$a$$b_{3k-1}$$b_{3k}$$b_{1}$$b_{2}$$b_{3}$$b^{\prime}_{3k^{\prime}-1}$$b^{\prime}_{3k^{\prime}}$$b^{\prime}_{1}$$b^{\prime}_{2}$$b^{\prime}_{3}$$a^{\prime}$
Figure 19: An induced copy of $T_{9}$ in Case 3 of Proposition 5.6

## References

  * [1] A. Bjőrklund, T. Husfeldt and M. Koivisto, Set partitioning via inclusion-exclusion, SIAM J. Comput. 39 (2009) 546–563.
  * [2] M. Chudnovsky and J. Stacho, $3$-colorable subclasses of $P_{8}$-free graphs, SIAM J. Discrete Math. 32 (2018) 1111–1138.
  * [3] Y. Egawa, J. Fujisawa, M. Furuya, M.D. Plummer and A. Saito, Forbidden triples generating a finite set of $3$-connected graphs, Electron. J. Combin. 22 (2015) #P3.13.
  * [4] Y. Egawa and M. Furuya, Forbidden triples containing a complete graph and a complete bipartite graph of small order, Graphs Combin. 30 (2014) 1149–1162.
  * [5] Y. Egawa and M. Furuya, Forbidden triples generating a finite set of graphs with minimum degree three, Discrete Appl. Math. 320 (2022) 282–295.
  * [6] Y. Egawa and Z. Zhao, Forbidden triples involving the complete bipartite graph with partite sets having cardinalities two and three, Ars Combin., to appear.
  * [7] R. Diestel, “Graph Theory” (5th edition), Graduate Texts in Mathematics 173, Springer, Berlin (2017).
  * [8] J. Fujisawa, M.D. Plummer and A. Saito, Forbidden subgraphs generating a finite set, Discrete Math. 313 (2013) 1835–1842.
  * [9] A. Gyárfás, On Ramsey covering-numbers, “Infinite and Finite Sets”, Colloq. Math. Soc. Janos Bolyai, 10, North-Holland (1975) pp. 801–816
  * [10] M. Kochol, Snarks without small cycles, J. Combin. Theory Ser. B 67 (1996) 34–47.
  * [11] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2017), Dynamic Survey 1, Revision #15.
  * [12] A. Scott and P. Seymour, A survey on $\chi$-boundedness, preprint, arXiv:1812.07500.
  * [13] D.P. Sumner, Subtrees of a graph and chromatic number, “The Theory and Application of Graphs”, Wiley, New York (1981) pp. 557–576.