# Generalized Turán number for linear forests

Xiutao ZHU and Yaojun CHEN111Corresponding author<EMAIL_ADDRESS>
Department of Mathematics, Nanjing University, Nanjing 210093, P.R. CHINA

###### Abstract

The generalized Turán number $ex(n,K_{s},H)$ is defined to be the maximum
number of copies of a complete graph $K_{s}$ in any $H$-free graph on $n$
vertices. Let $F$ be a linear forest consisting of $k$ paths of orders
$\ell_{1},\ell_{2},...,\ell_{k}$. In this paper, by characterizing the
structure of the $F$-free graph with large minimum degree, we determine the
value of $ex(n,K_{s},F)$ for $n=\Omega\left(|F|^{s}\right)$ and $k\geq 2$
except some $\ell_{i}=3$, and the corresponding extremal graphs. The special
case when $s=2$ of our result improves some results of Bushaw and Kettle
(2011) and Lidický et al. (2013) on the classical Turán number for linear
forests.

Key words: Generalized Turán number; Minimum degree; Linear forests

##  1 Introduction

Let $G=(V(G),E(G))$ be a graph and $|G|=|V(G)|$ is the order of $G$. If
$S\subseteq V(G)$, we use $G-S$ to denote the subgraph obtained from $G$ by
deleting all vertices in $S$ and $G[S]$ the subgraph induced by $S$. Let
$N_{S}(v)$ be the set of the neighbors of $v$ in $S$ and
$d_{S}(v)=\left|N_{S}(v)\right|$, abbreviated as $N(v)$ and $d(v)$ for
$S=V(G)$. We use $\delta(G)$, $\alpha(G)$, $\kappa(G)$ to denote the minimum
degree, independence number, and connectivity of $G$, respectively. Let $G\cup
H$ denote the disjoint union of $G$ and $H$, and $kG$ denotes $k$ disjoint
copies of $G$. We use $G+H$ to denote the graph obtained from $G\cup H$ by
adding all edges between $V(G)$ and $V(H)$. A path, clique and empty graph on
$m$ vertices are denoted by $P_{m}$, $K_{m}$ and $E_{m}$, respectively. If $u$
and $v$ are two vertices of a path $P$, we use $uPv$ to denote the segment of
$P$ from $u$ to $v$. We denote by $\overrightarrow{P}$ the path $P$ with a
given direction and $\overleftarrow{P}$ the path with the inverse direction.
We use $p(G)$ to denote the order of a longest path in $G$ and $P$ is
hamiltonian if $|P|=|G|$. A path $P$ is called a strong dominating path if
$N(v)\subseteq V(P)$ for any $v\in V(G)\backslash V(P)$.

A linear forest is the union of vertex disjoint paths, denoted by
$F=P_{\ell_{1}}\cup\cdots\cup P_{\ell_{k}}$, where
$\ell_{1}\geq\cdots\geq\ell_{k}$. Let
$\mathcal{O}=\\{\ell_{i}~{}|~{}\ell_{i}~{}is~{}odd,~{}1\leq i\leq k\\}$ and
$\chi_{\mathcal{O}}(\ell_{i})$ denote the indicative function. Define

$\delta_{F}=\sum_{i=1}^{k}\left\lfloor\ell_{i}/2\right\rfloor-1$

and $G_{F}(n)=K_{\delta_{F}}+E_{n-\delta_{F}}$ or
$K_{\delta_{F}}+(E_{n-\delta_{F}-2}\cup K_{2})$, according to $F$ contains an
even component or not, as shown in Figure 1($a$) and ($b$), respectively.

($a$)($b$)Figure 1. $G_{F}(n)$ (oval denotes a clique $K_{\delta_{F}}$)

The Turán number of $H$, denoted by $ex(n,H)$, is the maximum number of edges
in an $H$-free graph on $n$ vertices. Turán theory dates back to the early
1940’s when Turán [25] determined the value of $ex(n,K_{r})$ and extremal
graph. For a given graph $H$ with chromatic number $\chi\geq 3$, an asymptotic
solution to $ex(n,H)$ is given by the celebrated Erdős-Stone-Simonovits
theorem [12, 13] as below.

$ex(n,H)=\left(\frac{\chi-2}{\chi-1}+o(1)\right){n\choose 2}.$

In viewing this result, one can see that the asymptotic behavior of $ex(n,H)$
is still unknown for $H$ being a bipartite graph. The following is a classical
result on $ex(n,H)$ when $H$ is bipartite due to Erdős and Gallai.

###### Theorem 1

(Erdős and Gallai [10]) $ex(n,P_{\ell})\leq\frac{(\ell-2)n}{2}$, equality
holds if and only if $(\ell-1)|n$.

In the same paper, they also considered the graph $H=kK_{2}$ and determined
$ex(n,kK_{2})$ and the extremal graphs. Note that both a path $P_{\ell}$ and
$k$ independent edges $kK_{2}$ are special linear forests. In 2011, Bushaw and
Kettle [3] generalized the above results by determining the Turán number and
extremal graph for the linear forest consisting of the paths of the same
lengths.

###### Theorem 2

(Bushaw and Kettle [3]) Let $F=kP_{\ell}$ be a linear forest so that $\ell\neq
3$ and $k\geq 2$. If $n=\Omega\left(|F|^{\frac{3}{2}}2^{\ell}\right)$, then

$ex(n,F)=\binom{\delta_{F}}{2}+(n-\delta_{F})\delta_{F}+\mu,$

where $\mu=1$ if $\ell$ is odd and $\mu=0$ otherwise. The only extremal graph
is $G_{F}(n)$.

One can see that Theorem 2 is valid only when $n$ is exponential in $\ell$,
which is very large. Furthermore, Bushaw and Kettle [3] posed the following.

###### Conjecture 1

(Bushaw and Kettle [3]) Theorem 2 holds for all $n=\Omega\left(|F|\right)$.

This conjecture is still open now. Soon after, Lidický et al. [21] extended
Bushaw and Kettle’s result by determining $ex(n,F)$ for $F\not=kP_{3}$ and
sufficiently large $n$, and $G_{F}(n)$ is the extremal graph. Recently, Yuan
and Zhang [27] determined $ex(n,F)$ and the extremal graphs for all $n$ when
$F$ contains at most one odd components.

In 2016, Alon and Shikhelman [1] extended the idea of the Turán number to the
generalized Turán number $ex(n,T,H)$, that is, the maximum possible number of
copies of $T$ in an $H$-free graph $G$ on $n$ vertices. Obviously,
$ex(n,K_{2},H)=ex(n,H)$. Before this concept was proposed formally, there are
several papers dealing with the function $ex(n,T,H)$ for $T\neq K_{2}$,
related papers can refer to [2, 9, 16, 17, 18, 28]. Since 2016, the problem of
estimating generalized Turán number has received a lot of attentions. The most
attractive problem maybe is to determine $ex(n,K_{s},H)$.

Alon and Shikhelman [1] generalized Erdős-Stone-Simonovits theorem as below:

$ex(n,K_{s},H)=\binom{\chi-1}{s}\left(\frac{n}{\chi-1}\right)^{s}+o(n^{s}),$

where $\chi\geq 3$ is the chromatic number of $H$. Ma and Qiu [22] improved
the error term $o(n^{s})$ up to a constant factor. Luo [20] obtained the upper
bound of $ex(n,K_{s},P_{\ell})$, which extends Theorem 1.

###### Theorem 3

(Luo [20]) $ex(n,K_{s},P_{\ell})\leq\frac{n}{\ell-1}\binom{\ell-1}{s}$ and the
equality holds if and only if $(\ell-1)|n$.

Wang [26] determined $ex(n,K_{s},kK_{2})$, which extends the result obtained
by Erdős and Gallai in [10]. Some other results about generalized Turán number
can be found in [4, 14, 15, 23].

Motivated by the results of Bushaw and Kettle [3] and Lidický et al. [21], we
consider the generalized Turán number $ex(n,K_{s},H)$ for $H$ being a linear
forest in more general situation. The main result of this paper is the
following.

###### Theorem 4

Let $F$ be a linear forest so that $\ell_{i}\not=3$ for $1\leq i\leq k$ and
$k\geq 2$. Suppose $n\geq
5\binom{|F|-1}{s}^{2}/\left({(|F|-1)\binom{\delta_{F}}{s-1}}\right)+\delta_{F}$
and $s\leq\delta_{F}+1$. If $F\neq 2P_{\ell}$ with $\ell$ odd, then

$ex(n,K_{s},F)=max\left\\{\mathcal{N}_{s}(G_{F}(n)),ex(n,K_{s},P_{\ell_{1}})\right\\},$

and if $F=2P_{\ell}$ with $\ell$ odd, then

$ex(n,K_{s},F)=\left\\{\begin{array}[]{ll}\mathcal{N}_{s}(G_{F}(n)),&~{}for~{}s\leq\delta_{F},\\\
\lfloor\frac{n-1}{\ell-1}\rfloor\ell+\mu,&~{}for~{}s=\delta_{F}+1,\end{array}\right.$

where $\mu=1$ if $n-1\equiv\ell-2$ (mod $\ell-1$), and $\mu=0$ otherwise.

It is worth noting that in Theorem 4, $\mathcal{N}_{s}(G_{F}(n))\geq
ex(n,K_{s},P_{\ell_{1}})$ is not always true. For example, if $s\geq 3$ and
$\ell_{1}\gg\ell_{2}+\cdots+\ell_{k}$, then $\mathcal{N}_{s}(G_{F}(n))\leq
ex(n,K_{s},P_{\ell_{1}})$. Thus it is reasonable to use
$max\\{\mathcal{N}_{s}(G_{F}(n)),ex(n,K_{s},P_{\ell_{1}})\\}$ rather than
$\mathcal{N}_{s}(G_{F}(n))$. However, it is always true that
$\mathcal{N}_{s}(G_{F}(n))\geq ex(n,K_{s},P_{\ell_{1}})$ if $s=2$. Thus, we
have

###### Corollary 1

Let $F$ be a linear forest so that $\ell_{i}\not=3$ for $1\leq i\leq k$ and
$k\geq 2$. If $n=\Omega\left(|F|^{2}\right)$, then $ex(n,F)=e(G_{F}(n))$.

This implies Conjecture 1 is indeed true for all
$n=\Omega\left(|F|^{2}\right)$, which reduces the lower bound for $n$ in
Theorem 2 from exponential to polynomial in $|F|$.

The main idea to prove Theorem 4 is to delete one vertex of small degree each
step from an $F$-free graph until the remaining graph is empty or has large
minimum degree. And then we count the number of copies of $K_{s}$ in the
remaining graph. To do this, we have to characterize the structure of an
$F$-free graph with high minimum degree, which is a key ingredient in proving
Theorem 4.

###### Theorem 5

Let $F$ be a linear forest so that $\ell_{i}\not=3$ for $1\leq i\leq k$ and
$k\geq 2$. If $G$ is an $F$-free connected graph with
$\delta(G)\geq\delta_{F}$ and $|G|=n\geq 2|F|$, then $G\subseteq G_{F}(n)$
unless

  1. 1.

$F\in\\{P_{\ell+1}\cup P_{\ell}$, $2P_{\ell}\\}$ with $\ell$ even, or
$F\in\\{P_{\ell+2}\cup P_{\ell}$, $P_{\ell+1}\cup P_{\ell},2P_{\ell}\cup
P_{2}\\}$ with $\ell$ odd, and $G=K_{1}+tK_{\ell-1}$.

  2. 2.

$F=2P_{\ell}$ with $\ell$ odd, and $G\subseteq K_{1}+(t_{1}K_{\ell-1}\cup
t_{2}K_{\ell-2})$.

  3. 3.

$F=3P_{5}$ and $G=K_{2}+tK_{4}$ or $G=E_{2}+tK_{4}$.

Theorem 5 is of interest in its own right. In fact, Johansson [19] proved
that: For any $F$, if $|G|=|F|$ and $\delta(G)\geq\delta_{F}+1$, then
$F\subseteq G$. Later, Chen et al. [5] and Egawa and Ota [11] independently
obtained a stronger result: For any $F$, if $|G|\geq|F|$ and
$\sigma_{3}(G)\geq 3(\delta_{F}+1)$, then $F\subseteq G$, where
$\sigma_{3}(G)$ is the minimum degree sum of three nonadjacent vertices. Chen
and Zhang [7] obtained a version of stability result for $F$ contains at most
one odd path, they characterized the structure of connected graph $G$ if $G$
contains no $F$ and $\delta(G)=\delta_{F}$.

The remainder of this paper is organized as follows. In Section 2, we give
some preliminaries. In Section 3, we prove the key Theorem 5. In Section 4, we
give the proof of Theorem 4 using Theorem 5,

##  2 Preliminaries

In this section, we give some lemmas which will be used to prove Theorems 4
and 5.

###### Lemma 1

(Dirac [8]) Let $G$ be a connected graph with $\delta(G)=\delta$, then

$p(G)\geq min\left\\{|G|,2\delta+1\right\\}.$

###### Lemma 2

(Chvátal and Erdős [6]) Let $G$ be a graph so that $\alpha(G)\leq\kappa(G)+1$,
then $G$ has a hamiltonian path.

###### Lemma 3

(Chen et al. [5]) Let $G$ be a connected graph of order
$n\geq\sum_{i=1}^{k}n_{i}$. If $\sigma_{3}(G)\geq
3\sum_{i=1}^{k}\lfloor\frac{n_{i}}{2}\rfloor$, then $G$ contains linear forest
$P_{n_{1}}\cup P_{n_{2}}\cup\cdots\cup P_{n_{k}}$.

###### Lemma 4

(Chen et al. [5]) Let $G$ be a connected graph of order $n$, then the
following two results hold.

  1. (i)

If $G$ contains exactly two end blocks, then $p(G)\geq
min\\{n,\sigma_{3}(G)\\}$.

  2. (ii)

If $G$ contains only one cut vertex and there is a block that has no
hamiltonian path starting at this cut vertex, then $p(G)\geq
min\\{n,\sigma_{3}(G)\\}$.

###### Lemma 5

(Saito [24]) Suppose $G$ is a $2$-connected graph of order $n$. Then either
$G$ contains a strong dominating cycle or $p(G)\geq
min\\{n,\sigma_{3}(G)-1\\}$.

###### Lemma 6

Let $F$ be a linear forest so that $\ell_{i}\not=3$ for $1\leq i\leq k$ and
$k\geq 2$. If $P_{2\delta_{F}+1}\cup P_{\delta_{F}}$ is $F$-free, then
$F\in\\{5P_{5},2P_{\ell},P_{\ell+1}\cup P_{\ell}\\}$, or $F=P_{\ell+2}\cup
P_{\ell},2P_{\ell}\cup P_{2}$ and $\ell$ is odd,

_Proof_. It is obvious that $\ell_{1}\leq 2\delta_{F}+1$, and hence
$P_{\ell_{1}}\subseteq P_{2\delta_{F}+1}$. Suppose $t$ is the maximum number
such that $P_{\ell_{1}}\cup\cdots\cup P_{\ell_{t}}\subseteq
P_{2\delta_{F}+1}$. Because $F\not\subseteq P_{2\delta_{F}+1}\cup
P_{\delta_{F}}$, $P_{\ell_{t+1}}\cup\cdots\cup P_{\ell_{k}}\not\subseteq
P_{\delta_{F}}$. Hence we have

$\displaystyle\ell_{1}+\cdots+\ell_{t+1}\geq
2(\delta_{F}+1)=\sum\limits_{i=1}^{k}\ell_{i}-\sum\limits_{i=1}^{k}\chi_{\mathcal{O}}(\ell_{i}),$
(2.1)
$\displaystyle\ell_{t+1}+\cdots+\ell_{k}\geq\delta_{F}+1=\frac{1}{2}\left(\sum\limits_{i=1}^{k}\ell_{i}-\sum\limits_{i=1}^{k}\chi_{\mathcal{O}}(\ell_{i})\right),$
(2.2)

By (2.1) and (2.2), we have

$\displaystyle\ell_{t+1}+3\chi_{\mathcal{O}}(\ell_{t+1})$
$\displaystyle\geq\big{(}\ell_{1}-3\chi_{\mathcal{O}}(\ell_{1})\big{)}+\cdots+\big{(}\ell_{t}-3\chi_{\mathcal{O}}(\ell_{t})\big{)}+$
$\displaystyle~{}~{}~{}~{}\big{(}\ell_{t+2}-3\chi_{\mathcal{O}}(\ell_{t+2})\big{)}+\cdots+\big{(}\ell_{k}-3\chi_{\mathcal{O}}(\ell_{k})\big{)}.$
(2.3)

Assume that $\ell_{t+1}$ is even. If $t+1\geq 3$, then by (2.3) we have

$\ell_{t+1}\geq(\ell_{1}-3\chi_{\mathcal{O}}(\ell_{1}))+(\ell_{2}-3\chi_{\mathcal{O}}(\ell_{2}))>\ell_{t+1},$

or $F=2P_{5}\cup P_{4}$ which contradicts (2.2). Hence, $t+1=2$. Note that
(2.1) implies $k=t+1=2$ and (2.2) implies $\ell_{1}\leq\ell_{2}+1$. Let
$\ell_{2}=\ell$ be even, then $F=2P_{\ell},P_{\ell+1}\cup P_{\ell}$.

If $\ell_{t+1}$ is odd, then $\ell_{t+1}\geq 5$. If $t+1\geq 4$, then we have
$t+1\not=k$ by (2.2) and

$\ell_{t+1}+3\geq(\ell_{1}-3\chi_{\mathcal{O}}\ell_{1}))+\cdots+(\ell_{3}-3\chi_{\mathcal{O}}(\ell_{3}))+\cdots+(\ell_{k}-3\chi_{\mathcal{O}}(\ell_{k}))$

by (2.3), which holds only if $t+1=4$ and $F\in\\{5P_{5},4P_{5}\cup P_{2}\\}$.
Because $4P_{5}\cup P_{2}\subset P_{2\delta_{F}+1}\cup P_{\delta_{F}}$, we
have $F=5P_{5}$. If $t+1\leq 3$, then by (2.1), we have $k=t+1$ or
$F=P_{\ell_{1}}\cup\cdots\cup P_{\ell_{t+1}}\cup P_{2}$. In the former case,
by (2.2) we can deduce that

$\ell_{t+1}+1\geq\left(\ell_{1}-\chi_{\mathcal{O}}(\ell_{1})\right)+\cdots+\left(\ell_{t}-\chi_{\mathcal{O}}(\ell_{t})\right),$

which implies $t+1=2$ and $\ell_{1}\leq\ell_{2}+2$. that is,
$F\in\\{2P_{\ell_{2}},P_{\ell_{2}+1}\cup P_{\ell_{2}},P_{\ell_{2}+2}\cup
P_{\ell}\\}$. In the latter case, by (2.2) we can deduce that
$F\in\\{3P_{5}\cup P_{2},2P_{\ell_{2}}\cup P_{2},P_{\ell_{2}+1}\cup
P_{\ell_{2}}\cup P_{2},P_{\ell_{2}+2}\cup P_{\ell_{2}}\cup
P_{2},P_{\ell_{2}+3}\cup P_{\ell_{2}}\cup P_{2},P_{\ell_{2}+4}\cup
P_{\ell_{2}}\cup P_{2}\\}$. It is easy to check that only if
$F=2P_{\ell_{2}}\cup P_{2}$, $P_{2\delta_{F}+1}\cup P_{\delta_{F}}$ is
$F$-free. Let $\ell_{2}=\ell$ be odd. Then we can see that
$F\in\\{5P_{5},2P_{\ell},2P_{\ell}\cup P_{2},P_{\ell+1}\cup
P_{\ell},P_{\ell+2}\cup P_{\ell}\\}$.

Thus, the result follows by the arguments above. $\hfill\blacksquare$

###### Lemma 7

Let $F$ be a linear forest so that $\ell_{i}\not=3$ for $1\leq i\leq k$ and
$k\geq 2$. If $P_{2\delta_{F}+1}\cup P_{\delta_{F}+1}$ is $F$-free, then
$F=2P_{\ell}$ and $\ell$ is odd. Furthermore, $P_{2\delta_{F}+1}\cup
P_{\delta_{F}+2}$ contains $F$.

_Proof_. Because $P_{2\delta_{F}+1}\cup P_{\delta_{F}}$ is a subgraph of
$P_{2\delta_{F}+1}\cup P_{\delta_{F}+1}$, by Lemma 6, it is sufficient to
consider $F=5P_{5},2P_{\ell},P_{\ell+1}\cup P_{\ell}$, $P_{\ell+2}\cup
P_{\ell},2P_{\ell}\cup P_{2}$. After an easy check, we find that
$P_{2\delta_{F}+1}\cup P_{\delta_{F}+1}$ is $F$-free only for $F=2P_{\ell}$
and $\ell$ is odd. The latter part follows from the fact that
$P_{2\delta_{F}+1}\cup P_{\delta_{F}+2}$ contains $2P_{\ell}$.
$\hfill\blacksquare$

###### Lemma 8

Let $F$ be a linear forest so that $F\not=kP_{5}$ and $\ell_{i}\not=3$ for
$1\leq i\leq k$. Suppose $K_{s,t}=(X,Y)\subseteq G$ with $|X|=\delta_{F}$ and
$|Y|\geq\sum_{i=1}^{k}\ell_{i}-\delta_{F}$. Then $G$ has an $F$ if some
$\ell_{i}$ is even and $v_{1}v_{2}\in G-(X\cup Y)$ such that $x_{1}\in
N_{X}(v_{1})$, or each $\ell_{i}$ is odd and $G-(X\cup Y)$ has a path
$v_{1}v_{2}v_{3}$ such that $x_{1}\in N_{X}(v_{1})$ or two independent edges
$v_{1}v_{2},v_{3}v_{4}$ such that
$v_{1}x_{1},v_{3}x_{2}\in[\\{v_{1},v_{3}\\},X]$ and $x_{1}\not=x_{2}$.

_Proof_. By the assumption, we let $\ell_{i}$ be even or $\ell_{i}\geq 7$ be
odd. Partition $(X,Y)$ into $(X_{1},Y_{1}),(X_{2},Y_{2}),...,(X_{k},Y_{k})$
such that $|X_{j}|=\lfloor\frac{\ell_{j}}{2}\rfloor$ and
$|Y_{j}|=\lceil\frac{\ell_{j}}{2}\rceil$ if $j\not=i$,
$|X_{i}|=\lfloor\frac{\ell_{i}}{2}\rfloor-1$ and
$Y_{i}=Y\backslash(\cup_{j\not=i}Y_{j})$. Clearly,
$|Y_{i}|\geq\lceil\frac{\ell_{i}}{2}\rceil+1$ and $(X_{j},Y_{j})$ has a
$P_{\ell_{j}}$ if $j\not=i$. If $\ell_{i}=2$, then $v_{1}v_{2}$ is a
$P_{\ell_{i}}$. If $\ell_{i}\geq 4$ be even, we let $x_{1}\in X_{i}$. Then
$(X_{i},Y_{i})$ has a $P_{\ell_{i}-2}$ starting at $x_{1}$, which together
with $v_{1}v_{2}$ gives a $P_{\ell_{i}}$ in $G$. If $\ell_{i}\geq 7$ is odd,
we let $x_{1},x_{2}\in X_{i}$. Then $(X_{i},Y_{i})$ has a $P_{\ell_{i}-3}$
starting at $x_{1}$ and a $P_{\ell_{i}-4}$ starting at $x_{1}$ and ending at
$x_{2}$. Thus, the path $P_{\ell_{i}-3}$ together with $v_{1}v_{2}v_{3}$ or
the path $P_{\ell_{i}-4}$ together with $v_{1}v_{2},v_{3}v_{4}$ gives a
$P_{\ell_{i}}$ in $G$. Therefore, the conclusion holds.$\hfill\blacksquare$

###### Lemma 9

Let $F$ be a linear forest so that $F\not=kP_{5}$ and $\ell_{i}\not=3$ for
$1\leq i\leq k$ and $G$ an $F$-free connected graph with $|G|\geq 2|F|$. If
$G$ contains a strong dominating path $P$ such that $d(v)\geq\delta_{F}$ for
any $v\in V(G)\backslash V(P)$, then $G\subseteq G_{F}(n)$.

_Proof_. Let $P=v_{1}v_{2}\cdots v_{p}$ be a longest path with the property
and $Y=V(G)\backslash V(P)$. By the assumption, $Y\not=\emptyset$. By the
maximality of $P$, $N_{Y}(v_{1})=N_{Y}(v_{p})=\emptyset$ and any vertex of $Y$
has no consecutive neighbors in $P$, which implies $|P|\geq 2\delta_{F}+1$. If
$|P|=2\delta_{F}+1$, then $N(y)=\\{v_{2},v_{4},\ldots,v_{p-1}\\}$ for any
$y\in Y$. Let $X=N(y)$. Obviously, $|X|=\delta_{F}$, $|X|+|Y|\geq|F|$ and
$G[X,Y]$ is a complete bipartite graph. By Lemma 8, $P-X$ contains at most one
edge, according to $F$ consists of only odd paths or not. This implies
$G\subseteq G_{F}(n)$. Hence we may assume $|P|\geq 2\delta_{F}+2$.

We proceed on by induction on $k$.

If $k=1$, then since $\ell_{1}-1\geq|P|\geq 2\delta_{F}+2\geq
2\lfloor\frac{\ell_{1}}{2}\rfloor$, we deduce that $|P|=\ell_{1}-1$ and
$\ell_{1}\geq 7$ is odd. In this case, $d(y)=\delta_{F}=d$ for any $y\in Y$.
Let $y\in Y$ be given and $N(y)=X=\\{x_{1},x_{2},...,x_{d}\\}$, where the
subscripts occur along $P$ from $v_{1}$ to $v_{p}$. Set
$Q_{i}=x_{i}\overrightarrow{P}x_{i+1}$ for $0\leq i\leq d$, where
$x_{0}=v_{1}$ and $x_{d+1}=v_{p}$. Suppose there is some $y^{\prime}\in
Y\backslash\\{y\\}$ such that $N(y^{\prime})\not=X$. Let $a\in
N_{Q_{i}}(y^{\prime})\backslash X$. Obviously, $|Q_{i}|=3$ or 4. If $i=0$ or
$i=d$, then $|Q_{i}|=3$ and $|Q_{j}|=3$ for $1\leq j\leq d-1$. By symmetry of
$Q_{0}$ and $Q_{d}$, we assume that $i=0$. By the maximality of $P$,
$x_{1}\notin N(y^{\prime})$ and
$N(y^{\prime})\cap\\{x_{1}^{+},x_{d}\\}\not=\emptyset$. Thus, either
$x_{0}ay^{\prime}x_{1}^{+}x_{1}yx_{2}\overrightarrow{P}x_{d+1}$ is a
$P_{\ell_{1}+1}$, or $x_{0}ay^{\prime}x_{d}\overleftarrow{P}x_{1}y$ is a
$P_{\ell_{1}}$, a contradiction. Hence we have $1\leq i\leq d-1$. If
$|Q_{i}|=3$, then by the maximality of $P$, $x_{i},x_{i+1}\notin
N(y^{\prime})$ and
$N(y^{\prime})\cap\\{x_{i}^{-},x_{i+1}^{+}\\}\not=\emptyset$. Thus,
$x_{0}\overrightarrow{P}x_{i}^{-}y^{\prime}ax_{i}yx_{i+1}\overrightarrow{P}x_{d+1}$
or
$x_{0}\overrightarrow{P}x_{i}yx_{i+1}ay^{\prime}x_{i+1}^{+}\overrightarrow{P}x_{d+1}$
is a $P_{\ell_{1}+1}$, a contradiction. If $|Q_{i}|=4$, then $a=x_{i}^{+}$ or
$x_{i+1}^{-}$. By symmetry, we assume that $a=x_{i}^{+}$. By the maximality of
$P$, $x_{i},x_{i+1}^{-}\notin N(y^{\prime})$. If $x_{i}^{-}\in N(y^{\prime})$,
then
$x_{0}\overrightarrow{P}x_{i}^{-}y^{\prime}ax_{i}yx_{i+1}\overrightarrow{P}x_{d+1}$
is a $P_{\ell_{1}}$ and so $x_{i}^{-}\notin N(y^{\prime})$, which implies
$x_{i+1}\in N(y^{\prime})$. Thus,
$x_{0}\overrightarrow{P}x_{i}yx_{d}\overleftarrow{P}x_{i+1}y^{\prime}ax_{i+1}^{-}$
is a $P_{\ell_{1}}$, a contradiction. Therefore, $N(y^{\prime})=X$ for any
$y^{\prime}\in Y$. By Lemma 8, $P-X$ has at most one edge, and hence we have
$G\subseteq G_{F}(n)$.

Assume that $k\geq 2$ and the conclusion holds for $k-1$. Consider
$F=P_{\ell_{1}}\cup\cdots\cup P_{\ell_{k}}$. Let $F^{\prime}=F-P_{q}$, where
$q=5$ if some $\ell_{i}=5$, and $q=\ell_{k}$ otherwise. Set
$P^{\prime}=v_{1}v_{2}\cdots v_{q}$, $P^{\prime\prime}=P-V(P^{\prime})$ and
$G^{\prime}=G-V(P^{\prime})$. For any $y\in Y$, noting that
$d_{P^{\prime}}(y)\leq\lfloor\frac{q}{2}\rfloor$, we have
$d_{P^{\prime\prime}}(y)\geq\delta_{F^{\prime}}$. Since $|P|\geq
2\delta_{F}+2$, we have $|P^{\prime\prime}|\geq 2\delta_{F}+2-|P^{\prime}|\geq
2\delta_{F^{\prime}}+1$. Clearly, $G^{\prime}$ is $F^{\prime}$-free and
$|G^{\prime}|=n-q\geq 2|F^{\prime}|$, and $P^{\prime\prime}$ is a strong
dominating path of $G^{\prime}$ such that
$d_{P^{\prime\prime}}(y)\geq\delta_{F^{\prime}}$ for any $y\in Y$. By
induction hypothesis, $G^{\prime}\subseteq G_{F^{\prime}}(n-q)$. Let
$V(G^{\prime})=U\cup V$ with $|U|=\delta_{F^{\prime}}$ and
$V=V(G^{\prime})\backslash U$ such that $U=V(K_{\delta_{F^{\prime}}})$ in
$G_{F^{\prime}}(n-q)$. By the definition of $G_{F^{\prime}}(n-q)$, we can see
that any path of order at least $2\delta_{F^{\prime}}+1$ in $G^{\prime}$ must
contain all vertices of $U$. Thus, we have $U\subseteq V(P^{\prime\prime})$
and so $Y\subseteq V$. Since $G^{\prime}[V]$ has at most one edge, $Y$ is an
independent set and $d(y)\geq\delta_{F^{\prime}}$ for any $y\in Y$, we can
deduce that all vertices in $Y$ have the same neighborhoods on
$P^{\prime\prime}$ except at most one vertex $y^{\prime}\in Y$, and
$d_{P^{\prime\prime}}(y)=\delta_{F^{\prime}}$ for any $y\in
Y\backslash\\{y^{\prime}\\}$. Let $Q^{\prime\prime}=v_{1}v_{2}\cdots v_{p-q}$
and $Q^{\prime}=P-Q^{\prime\prime}$. By the symmetry of $P^{\prime\prime}$ and
$Q^{\prime\prime}$, all vertices in $Y$, except at most one vertex
$y^{\prime\prime}\in Y$, have the same neighborhoods on $Q^{\prime\prime}$,
and $d_{Q^{\prime\prime}}(y)=\delta_{F^{\prime}}$ for any $y\in
Y\backslash\\{y^{\prime\prime}\\}$.

If $|P^{\prime}|=\ell_{k}$ is even, then since
$d_{P^{\prime\prime}}(y)=\delta_{F^{\prime}}$ and $d(y)\geq\delta_{F}$ for any
$y\in Y\backslash\\{y^{\prime}\\}$, we can get
$d_{P^{\prime}}(y)=\frac{\ell_{k}}{2}$, and hence
$N_{P^{\prime}}(y)=\\{v_{2},\ldots,v_{\ell_{k}}\\}$. Thus,
$N_{P}(y_{1})=N_{P}(y_{2})$ for any $y_{1},y_{2}\in
Y\backslash\\{y^{\prime}\\}$. If $|P^{\prime}|=\ell_{k}$ is odd or
$|P^{\prime}|=5$, then noting that $|P^{\prime\prime}|\geq
2\delta_{F^{\prime}}+1$, we have

$|Q^{\prime\prime}|=|P^{\prime\prime}|\geq
2\delta_{F^{\prime}}+1=\sum_{i=1}^{k}\left(\ell_{i}-\chi_{B}(\ell_{i})\right)-(q-\chi_{B}(q))-1\geq|P’|,$

unless $F=2P_{\ell_{1}}$ and $\ell_{1}$ is odd, or $F\in\\{P_{5}\cup
P_{2},P_{5}\cup P_{4},P_{5}\cup 2P_{2}\\}$. If
$|Q^{\prime\prime}|\geq|P^{\prime}|$, then $P^{\prime}\subseteq
Q^{\prime\prime}$. Thus, $N_{P^{\prime}}(y_{1})=N_{P^{\prime}}(y_{2})$ and
hence $N_{P}(y_{1})=N_{P}(y_{2})$ for any $y_{1},y_{2}\in
Y\backslash\\{y^{\prime},y^{\prime\prime}\\}$. If $F=2P_{\ell_{1}}$ and
$\ell_{1}$ is odd, then
$2\delta_{F^{\prime}}+2\geq|Q^{\prime\prime}|=|P^{\prime\prime}|\geq
2\delta_{F^{\prime}}+1$. Let $y_{1},y_{2}\in
Y\backslash\\{y^{\prime},y^{\prime\prime}\\}$, then
$d_{P^{\prime\prime}}(y_{i})=d_{Q^{\prime\prime}}(y_{i})=\lfloor\ell_{1}/2\rfloor-1$
for $i=1,2$ by the arguments above. Since
$d(y_{i})\geq\delta_{F}=2\lfloor\frac{\ell_{1}}{2}\rfloor-1$ and
$|P-Q^{\prime\prime}-P^{\prime\prime}|\leq 2$, $y_{i}$ has exactly one
neighbor in $P-Q^{\prime\prime}-P^{\prime\prime}$. If
$|P^{\prime\prime}|=2\delta_{F^{\prime}}+1=\ell_{1}-2$, then $|P|=2\ell_{1}-2$
and
$V(P-Q^{\prime\prime}-P^{\prime\prime})=\\{v_{\ell_{1}-1},v_{\ell_{1}}\\}$. If
$y_{1},y_{2}$ have different neighbors in $\\{v_{\ell_{1}-1},v_{\ell_{1}}\\}$,
it is clear that $G$ contains $2P_{\ell_{1}}$, and so $y_{1},y_{2}$ have the
same neighbor in $\\{v_{\ell_{1}-1},v_{\ell_{1}}\\}$. Thus we have
$N_{P}(y_{1})=N_{P}(y_{2})$. If
$|P^{\prime\prime}|=2\delta_{F^{\prime}}+2=\ell_{1}-1$, then $|P|=2\ell_{1}-1$
and $V(P-Q^{\prime\prime}-P^{\prime\prime})=\\{v_{\ell_{1}}\\}$, and so
$v_{\ell_{1}}\in N_{P}(y_{1})\cap N_{P}(y_{2})$, which implies that
$N_{P}(y_{1})=N_{P}(y_{2})$. If $F\in\\{P_{5}\cup P_{2},P_{5}\cup
P_{4},P_{5}\cup 2P_{2}\\}$, then since $|P|\geq 2\delta_{F}+2$ and
$d_{P}(y)\geq\delta_{F}$ for any $y\in Y$, it is easy to check that $G$
contains $F$, a contradiction.

By the arguments above, we have $N_{P}(y_{1})=N_{P}(y_{2})$ for any
$y_{1},y_{2}\in Y\backslash\\{y^{\prime},y^{\prime\prime}\\}$.

Let $Y^{\prime}=Y\backslash\\{y^{\prime},y^{\prime\prime}\\}$, $y\in
Y^{\prime}$ be given and $X=N(y)$, then $|X|=\delta_{F}$. Obviously,
$|Y^{\prime}|\geq|F|-|X|$ and the edges between $X$ and $Y^{\prime}$ form a
complete bipartite graph in $G$. Since $G$ is $F$-free, by applying Lemma 8 on
$G-\\{y^{\prime},y^{\prime\prime}\\}$, we have
$G-\\{y^{\prime},y^{\prime\prime}\\}\subseteq G_{F}(n)$. Add $y^{\prime}$ and
$y^{\prime\prime}$ (if they exist) to $G-\\{y^{\prime},y^{\prime\prime}\\}$,
then since $G$ is $F$-free, it is not difficult to show $G\subseteq G_{F}(n)$.
$\hfill\blacksquare$

To discuss the structure of an $F$-free graph for $F=kP_{5}$, we need to
define a connected graph $G_{F}(n,i)$ of order $n$ as follows. Add $i$ new
independent edges $e_{1}$,…,$e_{i}$ to $K_{\delta_{F}}+E_{n-\delta_{F}-2i}$
and then connect $V(\cup_{j=1}^{i}e_{j})$ and $V(K_{\delta_{F}})$ such that
$[V(e_{j}),V(K_{\delta_{F}})]$ contains two independent edges for each $e_{j}$
except at most two of $e_{1},e_{2},...,e_{i}$, and any vertex in
$V(K_{\delta_{F}})$ has neighbors in at most one $e_{j}$, illustrated in
Figure 2.

Figure 2. $G_{F}(n,i)$ (oval denotes a clique
$K_{\delta_{F}}$)$e_{1}$$\cdots$$e_{i}$

###### Lemma 10

Let $F=kP_{5}$ with $k\geq 2$ and $G$ be an $F$-free connected graph with
$|G|\geq 2|F|$. If $G$ contains a strong dominating path $P$ such that
$d(v)\geq\delta_{F}$ for any $v\in V(G)\backslash V(P)$, then $G\subseteq
G_{F}(n,i)$, where $i\leq k$.

_Proof_. Let $P=v_{1}v_{2}\cdots v_{p}$ be a longest path with this property
and $Y=V(G-P)$. By the maximality of $P$,
$N_{Y}(v_{1})=N_{Y}(v_{p})=\emptyset$ and any vertex of $Y$ has no consecutive
neighbors in $P$, and so $|P|\geq 2\delta_{F}+1$. If $|P|=2\delta_{F}+1$, then
$N(y)=\\{v_{2},v_{4},\ldots,v_{p-1}\\}$ for any $y\in Y$. This implies that
$G\subseteq K_{\delta_{F}}+E_{n-\delta_{F}}$ and hence the conclusion holds.
Thus, we may assume $|P|\geq 2\delta_{F}+2$.

We proceed on by induction on $k$.

Assume that $k=2$. Then $\delta_{F}=3$ and $8\leq p\leq 9$. Let
$y,y^{\prime}\in Y$. We first show that $N(y)=N(y^{\prime})$. Suppose $p=8$.
If $\\{v_{2},v_{7}\\}\subset N(y)$ for some $y$, then by the symmetry we may
assume $N(y)=\\{v_{2},v_{4},v_{7}\\}$. If
$N(y’)\cap\\{v_{3},v_{5},v_{6}\\}\not=\emptyset$, then we can find $2P_{5}$, a
contradiction. Hence $N(y’)=N(y)$. If $\\{v_{2},v_{7}\\}\not\subset N(y)$ for
any $y$, then either $N(y)=\\{v_{2},v_{4},v_{6}\\}$ or
$N(y)=\\{v_{3},v_{5},v_{7}\\}$. If $N(y)=\\{v_{2},v_{4},v_{6}\\}$ and
$N(y^{\prime})=\\{v_{3},v_{5},v_{7}\\}$, then we can find $2P_{5}$ easily,
also a contradiction. Hence $N(y)=N(y^{\prime})$. Assume that $p=9$. Since $G$
is $F$-free, $N(y)\cap\\{v_{4},v_{6}\\}=\emptyset$ and
$\\{v_{2},v_{8}\\}\not\subseteq N(y)$ for any $y\in Y$. Thus, by symmetry we
may assume $N(y)=\\{v_{3},v_{5},v_{7}\\}$ or $N(y)=\\{v_{3},v_{5},v_{8}\\}$.
If $N(y^{\prime})\not=N(y)$, then we can find $2P_{5}$ in
$G[V(P)\cup\\{y,y^{\prime}\\}]$, and hence $N(y)=N(y^{\prime})$. Therefore, we
always have $N(y)=N(y^{\prime})$. Now let $X=N(y)$, then $|X|=\delta_{F}$,
$|X|+|Y|\geq 10$ and $[X,Y]$ is a complete bipartite. Consider the vertices
$P-X$ and note that $G$ has no $2P_{5}$, we have $G\subset G_{F}(n,i)$ with
$i\leq 2$.

Assume that $k\geq 3$ and the conclusion holds for $k-1$. Let $F’=(k-1)P_{5}$,
$P’=v_{1}v_{2}\cdots v_{5}$ and $P^{\prime\prime}=P-P’$. Since
$d_{P^{\prime}}(y)\leq 2$ for any $y\in Y$, $P^{\prime\prime}$ is a strong
dominating path of $G-P’$ and $d_{P^{\prime\prime}}(v)\geq\delta_{F’}$.
Clearly, $G-P’$ is $F’$-free. By induction hypothesis, $G-P’\subset
G_{F’}(n-5,i)$ with $i\leq k-1$. By the definition of $G_{F’}(n,i)$, any
strong dominating path of $G-P^{\prime}$ must contain all vertices of the $i$
independent edges except at most one vertex $y^{\prime}$ and all vertices in
the clique $K_{\delta_{F’}}$, and so all vertices in $Y-\\{y’\\}$ have the
same neighbors on $P^{\prime\prime}$. Let $Q^{\prime\prime}=v_{1}v_{2}\cdots
v_{p-5}$, then $P’\subset Q^{\prime\prime}$. By symmetry of $Q^{\prime\prime}$
and $P^{\prime\prime}$, all vertices in $Y-\\{y^{\prime\prime}\\}$ have the
same neighbors on $Q^{\prime\prime}$ and hence on $P’$. Let
$Y^{\prime}=Y\backslash\\{y^{\prime},y^{\prime\prime}\\}$. By the arguments
above, we have $N_{P}(y_{1})=N_{P}(y_{2})$ for any $y_{1},y_{2}\in
Y^{\prime}$. Let $X=N(y)$ for some $y\in Y^{\prime}$, then $|X|=\delta_{F}$,
$|X|+|Y^{\prime}|\geq 5k$ and $[X,Y^{\prime}]$ is a complete bipartite.
Consider the vertices in $P-X$ and note that $G$ is $F$-free, we have
$G\subset G_{F}(n,i)$, $i\leq k$. $\hfill\blacksquare$

##  3 $F$-free graphs with large minimum degree

In this section, we will give the proof of Theorem 5, which characterizes the
structure of an $F$-free graph $G$ with $\delta(G)\geq\delta_{F}$. Proof of
Theorem 5. Suppose that $G$ is 2-connected. If $G$ has a strong dominating
path, then $G\subseteq G_{F}(n)$ for $F\not=kP_{5}$ by Lemma 9, and
$G\subseteq G_{F}(n,i)$ for $F=kP_{5}$ by Lemma 10. In the latter case, we
have $i\leq 1$ because $\delta(G)\geq\delta_{F}$ and hence $G\subseteq
G_{F}(n,1)\subseteq G_{F}(n)$. Therefore, we may assume that $G$ has no
dominating path.

By Lemma 5, $p(G)\geq min\\{n,\sigma_{3}(G)-1\\}$. Since $G$ is $F$-free, we
have

$\begin{split}|F|>\sigma_{3}(G)-1&\geq\frac{3}{2}\sum\limits_{i=1}^{k}(\ell_{i}-\chi_{\mathcal{O}}(\ell_{i}))-4=\sum_{i=1}^{k}\ell_{i}+\frac{1}{2}\sum\limits_{i=1}^{k}(\ell_{i}-3\chi_{\mathcal{O}}(\ell_{i}))-4,\\\
\end{split}$

which implies

$F\in\\{3P_{5},2P_{5}\cup P_{2},P_{5}\cup 2P_{2},3P_{2},P_{7}\cup
P_{5},P_{7}\cup P_{2},P_{5}\cup P_{4},P_{4}\cup P_{2},2P_{5},P_{5}\cup
P_{2},2P_{2}\\}.$

Let $P=v_{1}v_{2}\cdots v_{p}$ be a longest path in $G$. By Lemma 5, $p\geq
3\delta_{F}-1\geq|F|-2$. Assume $G-P$ has a component $H$ with $|H|\geq 2$.
Since $G$ is 2-connected, there exist two independent edges
$x_{1}v_{i},x_{t}v_{j}$ with $x_{1},x_{t}\in V(H)$ and $i<j$. Let
$P^{\prime}=x_{1}x_{2}\cdots x_{t}$ be a path connecting $x_{1}$ and $x_{t}$
in $H$. Obviously, $t\geq 2$. By the maximality of $P$, we have

$t+1\leq i\leq j-t-1<j\leq p-t.$ (3.1)

If $F\in\\{2P_{5}\cup P_{2},3P_{2},P_{5}\cup P_{2},2P_{2},P_{5}\cup
2P_{2},P_{4}\cup P_{2},P_{7}\cup P_{2}\\}$, then since $p\geq|F|-2$, we can
see that $G$ contains $F$, a contradiction. Hence, $F\in\\{P_{5}\cup
P_{4},P_{5}\cup P_{7},2P_{5},3P_{5}\\}$. If $i=3$ or $j=p-2$, then it is easy
to see that $P\cup P^{\prime}\cup\\{x_{1}v_{i},x_{t}v_{j}\\}$ contains $F$,
and hence $i\geq 4$ and $j\leq p-3$. This implies $p\geq 10$ and so
$F\in\\{P_{5}\cup P_{7},3P_{5}\\}$. If $F=P_{5}\cup P_{7}$, then
$\delta_{F}=4$ and $p=11$. By (3.1), $i=4$ or $j=8$, and hence $P\cup
P^{\prime}\cup\\{x_{1}v_{i},x_{t}v_{j}\\}$ contains $P_{5}\cup P_{7}$, a
contradiction. Thus, $F=3P_{5}$. In this case, $\delta_{F}=5$ and $p=14$. For
any edge $x^{\prime}x^{\prime\prime}\in G-P$, since $G$ has no $3P_{5}$, we
have $N_{P}(x^{\prime})\cup
N_{P}(x^{\prime\prime})\subseteq\\{v_{5},v_{10}\\}$. Noting that
$\delta(G)\geq 5$, we get $\delta(H)\geq 3$. Because $H$ contains no $P_{5}$,
$H=K_{4}$ and $N_{P}(x)=\\{v_{5},v_{10}\\}$ for any $x\in V(H)$. By symmetry,
we have $G[\\{v_{6},v_{7},v_{8},v_{9}\\}]=K_{4}$. Thus, $G-V(P)-V(H)$ has no
isolated vertices because such a vertex has at most 4 neighbors in $P$ which
contradicts $\delta(G)\geq 5$. Note that $\delta(G)\geq 5$ and $G$ has no
$3P_{5}$, we can see
$G[\\{v_{1},v_{2},v_{3},v_{4}\\}]=G[\\{v_{11},v_{12},v_{13},v_{14}\\}]=K_{4}$,
and $G=K_{2}+tK_{4}$ or $E_{2}+tK_{4}$.

Next we assume that $G$ is not 2-connected. We distinguish the following two
cases separately. Case 1. $G$ contains exactly two end blocks or $G$ contains
only one cut vertex.

If $G$ contains exactly two end blocks, or $G$ has only one cut vertex and
some block contains no hamiltonian path starting at the cut vertex, then by
Lemma 4, $p(G)\geq min\\{n,\sigma_{3}(G)\\}$. Since $G$ is $F$-free, we have

$|F|>\sigma_{3}(G)=\sum_{i=1}^{k}\ell_{i}+\frac{1}{2}\sum\limits_{i=1}^{k}(\ell_{i}-3\chi_{\mathcal{O}}(\ell_{i}))-3,$

which implies $F\in\\{2P_{5},P_{5}\cup P_{2},2P_{2}\\}$. Let
$P=v_{1}v_{2}\cdots v_{p}$ be a longest path in $G$, we have
$p=\sigma_{3}(G)=|F|-1$. If $F=P_{5}\cup P_{2}$, then $p=6$ and $G-P$ has no
edges, which implies $d_{P}(v)\geq\delta_{F}=2$ for any $v\in G-P$. In this
case, it is easy to find an $F$ in $G$, a contradiction. If $P=2P_{2}$, then
$G$ is a star and the result holds trivially. If $F=2P_{5}$, then
$\delta_{F}=3$ and $p=9$. If $P$ is a strong dominating path, then $G\subset
G_{F}(n,i)$ with $i\leq 2$ by Lemma 10. Noting that $\delta(G)\geq 3$, we find
$G$ is 2-connected, a contradiction. Hence $P$ is not a strong dominating
path. Since $G$ has no $2P_{5}$, $N_{P}(x)\cup
N_{P}(x^{\prime})\subseteq\\{x_{5}\\}$ for any $xx^{\prime}\in G-P$. Let $H$
be any component of $G-P$ with $|H|\geq 2$. Then $N_{P}(x)\subset\\{v_{5}\\}$
for any $x\in V(H)$ and so $\delta(H)\geq 2$. Since $H$ is $P_{5}$-free, we
have $|H|=3,4$ by Lemma 1. In addition, if $G-P$ has an isolated vertices $x$,
then $\\{v_{2},v_{8}\\}\not\subset N(v)$ for otherwise $G$ has $2P_{5}$, and
so we can assume $N(v)=\\{v_{3},v_{5},v_{7}\\}$ or $\\{v_{3},v_{5},v_{8}\\}$
by symmetry. In both case, $G$ contains $2P_{5}$, a contradiction. Thus, $G-P$
has no isolated vertices. If there is an edge between
$\\{v_{1},v_{2},v_{3},v_{4}\\}$ and $\\{v_{6},v_{7},v_{8},v_{9}\\}$, then
since $G$ has no $2P_{5}$, the edge must be $v_{4}v_{6}$. In this case,
$v_{4},v_{5},v_{6}$ are cut vertices which contradicts our assumption. So
there is no edge between $\\{v_{1},v_{2},v_{3},v_{4}\\}$ and
$\\{v_{6},v_{7},v_{8},v_{9}\\}$. Therefore, $v_{5}$ is the only cut vertex,
$G-v_{5}$ has at least three components and each component has a hamiltonian
path starting at $v_{5}$, a contradiction.

Next we may assume that $v$ is the only cut vertex of $G$,
$B_{1},\ldots,B_{t}$ are all blocks and $t\geq 3$, and each $B_{i}$ contains a
hamiltonian path starting at $v$. Obviously, $|B_{i}|\geq\delta_{F}+1$ for
$1\leq i\leq t$. Assume that $|B_{1}|\geq\cdots\geq|B_{t}|$ and let $Q_{i}$ be
a hamiltonian path starting at $v$ in $B_{i}$ for $1\leq i\leq t$. Because
$|Q_{i}|\geq\delta_{F}+1$, $|Q_{1}-v|\geq\delta_{F}$ and $Q_{2}\cup Q_{3}$ is
a path of order at least $2\delta_{F}+1$. Since $G$ is $F$-free, by Lemma 7,
we have $|Q_{1}-v|\leq\delta_{F}+1$.

If $|Q_{1}-v|=\delta_{F}$, then by Lemma 6,
$F\in\\{5P_{5},2P_{\ell},P_{\ell+1}\cup P_{\ell}\\}$, or
$F\in\\{P_{\ell+2}\cup P_{\ell},2P_{\ell}\cup P_{2}\\}$ with $\ell$ odd. In
this case, noting that $\delta(G)\geq\delta_{F}$, we can see that
$G=K_{1}+tK_{\delta_{F}}$ with $t\geq 4$(because $n\geq 2|F|$). Note that $G$
contains $F$ if $F=5P_{5}$, hence $F\in\\{2P_{\ell},P_{\ell+1}\cup
P_{\ell}\\}$, or $F\in\\{P_{\ell+2}\cup P_{\ell},2P_{\ell}\cup P_{2}\\}$ with
$\ell$ odd. If $|Q_{1}-v|=\delta_{F}+1$, then by Lemma 7 and the fact that
$P_{2\delta_{F}+1}\cup P_{\delta_{F}+1}$ has no $F$, we have $F=2P_{\ell}$ and
$\ell$ is odd. In this case, it is not difficult to deduce that $G\subseteq
K_{1}+(t_{1}K_{\ell-1}\cup t_{2}K_{\ell-2})$.

Case 2. $G$ contains at least three end blocks and two cut vertices.

By the assumption, we may assume that $B_{1},B_{2},B_{3}$ are three end blocks
and $b_{i}\in B_{i}$ is the only cut vertex of $B_{i}$ with $b_{1}\not=b_{2}$.
Let $Q_{i}$ be the longest path in $B_{i}$ starting at $b_{i}$ for $i=1,2,3$,
$P$ a longest path connecting $b_{1},b_{2}$ and $P^{\prime}$ a path with
endpoints $b_{3}$ and $v$ such that $V(P)\cap V(P^{\prime})=\\{v\\}$. Because
$\delta(G)\geq\delta_{F}$, we have $|Q_{i}|\geq\delta_{F}+1$. Thus, it is not
difficult to see that the subgraph consisting of the paths
$Q_{1},Q_{2},Q_{3},P,P^{\prime}$ contains $P_{2\delta_{F}+1}\cup
P_{\delta_{F}+1}$ which is $F$-free. By Lemma 7, $F=2P_{\ell}$ and $\ell$ is
odd.

Let $S=V(B_{1})\cup V(B_{2})\cup V(P)$. It is clear that $N_{S}(u)\subseteq
V(P)$ for any $u\in V(G)\backslash S$.

Obviously, $\delta(G)\geq\delta_{F}=\ell-2$. Since $G$ is $F$-free, we have
$|Q_{1}\cup P\cup Q_{2}|\leq 2\ell-1$, and hence $|P|\leq 3$. Note that
$|P|\geq 2$, we have $|P|=2$ or 3.

If $|P|=2$, then $P=b_{1}b_{2}$. For any $u\in V(G)\backslash S$, by the
maximality of $P$, $d_{P}(u)\leq 1$, which means
$N_{S}(u)\subseteq\\{b_{1}\\}$ or $N_{S}(u)\subseteq\\{b_{2}\\}$. If
$u_{1},u_{2}\in V(G)\backslash S$ with $u_{1}b_{1},u_{2}b_{2}\in E(G)$, then
$G$ contains $2P_{\ell}$, and hence we may assume that
$N_{S}(u)\subseteq\\{b_{1}\\}$. In this case, $G-b_{1}$ contains at least $3$
components and each one is $P_{\ell}$-free for otherwise $G$ has $2P_{\ell}$.
Since $\delta(G)\geq\ell-2$, each component contains $\ell-2$ or $\ell-1$
vertices, $B_{2}=K_{\ell-1}$ and $G-V(B_{2})\subseteq
K_{1}+(s_{1}K_{\ell-1}\cup s_{2}K_{\ell-2})$. Of course, $G\subseteq
K_{1}+(t_{1}K_{\ell-1}\cup t_{2}K_{\ell-2})$.

If $|P|=3$, then $N(u)\cap\\{b_{1},b_{2}\\}=\emptyset$ for otherwise $G$ has
$2P_{\ell}$. Thus, $P=b_{1}vb_{2}$ and $N_{S}(u)\subseteq\\{v\\}$ for any
$u\in V(G)\backslash S$. If $|B_{1}|\geq\ell$, then since
$\delta(B_{1})\geq\ell-3$, by Lemma 1 we have $p(B_{1})\geq
min\\{|B_{1}|,2(\ell-3)+1\\}\geq\ell$, that is, $B_{1}$ contains a $P_{\ell}$.
Note that $Q_{2}\cup\\{v\\}$ also contains a $P_{\ell}$, a contradiction.
Thus, $|B_{1}|=\ell-1$. By symmetry, $|B_{2}|=\ell-1$. Since
$\delta(G)\geq\ell-1$, we have $B_{1}=B_{2}=K_{\ell-1}$. By the assumption,
$V(G)\backslash S\not=\emptyset$. Let $G^{\prime}=G-B_{1}-B_{2}$, then
$G^{\prime}$ is connected. By the arguments before,
$d_{G^{\prime}}(v)\geq\delta_{F}-2$ and $d_{G^{\prime}}(u)\geq\delta_{F}$ for
any $u\in V(G^{\prime})\backslash\\{v\\}$.

If $b_{1}b_{2}\in E(G)$, then $Q_{1}\cup\\{b_{1}b_{2}\\}\cup Q_{2}$ contains a
$P_{\ell}$. If $G’-v$ contains only one component, then $G’$ contains a path
of order at least

$min\\{|G-B_{1}-B_{2}|,2\delta_{F}-1\\}\geq min\\{|G-B_{1}-B_{2}|,\ell\\}.$

Because $G^{\prime}$ is $P_{\ell}$-free, we have
$\ell-1\geq|G^{\prime}|\geq\delta_{F}+1=\ell-1$, and so
$G^{\prime}=K_{\ell-1}$. In this case, $G$ consists of $B_{1},B_{2},B_{3}$ and
$b_{1}b_{2}b_{3}$ is a triangle, which is impossible since
$|G|=3(\ell-1)<2|F|$. If $G’-v$ contains two components, we can find a
$P_{\ell}$ easily, a contradiction.

If $b_{1}b_{2}\not\in E(G)$, then $G-v$ contains at least $3$ components
including $B_{1},B_{2}$, and each one is $P_{\ell}$-free, for otherwise $G$
has $2P_{\ell}$. Since $\delta(G)\geq\ell-2$, each component of $G-v$ contains
$\ell-1$ or $\ell-2$ vertices. This is to say $G^{\prime}\subseteq
K_{1}+(s_{1}K_{\ell-1}\cup s_{2}K_{\ell-2})$, and so $G\subseteq
K_{1}+(t_{1}K_{\ell-1}\cup t_{2}K_{\ell-2})$.

The proof of Theorem 5 is complete. $\hfill\blacksquare$

##  4 Generalized Turán number

In this section, we determine the generalized Turán number $ex(n,K_{s},F)$. We
will use a strategy to reduce the problem to graphs with large minimum degree.
For a fixed $F$, we define a process of $G$, called
$\left(\delta_{F}-1\right)$-$disintegration$ as follows: for $j=n$, let
$G^{n}=G$, and for $j<n$, let $G^{j}$ be obtained from $G^{j+1}$ by deleting a
vertex of degree less than $\delta_{F}$ in $G^{j+1}$ if such a vertex exists.
The process terminates at $G^{m}$ when $\delta(G^{m})\geq\delta_{F}$ or $m=0$.
We call $G^{m}$ the $\delta_{F}$-$core$ of $G$.

Before starting to prove Theorem 4, as a preparation, we first discuss the
properties of the $\delta_{F}$-core of $F$-free graphs for some special $F$.

###### Claim 1

Let $F$ be a linear forest and $G$ an $F$-free graph with
$\delta(G)\geq\delta_{F}$ and components $G_{1},G_{2},\ldots,G_{c}$, where
$|G_{1}|\geq\cdots\geq|G_{c}|$. Then $G=G_{1}\cup(c-1)K_{\ell-1}$ if
$F=2P_{\ell}$ and $\ell$ is odd, and $|G_{i}|\leq|F|-1$ for all $1\leq i\leq
c$ otherwise.

_Proof_. If $F=2P_{\ell}$ and $\ell$ is odd, then $\delta_{F}=\ell-2$. Since
$p(G_{i})\geq min\\{|G_{i}|,2\ell-3\\}$ by Lemma 1, we have
$|G_{i}|\leq\ell-1$ which implies $G_{i}=K_{\ell-1}$ for $2\leq i\leq c$, and
hence the result follows.

If $F\not=2P_{\ell}$ with $\ell$ odd, we suppose $|G_{1}|\geq|F|$. Since
$G_{1}$ contains no hamiltonian path, then $\alpha(G)\geq 3$ by Lemma 2.
Obviously,

$\sigma_{3}(G_{1})\geq 3\delta_{F}\geq 3(\delta_{F^{\prime}}+1),$

where $F^{\prime}=F-P_{\ell_{k}}$. By Lemma 3, we have $F^{\prime}\subseteq
G_{1}$. Since $G_{2}$ contains $P_{\ell_{k}}$, we can see that $G$ contains
$F$, a contradiction. $\hfill\blacksquare$

###### Claim 2

Let $F\in\\{3P_{5},2P_{\ell},P_{\ell}\cup P_{\ell+1},P_{\ell}\cup
P_{\ell+2},2P_{\ell}\cup P_{2}\\}$ and $s\leq\delta_{F}+1$.
If $F\not=2P_{\ell}$ with $\ell$ odd or $F\not=3P_{5}$, then

$\mathcal{N}_{s}(G_{F}(t(\ell-1)+1))\geq\mathcal{N}_{s}(K_{1}+tK_{\ell-1}).$

If $F=3P_{5}$, then

$\mathcal{N}_{s}(G_{F}(4t+2))>\mathcal{N}_{s}(K_{2}+tK_{4}).$

If $F=2P_{\ell}$ with $\ell$ odd, $2\leq s\leq\ell-2$ and $m\geq
5{\binom{|F|-1}{s}}/{\binom{\delta_{F}}{s-1}}$, then

$\mathcal{N}_{s}(G_{F}(m))=max\\{\mathcal{N}_{s}(G)~{}|~{}G~{}is~{}F\text{-}free,~{}|G|=m~{}and~{}\delta(G)\geq\delta_{F}\\}.$

_Proof_. If $F\not=2P_{\ell}$ with $\ell$ odd or $F\not=3P_{5}$, then
$\delta_{F}=\ell-1$. Thus we have

$\begin{split}\mathcal{N}_{s}(G_{F}(t(\ell-1)+1))-\mathcal{N}_{s}(K_{1}+tK_{\ell-1})&\geq\binom{\ell-1}{s}+(m-\ell+1)\binom{\ell-1}{s-1}-t\binom{\ell}{s}\\\
&=(t-1)\left(\ell-1-\frac{\ell}{s}\right)\binom{\ell-1}{s-1}\geq
0,\end{split}$

that is,
$\mathcal{N}_{s}(G_{F}(t(\ell-1)+1))\geq\mathcal{N}_{s}(K_{1}+tK_{\ell-1})$.

If $F=3P_{5}$, then $\delta_{F}=5$. Thus we have

$\begin{split}\mathcal{N}_{s}(G_{F}(4t+2))-\mathcal{N}_{s}(K_{2}+tK_{4})&\geq\binom{5}{s}+(4t-3)\binom{5}{s-1}+\binom{5}{s-2}-t\binom{6}{s}\\\
&=\big{(}(2s/3-1)(t-1)-s/2\big{)}\binom{6}{s}+\binom{5}{s-2}>0.\end{split}$

If $F=2P_{\ell}$ with $\ell$ odd, then $\delta_{F}=\ell-2$. Since $m\geq
5{\binom{|F|-1}{s}}/{\binom{\delta_{F}}{s-1}}$ and $G$ is $F$-free, by Theorem
5 and Claim 1, we have $G\in\\{G_{F}(m),K_{1}+(t_{1}K_{\ell-1}\cup
t_{2}K_{\ell-2}),G_{1}\cup tK_{\ell-1}\\}$, where $G_{1}$ is the largest
component of $G$ with $|G_{1}|=n_{1}$ if $G$ is disconnected. We first show
$\mathcal{N}_{s}\big{(}G_{F}(m)\big{)}\geq\mathcal{N}_{s}\big{(}K_{1}+(t_{1}K_{\ell-1}\cup
t_{2}K_{\ell-2})\big{)}$ when $m=1+t_{1}(\ell-1)+t_{2}(\ell-2)$. Noting that
$s\geq 2$ and $m\geq 5{\binom{|F|-1}{s}}/{\binom{\delta_{F}}{s-1}}$ implying
$t_{1}+t_{2}\geq 5$, we have

$\begin{split}&\mathcal{N}_{s}\big{(}G_{F}(m)\big{)}-\mathcal{N}_{s}\big{(}K_{1}+(t_{1}K_{\ell-1}\cup
t_{2}K_{\ell-2})\big{)}\\\
=&\binom{\ell-2}{s-2}+(m-\ell+2)\binom{\ell-2}{s-1}+\binom{\ell-2}{s}-t_{2}\binom{\ell-1}{s}-t_{1}\binom{\ell}{s}\\\
=&\binom{\ell-2}{s-2}+\biggl{(}t_{1}(\ell-1)+(t_{2}-1)(\ell-2)+1\biggr{)}\binom{\ell-2}{s-1}+\frac{\ell-s-1}{s}\binom{\ell-2}{s-1}\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-t_{1}\frac{\ell(\ell-1)}{s(\ell-s)}\binom{\ell-2}{s-1}-t_{2}\frac{\ell-1}{s}\binom{\ell-2}{s-1}\\\
=&\binom{\ell-2}{s-2}+\biggl{(}t_{1}(\ell-1)\left(1-\frac{\ell}{s(\ell-s)}\right)+(t_{2}-1)\left(\ell-2-\frac{\ell-1}{s}\right)\biggr{)}\binom{\ell-2}{s-1}\\\
\geq&\binom{\ell-2}{s-2}+\biggl{(}t_{1}(\ell-1)\frac{\ell-4}{2(\ell-2)}+(t_{2}-1)\frac{\ell-3}{2}\biggr{)}\binom{\ell-2}{s-1}>0.\end{split}$

Next we show $\mathcal{N}_{s}(G_{F}(m))\geq\mathcal{N}_{s}(G_{1}\cup
tK_{\ell-1})$ when $m=n_{1}+t(\ell-1)$. If $n_{1}\geq 2|F|$, then
$G_{1}\subseteq G_{F}(n_{1})$ by Lemma 9. Thus we have

$\begin{split}\mathcal{N}_{s}\left(G_{F}(m)\right)-\mathcal{N}_{s}(G_{1}\cup
tK_{\ell-1})\geq&\mathcal{N}_{s}(G_{F}(m))-\mathcal{N}_{s}(G_{F}(n_{1}))-t\binom{\ell-1}{s}\\\
=&t(\ell-1)\binom{\ell-2}{s-1}-t\binom{\ell-1}{s}>0.\end{split}$

If $\ell-1\leq n_{1}\leq 2|F|-1$, then noting that $G_{1}$ is
$P_{2\ell}$-free, by Theorem 3 we have

$\mathcal{N}_{s}(G_{1})\leq\frac{n_{1}}{2\ell-1}\binom{2\ell-1}{s}.$

Thus, note that $m\geq 5{\binom{|F|-1}{s}}/{\binom{\delta_{F}}{s-1}}$, that
is, $m\geq 5{\binom{2\ell-1}{s}}/{\binom{\ell-2}{s-1}}$, we have

$\begin{split}&\mathcal{N}_{s}(G_{F}(m))-\mathcal{N}_{s}(G_{1}\cup
tK_{\ell-1})\\\
\geq&(m-\ell+2)\binom{\ell-2}{s-1}+\binom{\ell-2}{s}+\binom{\ell-2}{s-2}-\frac{n_{1}}{2\ell-1}\binom{2\ell-1}{s}-t\binom{\ell-1}{s}\\\
=&\biggl{(}m-\ell+2\biggr{)}\binom{\ell-2}{s-1}+\frac{\ell-s-1}{s}\binom{\ell-2}{s-1}+\frac{s-1}{\ell-s}\binom{\ell-2}{s-1}\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\frac{n_{1}}{2\ell-1}\binom{2\ell-1}{s}-t\frac{\ell-1}{s}\binom{\ell-2}{s-1}\\\
=&\biggl{(}(m-\ell+1)\left(1-\frac{1}{s}\right)+\frac{n_{1}}{s}+\frac{s-1}{\ell-s}\biggr{)}\binom{\ell-2}{s-1}-\frac{n_{1}}{2\ell-1}\binom{2\ell-1}{s}\\\
>&\frac{m}{2}\binom{\ell-2}{s-1}-\frac{n_{1}}{2\ell-1}\binom{2\ell-1}{s}>0.\end{split}$

Therefore, the latter part holds. $\hfill\blacksquare$

Proof of Theorem 4. Let $F=P_{\ell_{1}}\cup\cdots\cup P_{\ell_{k}}$ be a
linear forest with $k\geq 2,\ell_{i}\not=3$ and $G$ an $F$-free graph of order
$n$ with $\mathcal{N}_{s}(G)=ex(n,K_{s},F)$ and $s\leq\delta_{F}+1$.
Obviously,

$\displaystyle\mathcal{N}_{s}(G)\geq
max\\{\mathcal{N}_{s}(G_{F}(n)),ex(n,K_{s},P_{\ell_{1}})\\}.$ (4.1)

Applying $\left(\delta_{F}-1\right)$-$disintegration$ to $G$ and let $G^{m}$
be the $\delta_{F}$-$core$ of $G$. If $m=0$, then since one vertex is deleted
at each step during the process of $(\delta_{F}-1)$-$disintegration$, that
destroys at most $\binom{\delta_{F}-1}{s-1}$ copies of $K_{s}$ in $G$, we have

$\begin{split}\mathcal{N}_{s}(G)&\leq\binom{\delta_{F}}{s}+\left(n-\delta_{F}\right)\binom{\delta_{F}-1}{s-1}\\\
&<\binom{\delta_{F}}{s}+\left(n-\delta_{F}\right)\binom{\delta_{F}}{s-1}\leq\mathcal{N}_{s}(G_{F}(n)),\end{split}$

which contradicts (4.1). This implies that $\delta(G^{m})\geq\delta_{F}$ and
$m\geq\delta_{F}+1$.

By the definitions of $\left(\delta_{F}-1\right)$-$disintegration$, we have

$\mathcal{N}_{s}\left(G^{j+1}\right)-\mathcal{N}_{s}\left(G^{j}\right)\leq\binom{\delta_{F}-1}{s-1}.$
(4.2)

If $m\leq j\leq n-1$, then

$\mathcal{N}_{s}(G_{F}(j+1))-\mathcal{N}_{s}(G_{F}(j))\geq\binom{\delta_{F}}{s-1}.$
(4.3)

Recall that $s\leq\delta_{F}+1$, by (4.2) and (4.3), we have

$\mathcal{N}_{s}\left(G^{j}\right)-\mathcal{N}_{s}\left(G_{F}(j)\right)\geq\mathcal{N}_{s}\left(G^{j+1}\right)-\mathcal{N}_{s}(G_{F}(j+1))+1,$

and so

$\mathcal{N}_{s}\left(G^{m}\right)-\mathcal{N}_{s}\left(G_{F}(m)\right)\geq\mathcal{N}_{s}\left(G^{n}\right)-\mathcal{N}_{s}(G_{F}(n))+(n-m),$

which implies that

$\mathcal{N}_{s}(G^{m})\geq n-m+\mathcal{N}_{s}(G_{F}(m))\geq n-\delta_{F}.$

On the other hand, since $G^{m}$ has no path of order $|F|$, by Theorem 3, we
have

$\mathcal{N}_{s}(G^{m})\leq\frac{m}{|F|-1}\binom{|F|-1}{s}.$

Thus, note that $n\geq
5\binom{|F|-1}{s}^{2}/\left({(|F|-1)\binom{\delta_{F}}{s-1}}\right)+\delta_{F}$,
we have

$m\geq\left(n-\delta_{F}\right)\left(|F|-1\right)\left/\binom{|F|-1}{s}\right.\geq
5\binom{|F|-1}{s}\left/{\binom{\delta_{F}}{s-1}}\right.,$ (4.4)

which means the core $G^{m}$ contains indeed at least
$5\binom{|F|-1}{s}/{\binom{\delta_{F}}{s-1}}$ vertices.

If $G^{m}$ is disconnected, we assume that the components of $G^{m}$ are
$G_{1}^{m},G_{2}^{m},...,G_{c}^{m}$ with
$|G_{1}^{m}|\geq|G_{2}^{m}|\geq\cdots\geq|G_{c}^{m}|$. (i) $F\neq 2P_{\ell}$
with $\ell$ odd. By (4.4), we have $m\geq 3|F|$. If $G^{m}$ is connected, then
by Theorem 5, $G^{m}\in\\{G_{F}(m),K_{1}+tK_{\ell-1},K_{2}+tK_{4}\\}$. By
Claim 2, we can see

$\begin{split}\mathcal{N}_{s}(G)&\leq\mathcal{N}_{s}(G^{m})+(n-m)\binom{\delta_{F}-1}{s-1}\leq\mathcal{N}_{s}(G_{F}(m))+(n-m)\binom{\delta_{F}-1}{s-1}\\\
&\leq\mathcal{N}_{s}(G_{F}(m))+(n-m)\binom{\delta_{F}}{s-1}\leq\mathcal{N}_{s}(G_{F}(n)),\end{split}$

with equality holds if and only if $n=m$ and $G=G_{F}(n)$.

If $G^{m}$ is disconnected, then since $m\geq 3|F|$, we have $c\geq 4$ by
Claim 1. If two of the components of $G^{m}$ are contained in one component of
$G$, then we can choose $G_{i}^{m},G_{j}^{m},G_{k}^{m}$ such that
$G_{i}^{m},G_{j}^{m}$ are contained in one component of $G-G_{k}^{m}$. Because
$\delta(G^{m})\geq\delta_{F}$, we can see that $G-G_{k}^{m}$ contains
$P_{2\delta_{F}+2}$ and $G_{k}^{m}$ contains $P_{\delta_{F}+1}$, which implies
$G$ contains $F$ by Lemma 7, a contradiction. Thus, we may assume
$G_{1},G_{2},...,G_{s}$ are components of $G$ and $G^{m}_{i}\subseteq
G_{i},1\leq i\leq c\leq s$. In this case, each $G_{i}$ contains a
$P_{\delta_{F}+1}$. If $G$ contains a $P_{\ell_{1}}$, say
$P_{\ell_{1}}\subseteq G_{1}$, then since $c\geq 4$, $G$ contains
$P_{\ell_{1}}\cup 3P_{\delta_{F}+1}$. Assume that $x,y$ are the endpoints of
two distinct $P_{\delta_{F}+1}$. Then $P_{\delta_{F}+1}\cup\\{xy\\}\cup
P_{\delta_{F}+1}$ is a path of oder $2\delta_{F}+2$, and so
$3P_{\delta_{F}+1}\cup\\{xy\\}$ contains $F$ by Lemma 7. If $F$ uses $xy$ to
form some $P_{\ell_{i}}$, then replace this $P_{\ell_{i}}$ with a
$P_{\ell_{i}}$ from $G_{1}$, we find an $F$ in $G$, a contradiction. This is
to say that $G$ is $P_{\ell_{1}}$-free and so $\mathcal{N}_{s}(G)\leq
ex(n,K_{s},P_{\ell_{1}})$. Therefore, we can obtain that
$\mathcal{N}_{s}(G)\leq
max\\{\mathcal{N}_{s}(G_{F}(n)),ex(n,K_{s},P_{\ell_{1}})\\}$. Combining this
with (4.1), we get that
$\mathcal{N}_{s}(G)=max\\{\mathcal{N}_{s}(G_{F}(n)),ex(n,K_{s},P_{\ell_{1}})\\}$.

(ii) $F=2P_{\ell}$ and $\ell$ is odd. By Theorem 4 and Claim 1, $G^{m}$ is
$G_{F}(m)$ or $K_{1}+(t_{1}K_{\ell-2}\cup t_{2}K_{\ell-1})$ or $G^{m}_{1}\cup
tK_{\ell-1}$. If $s\leq\ell-2$, then because $m\geq
5\binom{|F|-1}{s}/{\binom{\delta_{F}}{s-1}}$, by Claim 2, we have

$\begin{split}\mathcal{N}_{s}(G)&\leq\mathcal{N}_{s}(G^{m})+(n-m)\binom{\delta_{F}-1}{s-1}\\\
&\leq\mathcal{N}_{s}(G_{F}(m))+(n-m)\binom{\delta_{F}}{s-1}\leq\mathcal{N}_{s}(G_{F}(n)).\end{split}$

At last, if $s=\delta_{F}+1=\ell-1$, recall that each time we delete a vertex
during the process of $(\delta_{F}-1)$-$disintegration$, no copy of $K_{s}$ is
destroyed. Therefore, $\mathcal{N}_{s}(G)=\mathcal{N}_{s}(G^{m})$. It is easy
to show that $K_{1}+(tK_{\ell-1}\cup K_{r})$ contains the most copies of
$K_{s}$ among all kinds of $\delta_{F}$-core when $n$ is large, where
$n-1\equiv r$ (mod $\ell-1$), that is
$\mathcal{N}_{s}(G)=\lfloor\frac{n-1}{\ell-1}\rfloor\ell+1_{r=\ell-2}$.

Combining (i) and (ii), we complete the proof. $\hfill\blacksquare$

Acknowledgements

This research was supported by NSFC under grant numbers 11871270 and 11931006.

## References

  * [1] N. Alon and C. Shikhelman, Many $T$ copies in $H$-free graphs, _J. Combin. Theory Ser. B_ 121(2016), 146-172.
  * [2] B. Bollobás and E. Győri, Pentagons vs. triangles, _Discrete Math._ 308(2008), 4332-4336.
  * [3] N. Bushaw and N. Kettle, Turán numbers of multiple paths and equibipartite forests, _Combin. Probab. Comput._ 20(2011), 837-853.
  * [4] Z. Chase, The maximum number of triangles in a graph of given maximum degree, _Adv. Com._ (2020), paper No.10, 5 pp,
  * [5] Y.J. Chen, F. Tian and B. Wei, Degree sums and disjoint paths with prescribed orders in graphs, _Adv. Math.(China)_ 32(2003), 81-90.
  * [6] V. Chvátal and P. Erdős, A note on hamiltonian circuits, _Discrete Math._ 2(1972), 111-113.
  * [7] M.Z. Chen and X.D. Zhang, Erdős-Gallai stability theorem for linear forests, _Discrete Math._ 342(2019), 904-916.
  * [8] G.A. Dirac, Some theorems on abstract graphs, _Proc. London Math. Soc._ 2(1952), 69-81.
  * [9] P. Erdős, On the number of complete subgraphs contained in certain graphs, _Magy. Tud. Akad. Mat. Kut. Intéz. Közl._ 7(1962), 459-474.
  * [10] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, _Acta Math. Acad. Sci. Hungar._ 10(1959), 337-356.
  * [11] Y. Egawa and K. Ota, Vertex-disjoint paths in graphs, _Ars Combin._ 61(2001), 23-31.
  * [12] P. Erdős and M. Simonovits, A limit theorem in graph theory, _Studia Scientiarum Mathematicarum Hungarica_ 1(1966), 51-57.
  * [13] P. Erdős and A.H. Stone, On the structure of linear graphs, _Bulletin of the American Mathematical Society_ 52(1946), 1087-1091.
  * [14] D. Gerbner, E. Győri, A. Methuku and M. Vizer, Generalized Turán problems for even cycles, _J. Combin. Theory Ser. B_ 145(2020), 169-213.
  * [15] D. Gerbner, A. Methuku and M. Vizer, Generalized Turán problems for disjoint copies of graphs, _Discrete Math._ 342(2019), 3130-3141.
  * [16] A. Grzesik, On the maximum number of five-cycles in a triangle-free graph, _J. Combin. Theory Ser. B_ 102(2012), 1061-1066.
  * [17] E. Győri, J. Pach and M. Simonovits, On the maximal number of certain subgraphs in $K_{r}$-free graphs, _Graph Combin._ 7(1991), 31-37.
  * [18] H. Hatami, J. Hladký, D. Král, S. Norine and A. Razborov, On the number of Pentagons in triangle-free graphs, _J. Combin. Theory Ser. A_ 120(2013), 722-732.
  * [19] R. Johansson, An El-Zahár type condition ensuring path-factors, _J. Graph Theory_ 28 (1998), 39-42.
  * [20] R. Luo, The maximum number of cliques in graphs without long cycles, _J. Combin. Theory Ser. B_ 128(2017), 219-226.
  * [21] B. Lidický, H. Liu and C. Palmer, On the Turán number of forests, _Electron. J. Combin._ 20(2013), Paper 62, 13 pages.
  * [22] J. Ma and Y. Qiu, Some sharp results on the generalized Turán numbers, _European J. Combin._ 84(2020), 103026, 16 pages.
  * [23] B. Ning and X. Peng, Extensions of the Erdős-Gallai theorem and Luo’s theorem, _Combin. Probab. Comput._ 29(2020), 128-136.
  * [24] A. Saito, Long paths, long cycles, and their relative length _J. Graph Theory_ 30(1999), 91-99.
  * [25] P. Turán, On an extremal problem in graph theory, _Mat. Fiz. Lapok_ 48(1941), 436-452.
  * [26] J. Wang, The shifting method and generalized Turán number of matchings, _European J. Combin._ 85(2020), 7 pp.
  * [27] L.T. Yuan and X.D. Zhang, Turán numbers for disjoint paths, _J. Graph Theory_ https://doi.org/10.1002/jgt.22710.
  * [28] A. Zykov, On some properties of linear complexes, _Mat. Sbornik N. S._ 24(1949), 163-188.