# Extremal graphs for edge blow-up of graphs††thanks: This work is supported
by the National Natural Science Foundation of China (No. 11901554) and Science
and Technology Commission of Shanghai Municipality (No. 18dz2271000,
19jc1420100)

Long-Tu Yuan
School of Mathematical Sciences and Shanghai Key Laboratory of PMMP
East China Normal University
500 Dongchuan Road, Shanghai, 200240, P.R. China
Email<EMAIL_ADDRESS>

###### Abstract

Given a graph $H$ and an integer $p$, the edge blow-up $H^{p+1}$ of $H$ is the
graph obtained from replacing each edge in $H$ by a clique of order $p+1$
where the new vertices of the cliques are all distinct. The Turán numbers for
edge blow-up of matchings were first studied by Erdős and Moon. In this paper,
we determine the range of the Turán numbers for edge blow-up of all bipartite
graphs. Moreover, we characterize the extremal graphs for edge blow-up of all
non-bipartite graphs. Our results also extend several known results, including
the Turán numbers for edge blow-up of stars, paths and cycles. The method we
used can also be applied to find a family of counter-examples to a conjecture
posed by Keevash and Sudakov in 2004 concerning the maximum number of edges
not contained in any monochromatic copy of $H$ in a $2$-edge-coloring of
$K_{n}$.

Key words: Turán number; edge blow-up; Keevash-Sudakov conjecture.

AMS Classifications: 05C35; 05D99.

##  1 Introduction

Given a family of graphs $\mathcal{H}$, we say a graph $G$ is
$\mathcal{H}$-free ($H$-free if $\mathcal{H}=\\{H\\}$) if $G$ does not contain
any copy of $H\in\mathcal{H}$ as a subgraph. The Turán number of a family of
graphs $\mathcal{H}$, denote as ex$(n,\mathcal{H})$, is the maximum number of
edges in an $\mathcal{H}$-free graph $G$ of order $n$. Denote by
EX$(n,\mathcal{H})$ the set of $\mathcal{H}$-free graphs on $n$ vertices with
ex$(n,\mathcal{H})$ edges and call a graph in EX$(n,\mathcal{H})$ an extremal
graph for $H$. We simply use ex$(n,H)$ and EX$(n,H)$ instead of
ex$(n,\\{H\\})$ and EX$(n,\\{H\\})$ respectively if $\mathcal{H}=\\{H\\}$.

In 1941, Turán [24] proved that the unique extremal graph without containing a
clique on $p+1\geq 3$ vertices is the complete $p$-partite graph on $n$
vertices which is balanced, in that the partite sizes are as equal as
possible. This balanced complete $p$-partite graph on $n$ vertices is the
Turán graph $T_{p}(n)$ and let $t_{p}(n)=e(T_{p}(n))$ be the number of edges
of $T_{p}(n)$.

Later, in 1946, Erdős and Stone [6] proved the following well-known theorem.

######  Theorem 1.1 (Erdős and Stone [6])

For all integers $p\geq 2$ and $N\geq 1$, and every $\epsilon>0$, there exists
an integer $n_{0}$ such that every graph with $n\geq n_{0}$ vertices and at
least

$t_{p-1}(n)+\epsilon n^{2}$

edges contains $T_{p}(Np)$ as a subgraph.

Let $\mathcal{F}$ be a family of graphs, the subchromatic number
$p(\mathcal{F})$ of $\mathcal{F}$ is defined by

$p(\mathcal{F})=\min\\{\chi(F):F\in\mathcal{F}\\}-1,$

where $\chi(F)$ is the chromatic number of $F$. The classical Erdős-Stone-
Simonovits theorem [6, 9] states that

$\mbox{ex}(n,\mathcal{F})=\left(1-\frac{1}{p(\mathcal{F})}\right){n\choose
2}+o(n^{2}).$

If $\mathcal{F}$ contains a bipartite graph, then $p(\mathcal{F})=1$ and
ex$(n,\mathcal{F})=o(n^{2})$. For this degenerate (bipartite) extremal graph
problem, there is an excellent survey by Füredi and Simonovits [11]. Let $G$
be a graph with $\chi(G)=p+1\geq 3$. If there is an edge $e$ such that
$\chi(G-\\{e\\})=p$, then we say that $G$ is edge-critical and $e$ is a
critical edge. The Turán numbers of edge-critical graphs are determined when
$n$ is sufficiently large. In 1968, Simonovits [21] proved the following
theorem.

######  Theorem 1.2 (Simonovits [21])

Let $G$ be an edge-critical graph with $\chi(G)=p+1\geq 3$. Then there exists
an $n_{0}$ such that if $n>n_{0}$ then $T_{p}(n)$ is the unique extremal graph
for $G$ on $n$ vertices.

Although the Turán numbers of non-bipartite graphs are asymptotically
determined by Erdős-Stone-Simonovits theorem, it is a challenge to determine
the exact Turán functions for many non-bipartite graphs, There are only few
graphs whose Turán numbers were determined exactly, including edge-critical
graphs [21] and some specific graphs [4, 23, 27].

Given a graph $H$ and an integer $p\geq 2$, the edge blow-up of $H$, denoted
by $H^{p+1}$, is the graph obtained from replacing each edge in $H$ by a
clique of order $p+1$ where the new vertices of the cliques are all distinct.
The subscript in the case of graphs indicates the number of vertices, e.g.,
denote by $P_{k}$ a path on $k$ vertices, $S_{k}$ a star on $k$ vertices and
$K_{n_{1},\ldots,n_{p}}$ the complete $p$-partite graph with partite sizes
$n_{1},\ldots,n_{p}$. A matching in $G$ is a set of edges from $E(G)$, no two
of which share a common vertex, and the matching number of $G$, denoted by
$\nu(G)$, is the number of edges in a maximum matching. Accordingly, we denote
by $M_{2k}$ the disjoint union of $k$ disjoint copies of edges.

In 1959, Erdős and Gallai [7] characterized the extremal graphs for $M_{2k}$.
Later, Erdős [8] studied the extremal graphs for $M^{3}_{2k}$ and Moon [19]
determined the extremal graphs for $M^{p+1}_{2k}$ for infinitely many values
of $n$ when $p\geq 3$. After almost forty years, Erdős, Füredi, Gould, and
Gunderson [10] determined the Turán number of $S^{3}_{k+1}$ and Chen, Gould,
Pfender, and Wei [4] determined the Turán number of $S^{p+1}_{k+1}$ for
general $p\geq 3$. Glebov [13] determined the extremal graphs for edge blow-up
of paths. Later, Liu [16] generalized Glebov’s result to edge blow-up of
paths, cycles and a class of trees. Very recently, Wang, Hou, Liu, and Ma [25]
determined the Turán numbers for edge blow-up of a large family of trees. For
other extremal results concerning edge blow-up of specific graphs, we refer
the interested readers to [14, 20, 28]. We will characterize the extremal
graphs for edge blow-up of non-partite graphs and estimate the Turán numbers
of edge blow-up of bipartite graphs. Our main theorems need some definitions,
so we state them in Section 2. As applications of our main theorems, see
Sections 3 and 6, we determine the Turán numbers of edge blow-up of complete
bipartite graphs and complete graphs.

###### Theorem 1.3

Let $K_{t}$ be the complete graph on $t$ vertices. For $p\geq t+1$ and
sufficiently large $n$, we have

$\emph{ex}(n,K_{t}^{p+1})={t-1\choose 2}\left(n-{t-1\choose
2}\right)+t_{p}\left(n-{t-1\choose 2}\right).$

Moreover, the extremal graphs are characterized.

###### Theorem 1.4

Let $K_{s,t}$ be the complete bipartite graph with $s\leq t$. For $p\geq 3$
and sufficiently large $n$, we have

$\emph{ex}(n,K_{s,t}^{p+1})={s-1\choose 2}+(s-1)(n-s+1)+t_{p}(n-s+1)+p(s,t),$

where $p(s,t)$ is a constant depending on $s$ and $t$.

For a given graph $H$, let $g(n,H)$ denote the maximum number of edges not
contained in any monochromatic copy of $H$ in a $2$-edge-coloring of $K_{n}$.
If we color the edges of an extremal $n$-vertex graph for $H$ red and color
the other edges blue, then we can see that $g(n,H)\geq\mbox{ex}(n,H)$ for any
$H$ and $n$. In 2004, Keevash and Sudakov showed in [15] that this lower bound
is tight for sufficiently large $n$ if $H$ is edge-critical or a cycle of
length four. Hence, they posed the following conjecture.

######  Conjecture 1.5 (Keevash and Sudakov [15])

Let $H$ be a given graph. If $n$ is sufficiently large, then

$g(n,H)=\emph{ex}(n,H).$

Ma [18] and Liu-Pikhurko-Sharifzadeh [17] confirmed Conjecture 1.5 for a large
family of bipartite graphs. Our method also works for this problem. In Section
6, we will show that Conjecture 1.5 does not hold for a large family of non-
bipartite graphs. In particular, we prove the following theorem.

###### Theorem 1.6

Let $n$ be sufficiently large. Then

$g(n,K_{t}^{p+1})=\emph{ex}(n,K_{t}^{p+1})+{{t-1\choose 2}\choose 2}.$

The organisation of this paper is as follows. In Section 2, we introduce some
definitions and state our main theorems. In Section 3, we present several
corollaries of our main theorems. In Section 4, we present several lemmas. In
Section 5, we will prove Theorems 2.3 and 2.4. In Section 6, we deduce some
results about graphs without containing a matching with given sizes. In
Section 7, we will discuss more applications of our method.

##  2 Main theorems

Let $K_{t}$ be a complete graph on $t$ vertices and $\overline{K}_{t}$ be the
complement of $K_{t}$. Denote by $G\cup H$ the vertex-disjoint union of $G$
and $H$ and by $k\cdot G$ the vertex-disjoint union of $k$ copies of $G$.
Denote by $G+H$ the graph obtained from $G\cup H$ by adding edges between each
vertex of $G$ and each vertex of $H$.

In order to study the Turán numbers of non-bipartite graphs, Simonovits [22]
defined the decomposition family $\mathcal{M}(\mathcal{F})$ of a family of
graphs $\mathcal{F}$.

######  Definition 2.1 (Simonovits [22])

_Given a family of graphs $\mathcal{F}$ with $p(\mathcal{F})=p\geq 2$, let
$\mathcal{M}(\mathcal{F})$ be the family of minimal111If
$M\in\mathcal{M}(\mathcal{F})$, then
$M^{\prime}\notin\mathcal{M}(\mathcal{F}$) where $M^{\prime}$ is a proper
subgraph of $M$. graphs $M$ satisfying the following: there exist an
$F\in\mathcal{F}$ and a constant $t$ depending on $F$ such that
$F\subseteq(M\cup\overline{K}_{t})+T_{p-1}((p-1)t)$. We call
$\mathcal{M}(\mathcal{F})$ the decomposition family of $\mathcal{F}$._

Thus, a graph $M$ is in $\mathcal{M}(\mathcal{F})$ if the graph obtained from
putting a copy of $M$ (but not any of its proper subgraphs) into a class of a
large $T_{p}(n)$ contains some $F\in\mathcal{F}$. If $F\in\mathcal{F}$ with
chromatic number $p+1$, then $F\subseteq T_{p+1}((p+1)s)$ for some $s\geq 1$.
Therefore the decomposition family $\mathcal{M}(\mathcal{F})$ always contains
some bipartite graphs222It is possible that the decomposition family contains
non-bipartite graphs.. A deep theorem of Simonovits [22] shows that if the
decomposition family $\mathcal{M}(\mathcal{F})$ contains a linear forest333A
linear forest is a graph consisting of paths., then the extremal graphs for
$\mathcal{F}$ have very simple and symmetric structure (the theorem is quite
complicated, we refer the interested readers to [22] for more information).
Our theorems focus on graphs $F$ such that $\mathcal{M}(F)$ contains a
matching (a matching is a linear forest). Hence, our theorems are refinements
of Simonovits’ theorem in a certain sense. The main purpose of this paper is
to determine the exact Turán numbers for new families of graphs.

To state our main theorems and related results, we need the following result.
Let $\Delta(G)$ be the maximum degree of $G$. Define
$f(\nu,\Delta)=\max\\{e(G):\nu(G)\leq\nu,\Delta(G)\leq\Delta\\}$. In 1972,
Abbott, Hanson, and Sauer [1] determined $f(k-1,k-1)$. Later Chvátal and
Hanson [5] proved the following theorem.

######  Theorem 2.2 (Chvátal and Hanson [5])

For every $\nu\geq 1$ and $\Delta\geq 1$,

$f(\nu,\Delta)=\nu\Delta+\left\lfloor\frac{\Delta}{2}\right\rfloor\left\lfloor\frac{\nu}{\lceil\Delta/2\rceil}\right\rfloor\leq\nu\Delta+\nu.$

In 2009, basing on Gallai’s Lemma [12], Balachandran and Khare [2] gave a more
‘structural’ proof of this result. Hence they gave a simple characterization
of all the cases where the extremal graph is unique. Denote by
$\mathcal{E}_{\nu,\Delta}$ the set of the extremal graphs in Theorem 2.2.

$E_{\nu,\Delta}$$Q_{s-1}$$T_{p}(n-s+1)$Figure 1: a graph of
$\mathcal{H}(n,p,s,\nu,\Delta,\mathcal{B})$

Let $H(n,p,s)=K_{s-1}+T_{p}(n-s+1)$ and
$H^{\prime}(n,p,s)=\overline{K}_{s-1}+T_{p}(n-s+1)$. Let
$h(n,p,s)=e(H(n,p,s))$ and $h^{\prime}(n,p,s)=e(H^{\prime}(n,p,s))$. For a set
of graphs $\mathcal{B}$, denote by $\mathcal{H}(n,p,s,\nu,\Delta,\mathcal{B})$
(Figure 1) the set of graphs which are obtained by taking an
$H^{\prime}(n,p,s)$, putting a copy of
$E_{\nu,\Delta}\in\mathcal{E}_{\nu,\Delta}$ in one class of $T_{p}(n-s+1)$ and
putting a copy of $Q_{s-1}\in\mbox{EX}(s-1,\mathcal{B})$ in
$\overline{K}_{s-1}$. As before, we use $\mathcal{H}(n,p,s,\nu,\Delta,B)$ to
denote $\mathcal{H}(n,p,s,\nu,\Delta,\\{B\\})$ if $\mathcal{B}=\\{B\\}$.

A covering of a graph is a set of vertices which together meet all edges of
the graph. An independent set of a graph is a set of vertices no two of which
are adjacent. Similarly, an independent covering of a bipartite graph is an
independent set which meets all edges of the bipartite graph. The minimum
number of vertices in a covering of a graph $F$ is called the covering number
of $F$ and is denoted by $\beta(F)$.

Let $\mathcal{F}$ be a family of graphs containing at least one bipartite
graph. We need the following three parameters: $q(\mathcal{F})$,
$\mathcal{S}(\mathcal{F})$, $\mathcal{B}(\mathcal{F})$, of $\mathcal{F}$ to
describe our main theorems.

The independent covering number $q(\mathcal{F})$ of $\mathcal{F}$ is defined
by

$q(\mathcal{F})=\min\\{q(F):F\in\mathcal{F}\mbox{ is bipartite}\\},$

where $q(F)$ is the minimum order of an independent covering of $F$.

The independent covering family $\mathcal{S}(\mathcal{F})$ of $\mathcal{F}$ is
the family of independent coverings of bipartite graphs $F\in\mathcal{F}$ with
order $q(\mathcal{F})$.

The subgraph covering family $\mathcal{B}(\mathcal{F})$ of $\mathcal{F}$ is
the set of subgraphs (regardless of isolated vertices) of $F\in\mathcal{F}$
which are induced by a covering of $F$ with order at most $q(\mathcal{F})-1$
(if $\beta(F)\geq q(\mathcal{F})$ for each $F\in\mathcal{F}$, then we set
$\mathcal{B}(\mathcal{F})=\\{K_{q}\\}$).

In the rest of this paper, given a graph $G$, let $G^{p+1}$ be the edge blow-
up of $G$ with $p\geq\chi(G)+1$, $\mathcal{M}=\mathcal{M}(G^{p+1})$,
$\mathcal{B}=\mathcal{B}(\mathcal{M})$ and $q=q(\mathcal{M})$. Let
$k=\min\\{d_{H_{S}}(x):x\in S,S\in\mathcal{S}(\mathcal{M})\\}$, where
$H_{S}\in\mathcal{M}$ contains $S$. For any connected bipartite graph $G$, let
$A$ and $B$ be its two color classes with $|A|\leq|B|$. Moreover, if $G$ is
disconnected, we always partition $G$ into $A\cup B$ such that $|A|$ is as
small as possible. We will establish the following theorems.

###### Theorem 2.3

Let $G$ be a bipartite graph and $n$ be sufficiently large. For $p\geq 3$, we
have the following:
(i). If $q=|A|$, then

$h^{\prime}(n,p,q)+\emph{ex}(q-1,\mathcal{B})\leq\emph{ex}(n,G^{p+1})\leq
h(n,p,q)+f(k-1,k-1).$ (1)

Furthermore, both bounds are best possible.
(ii). If $q<|A|$, then

$\emph{ex}(n,G^{p+1})=h^{\prime}(n,p,q)+\emph{ex}(q-1,\mathcal{B}).$

Moreover, the graphs in $\mathcal{H}(n,p,q,0,0,\mathcal{B})$ are the only
extremal graphs for $G^{p+1}$.

###### Theorem 2.4

Let $G$ be a non-bipartite graph and $n$ be sufficiently large. For
$p\geq\chi(G)+1$, we have

$\emph{ex}(n,G^{p+1})=h^{\prime}(n,p,q)+\emph{ex}(q-1,\mathcal{B}).$

Moreover, the graphs in $\mathcal{H}(n,p,q,0,0,\mathcal{B})$ are the only
extremal graphs for $G^{p+1}$.

##  3 Corollaries

For a given graph $H$ with $\chi(H)=p+1\geq 3$, Erdős-Stone-Simonovits theorem
tells us that the structure of the extremal graphs for $H$ are close to the
Turán graph $T_{p}(n)$. More precisely, any extremal graph for $H$ can be
obtained from $T_{p}(n)$ by adding and deleting at most $o(n^{2})$ edges. The
decomposition family of a forbidden graph $H$ often helps us to determine the
fine structure of the extremal graphs for $H$. Hence, we need the following
lemmas concerning the extremal graphs of the decomposition family of
$G^{p+1}$.

Given a graph $H$, a vertex split on some vertex $v\in V(H)$ is defined as
follows: replace $v$ by an independent set of size $d(v)$ in which each vertex
is adjacent to exactly one distinct vertex in $N_{H}(v)$. Denote by
$\mathcal{H}(H)$ the family of graphs that can be obtained from $H$ by
applying a vertex split on some $U\subseteq V(H)$. Obviously each graph in
$\mathcal{H}(H)$ has $e(H)$ number of edges. Note that $U$ could be empty,
therefore $H\in\mathcal{H}(H)$. For example, $\mathcal{H}(P_{k+1})$ is the
family of all linear forests with $k$ edges and $\mathcal{H}(C_{k})$ consists
of $C_{k}$ and all linear forests with $k$ edges.

The following lemma is proved in [16].

######  Lemma 3.1 (Liu [16])

Given a graph $G$ with $2\leq\chi(G)\leq p-1$, we have
$\mathcal{M}=\mathcal{H}(G)$, in particular, a matching of size $e(G)$ is in
$\mathcal{M}$. In particular, if $H\in\mathcal{M}$, then after splitting any
vertex set of $H$, the resulting graph also belongs to $\mathcal{M}$.

Let $K_{n_{1},\ldots,n_{p}}$ be the complete $p$-partite graph with class
sizes $n_{1},\ldots,n_{p}$. Denote by $K_{n_{1},\ldots,n_{p}}(n,H_{n_{1}})$
the graph obtained by embedding $H_{n_{1}}$ into the class of
$K_{n_{1},\ldots,n_{p}}$ with size $n_{1}$.

###### Proposition 3.2

Let $F_{n_{1}}$ be an extremal graph for $\mathcal{M}$ on $n_{1}$ vertices.
Then $K_{n_{1},\ldots,n_{p}}(n,F_{n_{1}})$ does not contain $G^{p+1}$ as a
subgraph.

Proof. Proposition 3.2 follows directly from definition of decomposition
family. $\square$

Theorem 2.3 implies the results of Erdős [8], Moon, [19] and Simonovits [21]
for edge-blow up of matchings, results of Erdős, Füredi, Gould, and Gunderson
[10] and Chen, Gould, Pfender, and Wei [4] for edge-blow up of stars and
results of Glebov [13] and Liu [16] for edge-blow up of paths and even cycles.
Theorems 2.4 implies the result of Liu [16] for edge-blow up of odd cycles. We
state those results as corollaries of Theorems 2.3 and 2.4. In the following
of this section, we will deduce the above results from our main theorems by
applying Lemma 3.1.

######  Corollary 3.3 (Erdős [8], Moon [19] and Simonovits [21])

Let $G=M_{2t}$ be a matching on $2t$ vertices and $p\geq 2$. Then for
sufficiently large $n$, we have

$\emph{ex}(n,M_{2t}^{p+1})=h(n,p,t).$

Moreover, $H(n,p,t)$ is the unique extremal graph for $M_{2t}^{p+1}$.

Proof. Clearly, we have $\mathcal{M}=\\{M_{2t}\\}$. Applying Theorem 2.3 with
$q=|A|=t$, $k=1$, $p\geq 3$, and $\mathcal{B}=\\{K_{q}\\}$, the lower and
upper bounds of (1) are the same. Thus we have
$\mbox{ex}(n,M_{2t}^{p+1})=h(n,p,t).$ The proof of Corollary 3.3 for $p\geq 3$
is complete. Since $\mathcal{M}$ contains only a matching $M_{2t}$, the proof
of Theorem 2.3 implies Corollary 3.3 for $p=2$ (see Corollary 7.1). $\square$

######  Corollary 3.4 (Erdős, et al. [10] and Chen, et al. [4])

Let $G=S_{t+1}$ be a star on $t+1$ vertices and $p\geq 2$. Then, for
sufficiently large $n$, we have

$\emph{ex}(n,S_{t+1}^{p+1})=h(n,p,1)+f(t-1,t-1).$

Moreover, the extremal graphs are characterized.

Proof. By Lemma 3.1, we have $\mathcal{M}=\\{M_{2t},S_{t+1}\\}$. Note that the
graphs in $\mathcal{H}(n,p,1,k-1,k-1,K_{2})$ does not contain $S_{t+1}^{p+1}$
as a subgraph (by Proposition 3.2). Applying Theorem 2.3(i) with $q=|A|=1$,
$k=t$, $p\geq 3$, and $\mathcal{B}=\\{K_{1}\\}$, we have
ex$(n,S_{t+1}^{p+1})\leq h(n,p,1)+f(t-1,t-1)$. The proof of Corollary 3.4 for
$p\geq 3$ is complete. Note that $\mathcal{M}$ contains a matching. The proof
of Theorem 2.3 implies444We omit the proof, since it is essentially the same
as the proof of Theorem 2.3. Corollary 3.4 for $p=2$. $\square$

######  Corollary 3.5 (Glebov [13] and Liu [16])

Let $G=P_{t}$ be a path on $t$ vertices and $p\geq 3$. Then, for sufficiently
large $n$, we have

$\emph{ex}(n,P_{t}^{p+1})=h\left(n,p,\left\lfloor\frac{t}{2}\right\rfloor\right)+i,$

where $i=1$ when $t$ is odd and $i=0$ when $t$ is even.

Proof. By Lemma 3.1, $\mathcal{M}$ consists of all linear forests with $t-1$
edges. For a linear forest $F$ in $\mathcal{M}$ consisting of paths
$P_{t_{1}}$, $P_{t_{2}}$, $\ldots$, $P_{t_{\ell}}$, each covering of $F$ has
at least $\sum_{i=1}^{\ell}\lfloor t_{i}/2\rfloor\geq(t-1)/2$ vertices. If $t$
is even, then $k=1$. Since $(q-1)S_{3}\cup S_{2}\in\mathcal{M}$ and the
minimum non-independent coverings of linear forests with $t-1$ edges is
$t/2+1$, applying Theorem 2.3(i) with $q=|A|=t/2$, $k=1$, $p\geq 3$, and
$\mathcal{B}=\\{K_{q}\\}$, the lower and upper bounds of (1) are the same.
Assume that $t$ is odd. Then $k=2$. Note that the graphs in
$\mathcal{H}(n,p,q,1,1,K_{q})$ do not contain a copy of $P_{t}^{p+1}$, where
$q=|A|=\lfloor t/2\rfloor$. It follows from the upper bound of (1) that
$\mbox{ex}(n,P_{t}^{p+1})=h(n,p,q)+1$. Thus, the proof of Corollary 3.5 is
complete. $\square$

######  Corollary 3.6 (Liu [16])

Let $G=C_{t}$ be a cycle on $t$ vertices. Then, for sufficiently large $n$, we
have the following:
(a) If $t$ is even and $p\geq 3$, then

$\emph{ex}(n,C_{t}^{p+1})=h\left(n,p,\left\lfloor\frac{t}{2}\right\rfloor\right)+1.$

(b) If $t$ is odd and $p\geq 4$, then

$\emph{ex}(n,C_{t}^{p+1})=h\left(n,p,\left\lceil\frac{t}{2}\right\rceil\right).$

Proof. By Lemma 3.1, $\mathcal{M}$ consists of all linear forests with $t$
edges and the cycle of length $t$. Let $t$ be even. Since the graphs in
$\mathcal{H}(n,p,t/2,1,1,K_{t/2})$ do not contain $C_{t}^{p+1}$ as a subgraph
(by Proposition 3.2), applying Theorem 2.3(i) with $q=|A|=t/2$, $k=2$,
$p\geq\chi(C_{t})+1=3$ and $\mathcal{B}=\\{K_{q}\\}$, the lower bound and the
upper bound of Theorem 2.3 are the same. The proof of Corollary 3.6(a) is
complete. Let $t$ be odd. Then Corollary 3.6(b) follows from Theorem 2.4 with
$q=\lceil t/2\rceil$, $\mathcal{B}=\\{K_{q}\\}$, and $p\geq\chi(C_{t})+1=4$.
$\square$

Proof of Theorem 1.3:
Proof. Let $G=K_{t}$. Denote by $S_{k,k}$ the graph on $2k$ vertices obtained
by taking two copies of $S_{k}$ and joining the centers of them with a new
edge. Since each bipartite graph in $\mathcal{M}$ is obtained by splitting at
least $t-2$ vertices of $K_{t}$, we have $q=t-1+{t-2\choose 2}={t-1\choose
2}+1$ (the graph $F\in\mathcal{M}(K_{t}^{p+1})$ consisting of $S_{t-1,t-1}$
and ${t-2\choose 2}$ independent edges) and $\mathcal{B}=\\{K_{2}\\}$ (the
edge joining the centers of $S_{t-1}$ in $S_{t-1,t-1}$ of $F$). Applying
Theorem 2.4, we have $\mbox{ex}(n,K_{t}^{p+1})={t-1\choose
2}\left(n-{t-1\choose 2}\right)+t_{p}\left(n-{t-1\choose 2}\right).$ Moreover,
the extremal graphs are characterized. The proof of Theorem 1.3 is complete.
$\square$

The proof of Theorem 1.4 needs more efforts, so we move it to Section 6.

##  4 Several technical lemmas

The following simple propositions help us to determine the extremal graphs for
$\mathcal{M}$.

###### Proposition 4.1

Let $F$ be a bipartite graph. Then we have $q(F)=|A|.$

Proof. Since $A$ is an independent covering of $F$, we have $q(F)\leq|A|$.
Suppose $F$ is connected. Then each independent covering of $F$ must contain
either all the vertices of $A$ or all the vertices of $B$. Indeed, assume that
$A_{1}\subsetneq A$, $B_{1}\subsetneq B$ are two non-empty vertex sets and
$A_{1}\cup B_{1}$ is an independent covering of $F$. Let $A_{2}=A-A_{1}$ and
$B_{2}=B-B_{1}$. Since $F$ is connected and $A_{1}\cup B_{1}$ is an
independent set, there is some edge between $A_{2}$ and $B_{2}$, contradicting
that $A_{1}\cup B_{1}$ is a covering of $F$. Hence we have $q(F)=|A|$. If $F$
is disconnected, the result follows easily by studying each component of $F$
(recall that we always partition $F$ with $|A|$ as small as possible). The
proof is complete. $\square$

We need the following proposition to determine the extremal graphs for
$G^{p+1}$ when $k=1$ (recall definitions of $\mathcal{S}(\mathcal{M})$, $q$
and $k$).

###### Proposition 4.2

If there is an independent covering $S\in\mathcal{S}(\mathcal{M})$ obtained by
splitting some vertices in $G$, then $k=1$. Moreover, if $G$ is bipartite with
$q<|A|$ or $G$ is non-bipartite, then $k=1$.

Proof. Let $H_{S}\in\mathcal{M}$ be a bipartite graph with $q(H_{S})=q$ and
$S$ be an independent covering of $H_{S}$ with order $q$. Since each vertex in
$S$ obtained by splitting a vertex in $G$ has degree one in $H_{S}$, by
definition of $k$, we have $k=1$. Let $G$ be a bipartite graph with $q<|A|$.
Then there is an $x\in S$ which is obtained by splitting a vertex in $G$.
Otherwise, by Proposition 4.1, we have $q=|A|$, a contradiction. Thus, we have
$k=1$. Let $G$ be a non-bipartite graph. Then, there is an $x\in S$ which is
obtained by splitting a vertex in $G$. Otherwise, $G$ has an independent
covering and hence is bipartite, a contradiction. The result follows similarly
as before. $\square$

Now, we will study the Turán number of the decomposition family of $G^{p+1}$
which helps us to determine the Turán number of $G^{p+1}$.

###### Lemma 4.3

Suppose that $n$ is sufficiently large. Then we have the following.
(a). If $G$ is bipartite with $q=|A|$, then

$h^{\prime}(n,1,q)+\emph{ex}(q-1,\mathcal{B})\leq\emph{ex}(n,\mathcal{M})\leq
h(n,1,q)+f(k-1,k-1).$ (2)

Furthermore, both bounds are best possible.
(b). If $G$ is bipartite with $q<|A|$ or $G$ is non-bipartite, then

$\emph{ex}(n,\mathcal{M})=h^{\prime}(n,1,q)+\emph{ex}(q-1,\mathcal{B}).$ (3)

Moreover, the extremal graphs are characterized.

Proof. Let $H\in\mathcal{M}$ be a bipartite graph with an independent covering
$S\in\mathcal{S}(\mathcal{M})$ and a vertex $x\in S$ such that $d_{H}(x)=k$.
Let $G^{\prime}$ be an extremal graph for $\mathcal{M}$.
$(a)$. Assume that $G$ is bipartite and $q=|A|$. For the upper bound of (2),
suppose that

$e(G^{\prime})\geq h(n,1,q)+f(k-1,k-1)={q-1\choose
2}+(q-1)(n-q+1)+f(k-1,k-1).$ (4)

First, there are at most $q-1$ vertices of $G^{\prime}$ with degree at least
$e(G)+q$. Otherwise, by Lemma 3.1, $G^{\prime}$ contains a copy of
$H_{1}\in\mathcal{M}$ ($H_{1}$ is a star forest555A star forest is a graph
consisting of stars.) obtained from $H$ by splitting all vertices of $H-S$, a
contradiction. Suppose that the number of vertices of $G^{\prime}$ with degree
at least $e(G)+q$ is less than $q-1$. By Lemma 3.1, $\mathcal{M}$ contains a
matching with size $e(G)$. Since $n$ is sufficiently large and $f(\Delta,\nu)$
is a constant depending on $\Delta$ and $\nu$, we have

$\displaystyle e(G^{\prime})$ $\displaystyle\leq(q-2)(n-1)+f(e(G)+q,e(G))$
$\displaystyle<{q-1\choose 2}+(q-1)(n-q+1)+f(k-1,k-1),$

contradicting (4). Thus, there are exactly $q-1$ vertices of $G^{\prime}$ with
degree at least $e(G)+q$. Let $X$ be set of vertices with degree at least
$e(G)$ and $\widetilde{G}=G^{\prime}-X$. Then $\widetilde{G}$ contains neither
$S_{k+1}$ nor $M_{2k}$ as a subgraph. Otherwise, by Lemma 3.1, $G^{\prime}$
contains either a copy of $H_{1}\in\mathcal{M}$ or a copy of
$H_{2}\in\mathcal{M}$ obtained from $H$ by splitting all vertices of $H-S$ and
the vertex $x$. Hence, we have $e(\widetilde{G})\leq f(k-1,k-1)$. Then by (4),
we have that $e(\widetilde{G})=f(k-1,k-1)$ and each vertex in $X$ has degree
$n-1$. Moreover, it follows from Theorem 2.2 that
$\widetilde{G}\in\mathcal{E}_{k-1,k-1}$. Thus we have
$G^{\prime}\in\mathcal{H}(n,1,q,k-1,k-1,K_{q})$ or
$e(G^{\prime})<h(n,1,q)+f(k-1,k-1)$. The lower bound of (2) follows from the
fact that the graphs in $\mathcal{H}(n,1,q,0,0,\mathcal{B})$ do not contain
any graph in $\mathcal{M}$ as a subgraph (by definitions of $q$ and
$\mathcal{B}$).

$(b)$. Now let $G$ be a bipartite graph666The graph $G=F_{t,t}$ obtained from
by taking two copies of $S_{t}$ with $t\geq 4$ and joining two leaves in
deferent $S_{t}$’s satisfies that $q=3<t=|A|$ (splitting the vertices of the
added edge). with $q<|A|$ or be a non-partite graph. Thus, it follows from the
definitions of $q$ and $\mathcal{B}$ that each graph in
$\mathcal{H}(n,1,q,0,0,\mathcal{B})$ does not contain any graph in
$\mathcal{M}$ as a subgraph. Thus we have $e(G^{\prime})\geq
h^{\prime}(n,1,q)+\mbox{ex}(q-1,\mathcal{B})$. Let $X$ be the set vertices of
$G^{\prime}$ with degree at least $e(G)$ and $\widetilde{G}=G^{\prime}-X$.
Similarly as the previous arguments, we have $|X|=q-1$. It follows from
Proposition 4.2 that $k=1$. Hence, we have $e(\widetilde{G})=0$. So we have
$e(G^{\prime})=h^{\prime}(n,1,q)+\mbox{ex}(q-1,\mathcal{B})$. Moreover, the
extremal graphs are in $\mathcal{H}(n,1,q,0,0,\mathcal{B})$. $\square$

###### Lemma 4.4

Let $F$ be a graph with a partition of vertices into $p+1$ parts
$V(F)=V_{0}\cup V_{1}\cup V_{2}\cup\ldots\cup V_{p}$ satisfying the following:
(1) there exist $V^{\prime}_{1}\subseteq V_{1}$, $\ldots$,
$V^{\prime}_{p}\subseteq V_{p}$ such that $F[V^{\prime}_{1}\cup\ldots\cup
V^{\prime}_{p}]=T_{p}(ap)$;
(2) $|V_{0}|=q-1$ and each vertex of $V_{0}$ is adjacent to each vertex of
$T_{p}(ap)$;
(3) each vertex of $V^{\prime\prime}_{i}=V_{i}\setminus V^{\prime}_{i}$ is
adjacent to each vertex of $V^{\prime}_{j\neq i}$ for $i\in[p]$.
Let $G$ be a bipartite graph with $q=|A|$ and $|V(G)|\leq a$. If there exist
an $i\in[p]$ and a $y\in V^{\prime\prime}_{i}$ such that one of the following
holds:
(a) $\sum_{j\neq i}\nu(F[V^{\prime\prime}_{j}])\geq k$;
(b) $\Delta(F[V^{\prime\prime}_{i}])\geq k$;
(c) $d_{F[V^{\prime\prime}_{i}]}(y)+\sum_{j\neq i}\nu(F[N(y)\cap
V^{\prime\prime}_{j}])\geq k$,
then $F$ contains a copy of $G^{p+1}$.

Proof. If $k=1$, then the lemma holds trivially by definition of $k$ and
definition of decomposition family (the graph $H$ consisting of $q-1$ stars
and an isolated edges belongs to $\mathcal{M}$ and $F[V_{0}\cup
V_{i^{\prime}}]$ contains a copy of $H$, where $F[V_{i^{\prime}}]$ contains an
edge). Assume that $k\geq 2$, i.e., there is no independent covering
$S\in\mathcal{S}(\mathcal{M})$ obtained by splitting some vertices in $G$.
Then it follows from Proposition 4.1 that $q=|A|$ and hence
$k=\min\\{d_{G}(x):x\in A\mbox{ or }x\in G\mbox{ when }|A|=|B|\\}$. Let
$V^{\prime}_{i}=\\{x_{i,1},x_{i,2}\ldots,x_{i,a}\\}$ for $i\in[p]$ and
$F^{\prime}=F-V_{0}$. Since each vertex of $V_{0}$ is adjacent to each vertex
of $V^{\prime}_{i}$, $|V_{0}|=q-1=|A|-1$, and $a\geq|V(G)|$, it is enough to
show that $F^{\prime}$ contains a copy of $S^{p+1}_{k+1}$ with the following
property: each copy of $K_{p}$ in $S^{p+1}_{k+1}$ without containing the
center777The center of $S^{p+1}_{k+1}$ is the vertex in $S^{p+1}_{k+1}$ with
degree $pk$. of $S^{p+1}_{k+1}$ contains at least one vertex in
$\cup_{i=1}^{p}V^{\prime}_{i}$ . In fact, we map the center of $S^{p+1}_{k+1}$
and $V_{0}$ to either $A$ of $G^{p+1}$, or $B$ of $G^{p+1}$ when there is a
vertex $x\in B$ with degree $k$ with $|A|=|B|$. We will prove the lemma in the
following three cases.

Case 1. $\sum_{j\neq i}\nu(F[V^{\prime\prime}_{j}])\geq k$. Without loss of
generality, let $\sum_{j\neq 1}\nu(F[V^{\prime\prime}_{j}])\geq k$. Let
$\\{y_{1}z_{1},y_{2}z_{2},\ldots,y_{k}z_{k}\\}$ be a matching in $\cup_{j\neq
1}F[V^{\prime\prime}_{j}]$ and

$F_{s}=F[x_{1,1},y_{s},z_{s},x_{2,s},x_{3,s},\ldots,x_{p,s}]$

for $s\in[k]$. Clearly, we have $F_{s}=K_{p+1}$ for $s\in[k]$ and
$V(F_{s})\cap V(F_{t})=\\{x_{1,1}\\}$ for $s\neq t$. Since
$x_{2,s}\in\cup_{i=1}^{p}V^{\prime}_{i}$ for $s\in[k]$, we obtain the desired
copy of $S^{p+1}_{k+1}$, the result follows.

Case 2. $\Delta(F[V^{\prime\prime}_{i}])\geq k$. Without loss of generality,
let $\Delta(F[V^{\prime\prime}_{1}])\geq k$, $y$ be a vertex in
$V^{\prime\prime}_{1}$ with $d_{F[V^{\prime\prime}_{1}]}(y)\geq k$ and
$x_{1},x_{2},\ldots,x_{k}$ be the neighbours of $y$ in $V^{\prime\prime}_{1}$.
Let

$F_{s}=F[y,x_{s},x_{2,s},x_{3,s},\ldots,x_{p,s}]$

for $s\in[k]$. Clearly we have $F_{s}=K_{p+1}$ for $s\in[k]$ and $V(F_{s})\cap
V(F_{t})=\\{y\\}$ for $s\neq t$. Since
$x_{2,s}\in\cup_{i=1}^{p}V^{\prime}_{i}$ for $s\in[k]$, we obtain the desired
copy of $S^{p+1}_{k+1}$, the result follows.

Case 3. $d_{F[V^{\prime\prime}_{i}]}(y)+\sum_{j\neq i}\nu(F[N(y)\cap
V^{\prime\prime}_{j}])\geq k$. Without loss of generality, let
$d_{F[V^{\prime\prime}_{1}]}(y)+\sum_{j\neq 1}\nu(F[N(y)\cap
V^{\prime\prime}_{j}])\geq k$. Let $d_{F[V^{\prime\prime}_{1}]}(y)=t<k$,
$x_{1},x_{2},\ldots,x_{t}$ be the neighbours of $y$ in
$F[V^{\prime\prime}_{1}]$ and $\\{y_{t+1}z_{t+1},\ldots,y_{k}z_{k}\\}$ be a
matching in $\bigcup_{j\neq 1}F[N(y)\cap V^{\prime\prime}_{j}]$. Let

$F_{s}=\left\\{\begin{array}[]{ll}\
F[y,x_{s},x_{2,s},x_{3,s},\ldots,x_{p,s}]&\mbox{ for }s=1,2,\ldots,t,\\\
F[y,y_{s},z_{s},x_{2,s},x_{3,s},\ldots,x_{p,s}]&\mbox{ for
}s=t+1,t+2,\ldots,k.\end{array}\right.$

Clearly, we have $F_{s}=K_{p+1}$ for $s\in[k]$ and $V(F_{s})\cap
V(F_{t})=\\{y\\}$ for $s\neq t$. Since
$x_{2,s}\in\cup_{i=1}^{p}V^{\prime}_{i}$ for $s\in[k]$, we obtain the desired
copy of $S^{p+1}_{k+1}$, the result follows. $\square$

Let $G$ be a graph with a partition of the vertices into $p\geq 2$ non-empty
parts

$V(G)=V_{1}\cup V_{2}\cup\ldots\cup V_{p}.$

Let $G_{i}=G[V_{i}]$ for $i=1,2,\ldots,p$ and define

$G_{cr}=(V(G),\\{v_{i}v_{j}:v_{i}\in V_{i},v_{j}\in V_{j},i\neq j\\}),$

where “cr” denotes “crossing”. The following lemma is proved in [4].

######  Lemma 4.5 (Chen, Gould, Pfender, and Wei [4])

Let $G$ be a graph on $n$ vertices. Suppose $G$ is partitioned as above so
that

$\displaystyle\sum_{j\neq i}\nu(G[V_{j}])\leq k-1\mbox{ and
}\Delta(G[V_{i}])\leq k-1;$ (5) $\displaystyle d_{G[V_{i}]}(x)+\sum_{j\neq
i}\nu(G[N(x)\cap V_{j}])\leq k-1.$ (6)

are satisfied for all $i$ and for all $x\in V_{i}$. If $G$ does not contain a
copy of $S_{k+1}^{p+1}$, then

$\displaystyle\sum_{i=1}^{p}|E(G_{i})|-\left(\sum_{1\leq i<j\leq
p}|V_{i}||V_{j}|-|E(G_{cr})|\right)\leq f(k-1,k-1).$ (7)

Moreover, if the equality holds, then

$\displaystyle\sum_{1\leq i<j\leq
p}|V_{i}||V_{j}|=|E(G_{cr})|,\;e(G[V_{i}])=f(k-1,k-1),\;e(G[V_{\ell\neq
i}])=0,$ (8)

and $G[V_{i}]\in\mathcal{E}_{k-1,k-1}$ for some $i\in\\{1,\ldots,p\\}$.
Furthermore, if $\sum_{j\neq i}|E(G_{j})|\geq 1$ for each
$i\in\\{1,\ldots,p\\}$, i.e., at least two of $E(G_{1}),\ldots,E(G_{p})$ are
non-empty, then

$\displaystyle\sum_{i=1}^{p}|E(G_{i})|-\left(\sum_{1\leq i<j\leq
p}|V_{i}||V_{j}|-|E(G_{cr})|\right)\leq k^{2}-2k.$ (9)

Remark. By analyzing the proof of Lemma 4.5, it is not difficult to see that
if the equality holds in (7), then (8) is satisfied and
$G[V_{i}]\in\mathcal{E}_{k-1,k-1}$ (See Lemma 2.7 in [27]). The proof of Lemma
4.5 also implies the last assertion of Lemma 4.5 (See the last sentence of the
proof of Lemma 3.2 in [4]).

In 1968, Simonovits [21] introduced the so-called progressive induction which
is similar to the mathematical induction and Euclidean algorithm and combined
from them in a certain sense.

######  Lemma 4.6 (Simonovits [21])

Let $\mathfrak{U}=\cup_{i=1}^{\infty}\mathfrak{U}_{i}$ be a set of given
elements, such that $\mathfrak{U}_{i}$ are disjoint finite subsets of
$\mathfrak{U}$. Let $B$ be a condition or property defined on $\mathfrak{U}$
(i.e. the elements of $\mathfrak{U}$ may satisfy or not satisfy $B$). Let
$\phi(a)$ be a function defined on $\mathfrak{U}$ such that $\phi(a)$ is a
non-negative integer and
(a) if $a$ satisfies $B$, then $\phi(a)=0$.
(b) there is an $M_{0}$ such that if $n>M_{0}$ and $a\in\mathfrak{U}_{n}$ then
either $a$ satisfies $B$ or there exist an $n^{\prime}$ and an $a^{\prime}$
such that

$\frac{n}{2}<n^{\prime}<n,a^{\prime}\in\mathfrak{U}_{n^{\prime}}\mbox{ and
}\phi(a)<\phi(a^{\prime}).$

Then there exists an $n_{0}$ such that if $n>n_{0}$, every
$a\in\mathfrak{U}_{n}$ satisfies $B$.

Remark. In our problems, $\mathfrak{U}_{n}$ is a set of extremal graphs for
$G^{p+1}$ on $n$ vertices, $B$ is the property defined on $\mathfrak{U}$
concerning the number of edges or the structure of graphs.

##  5 Proof of the main theorems

Proof of Theorem 2.3 (i):
Proof. We will prove that, for sufficiently large $n$,

$h^{\prime}(n,p,q)+\mbox{ex}(q-1,\mathcal{B})\leq\mbox{ex}(n,G^{p+1})\leq
h(n,p,q)+f(k-1,k-1)$ (10)

and if $\mbox{ex}(n,G^{p+1})=h(n,p,q)+f(k-1,k-1)$, then
$\mbox{EX}(n,G^{p+1})=\mathcal{H}(n,p,q,k-1,k-1,K_{q})$. Lemma 4.3 together
with Proposition 3.2 implies the lower bound of (10). We will prove the upper
bound of (10) by Lemma 4.6. Suppose $F_{n}$ is an extremal graph for
$G^{p+1}$. It will be shown that, if $n$ is sufficiently large, then
$e(F_{n})\leq h(n,p,q)+f(k-1,k-1).$ Let
$H_{n}\in\mathcal{H}(n,p,q,k-1,k-1,K_{q})$. Clearly,
$e(H_{n})=h(n,p,q)+f(k-1,k-1)$. If $e(F_{n})<e(H_{n})$, then we are done. Let

$e(F_{n})\geq e(H_{n}).$ (11)

Let $\mathfrak{U}_{n}$ be the set of extremal graphs for $G^{p+1}$ on $n$
vertices and $B$ be the property defined on $\mathfrak{U}$ stating that
$e(F_{n})\leq e(H_{n})$ and equality holds if and only if
$F_{n}\in\mathcal{H}(n,p,q,k-1,k-1,K_{q})$. Define
$\phi(F_{n})=\max\\{e(F_{n})-e(H_{n}),0\\}$. Then $\phi(F_{n})$ is a non-
negative integer. According to Lemma 4.6, it is enough to show that if
$e(F_{n})\geq e(H_{n})$, then either
$F_{n}\in\mathcal{H}(n,p,q,k-1,k-1,K_{q})$ or there exists an
$n^{\prime}\in(n/2,n)$ such that $\phi(F_{n^{\prime}})>\phi(F_{n})$ when $n$
is sufficiently large.

Now, we will find a subgraph of $F_{n}$ satisfying the conditions of Lemma
4.5. Since $e(H_{n})\geq t_{p}(n)$, by Theorem 1.1 and (11), there is an
$n_{1}$ such that if $n>n_{1}$, then $F_{n}$ contains $T_{p}(n_{2}p)$ ($n_{2}$
is sufficiently large) as a subgraph. Since $2\leq\chi(G)\leq p-1$, it follows
from Lemma 3.1 that $\mathcal{M}$ contains a matching $M_{2k_{1}}$, where
$k_{1}=e(G)$. Each partite class of $T_{p}(n_{2}p)$ contains no copy of
$M_{2k_{1}}$. Otherwise, it follows from definition of decomposition family
that $F_{n}$ contains a copy of $G^{p+1}$, a contradiction. Let
$\\{x_{1}y_{1},x_{2}y_{2},\ldots,x_{s_{1}}y_{s_{1}}\\}$ be a maximum matching
in one class, say $B^{\prime}_{1}$, of $T_{p}(n_{2}p)$ and let
$\widetilde{B}_{1}=B^{\prime}_{1}-\\{x_{1},y_{1},\ldots,x_{s_{1}},y_{s_{1}}\\}$.
Then there is no edge in $F_{n}[\widetilde{B}_{1}]$. Hence there is an induced
subgraph $T_{p}(n_{3}p)$ ($n_{3}=n_{2}-2k_{1}$ is sufficiently large) of
$F_{n}$ with partite sets $B_{1},B_{2},\ldots,B_{p}$ obtained by deleting
$2k_{1}$ vertices of each class of $T_{p}(n_{2}p)$.

Let $c$ be a sufficiently small constant and $S=V(F_{n})\setminus
V(T_{p}(n_{3}p))$. Let $T_{0}=T_{p}(n_{3}p)$. For $i\geq 1$, we will define
vertices $x_{i}\in S$ and graphs $T_{i}$ recursively. If there is a $u\in
S\setminus\\{x_{1},\ldots,x_{i-1}\\}$ which has at least $c^{2i}n_{3}$
neighbors in each class of $T_{i-1}$, then let $x_{i}=u$ and define $T_{i}$ as
a subgraph of $T_{i-1}$ which is isomorphic to $T_{p}(c^{2i}n_{3}p)$. By the
definition, we get that $\\{x_{1},\ldots,x_{i}\\}$ together with $T_{i}$ form
a complete $(p+1)$-partite graph. We claim $i\leq q-1$. Otherwise, we easily
find a copy of $T_{q}\subseteq F_{n}$ with $V(T_{q})=B_{1}^{q}\cup\ldots\cup
B_{p}^{q}$. Thus the induced subgraph of $F_{n}$ on
$B^{q}_{1}\cup\\{x_{1},x_{2},\ldots,x_{q}\\}$ is a graph with $q+c^{2q}n_{3}$
vertices and at least $c^{2q}n_{3}q$ edges. Since

$c^{2q}n_{3}q>{q-1\choose 2}+(q-1)(c^{2q}n_{3}+1)+f(k-1,k-1),$

by Lemma 4.3, this induced subgraph contains a copy of $M\in\mathcal{M}$
provided $n_{3}$ is large enough. Note that each vertex of this induced
subgraph is adjacent to each vertex of $B^{q}_{2}\cup\ldots\cup B^{q}_{p}$. By
definition of decomposition family, $S_{n}$ contains a copy of $G^{p+1}$, a
contradiction.

Now, suppose the above process ends at $T_{\ell}$ with $0\leq\ell\leq q-1$.
Denote by $x_{1},x_{2},\ldots,x_{\ell}$ the vertices joining to all the
vertices of $T_{\ell}$. Let $B^{\ell}_{1},\ldots,B^{\ell}_{p}$ be the classes
of $T_{\ell}$. Partition the remaining vertices into the following vertex
sets: Let $x\in
V(F_{n})\setminus(V(T_{\ell})\cup\\{x_{1},\ldots,x_{\ell}\\})$. If there
exists $i\in[p]$ such that $x$ is adjacent to less than $c^{2\ell+2}n_{3}$
vertices of $B^{\ell}_{i}$ and is adjacent to at least $(1-c)c^{2\ell}n_{3}$
vertices of $B^{\ell}_{j}$ for $j\neq i$, then let $x\in C^{\ell}_{i}$. If
there exists $i\in[p]$ such that $x$ is adjacent to less than
$c^{2\ell+2}n_{3}$ vertices of $B^{\ell}_{i}$ and is adjacent to less than
$(1-c)c^{2\ell}n_{3}$ vertices of some of $B^{\ell}_{j}$ with $j\neq i$, then
let $x\in D$. Obviously,

$C^{\ell}_{1}\cup\ldots\cup C^{\ell}_{p}\cup D$

is a partition of
$V(F_{n})\setminus(V(T_{\ell})\cup\\{x_{1},\ldots,x_{\ell}\\})$. Since
$\mathcal{M}$ contains a matching with size $k_{1}$ and each vertex of
$C^{\ell}_{i}$ is adjacent to less than $c^{2\ell+2}n_{3}$ vertices of
$B^{\ell}_{i}$, there are at least $c^{2\ell}n_{3}(1-c^{2}k_{1})$ vertices of
$B^{\ell}_{i}$ which are not adjacent to any vertices of $C^{\ell}_{i}$.
Indeed, there are at most $k_{1}$ independent edges in $B^{\ell}_{i}\cup
C^{\ell}_{i}$. Otherwise, since each vertex in $C^{\ell}_{i}$ is adjacent to
at least $(1-c)c^{2\ell}n_{3}$ of $B^{\ell}_{j\neq i}$, it is easy to see that
$F_{n}$ contains a copy of $G^{p+1}$, a contradiction. Consider the edges
joining $B^{\ell}_{i}$ and $C^{\ell}_{i}$ and select a maximal set of
independent edges, say $x_{1}y_{1},\ldots,x_{t}y_{t}$, $x_{i^{\prime}}\in
B^{\ell}_{i}$, $y_{i^{\prime}}\in C^{\ell}_{i}$, $1\leq i^{\prime}\leq t\leq
k_{1}$, among them, then the number of vertices of $B^{\ell}_{i}$ joining to
at least one of $y_{1},y_{2},\ldots,y_{t}$ is less than $c^{2\ell+2}n_{3}q$,
and the remaining vertices of $B^{\ell}_{i}$ are not adjacent to any vertices
of $C_{i}$ by the maximality of $x_{1}y_{1},\ldots,x_{t}y_{t}$. Hence we can
move $c^{2\ell+2}n_{3}k_{1}$ vertices of $B^{\ell}_{i}$ to $C^{\ell}_{i}$,
obtain $B^{\prime}_{i}$ and $C^{\prime}_{i}$ such that
$B^{\prime}_{i}\subseteq B^{\ell}_{i}$, $C^{\ell}_{i}\subseteq
C^{\prime}_{i}$, and there is no edge between $B^{\prime}_{i}$ and
$C^{\prime}_{i}$. Let $n_{4}=(1-c^{2}k_{1})c^{2\ell}n_{3}$. We conclude that
$T^{\prime}_{\ell}=T_{p}(n_{4}p)$ with classes
$B^{\prime}_{1},\ldots,B^{\prime}_{p}$ is an induced subgraph of $F_{n}$
satisfying the following conditions:

Let $\widehat{F}=F_{n}-T^{\prime}_{\ell}$. The vertices of $\widehat{F}$ can
be partitioned into $p+2$ classes $C^{\prime}_{1},\ldots,C^{\prime}_{p}$, $D$
and $E$ such that

  * •

each $x\in E$ is adjacent to each vertex of $T^{\prime}_{\ell}$ and
$|E|=\ell$;

  * •

if $x\in C^{\prime}_{i}$ then $x$ is adjacent to at least
$(1-c-c^{2}k_{1})c^{2\ell}n_{3}$ vertices of $B^{\prime}_{j\neq i}$ and is
adjacent to no vertex of $B^{\prime}_{i}$;

  * •

if $x\in D$, then there are two different classes, $B^{\prime}_{i}$ and
$B^{\prime}_{j}$, of $T^{\prime}_{\ell}$ such that $x$ is adjacent to less
than $c^{2\ell+2}n_{3}$ vertices of $B^{\prime}_{i}$ and less than
$(1-c)c^{2\ell}n_{3}$ vertices of $B^{\prime}_{j}$.

Denote by $e_{F}$ the number of the edges joining $\widehat{F}$ and
$T^{\prime}_{\ell}$. Clearly, we have

$e(F_{n})=e(T^{\prime}_{\ell})+e_{F}+e(\widehat{F}).$ (12)

Select an induced copy of $T^{\prime}_{\ell}$ in $H_{n}$, let
$H_{n-n_{4}p}=H_{n}-T^{\prime}_{\ell}$ and $e_{T}$ be the number of edges of
$H_{n}$ joining $T^{\prime}_{\ell}$ and $H_{n-n_{4}p}.$ Then, we have

$e(H_{n})=e(T^{\prime}_{\ell})+e_{T}+e(H_{n-n_{4}p}).$ (13)

Since $\widehat{F}$ does not contain a copy of $G^{p+1}$, we have
$e(\widehat{F})\leq e(F_{n-n_{4}p})$, where $F_{n-n_{4}p}$ is an extremal
graph for $G^{p+1}$ on $n-n_{4}p$ vertices. By (12) and (13), we have

$\displaystyle\phi(F_{n})$
$\displaystyle=e(F_{n})-e(H_{n})=e(T^{\prime}_{\ell})-e(T^{\prime}_{\ell})+(e_{F}-e_{T})+e(\widehat{F})-e(H_{n-n_{4}p})$
$\displaystyle\leq(e_{F}-e_{T})+e(F_{n-n_{4}p})-e(H_{n-n_{4}p})$
$\displaystyle=(e_{F}-e_{T})+\phi(F_{n-n_{4}p}).$

If $e_{F}-e_{T}<0$, then $\phi(F_{n})<\phi(F_{n-n_{4}p})$. Since
$n-n_{4}p>n/2$, we are done. Hence, we may assume that $e_{F}-e_{T}\geq 0$.
Recall that $n_{4}=(1-c^{2}k_{1})c^{2\ell}n_{3}$. Since $c$ is sufficiently
small, we have

$\displaystyle e_{F}-e_{T}\leq$ $\displaystyle\ell\cdot n_{4}p+(n-\ell-
n_{4}p-|D|)\cdot n_{4}(p-1)$
$\displaystyle+|D|\cdot\left(n_{4}(p-2)+(1-c)c^{2\ell}n_{3}+c^{2\ell+2}n_{3}\right)$
$\displaystyle-\left((q-1)\cdot n_{4}p+(n-q+1-n_{4}p)\cdot n_{4}(p-1)\right)$
$\displaystyle\leq$
$\displaystyle(\ell-(q-1))n_{4}+(c^{2}(k_{1}+1)-c))c^{2\ell}n_{3}|D|$
$\displaystyle\leq$ $\displaystyle 0,$

with the equality holds if and only if $|D|=0$, $\ell=q-1$, and each vertex of
$C^{\prime}_{i}$ is adjacent to each vertex of $B^{\prime}_{j\neq i}$. Note
that $T_{p}(n-q+1-n_{4}p)$ has more edges than any other $p$-chromatic graph
on $n-q+1-n_{4}p$ vertices. It follows from Lemmas 4.4 and 4.5, that
$e(F_{n})\leq h(n,p,q)+f(k-1,k-1)$ with equality holds if and only if
$F_{n}\in\mathcal{H}(n,p,q,k-1,k-1,K_{q})$ (If each graph in
$\mathcal{H}(n,p,q,k-1,k-1,K_{q})$ contains a copy of $G^{p+1}$, then we have
$e(F_{n})<h(n,p,q)+f(k-1,k-1)$). The proof is complete. $\square$

Proofs of Theorem 2.3(ii) and Theorem 2.4:
Proof. The proof is essentially the same as the proof of Theorem 2.3(i) and we
sketch the proof as follows. Let $F_{n}$ be an extremal graph for $G^{p+1}$.
Applying Lemma 4.3(b) and Proposition 3.2, we obtained that

$e(F_{n})\geq h^{\prime}(n,p,q)+\mbox{ex}(q-1,\mathcal{B}).$ (14)

By Theorem 1.1, $F_{n}$ contains a copy of $T_{p}(n_{1}p)$. Since
$\mathcal{M}$ contains a matching, as previous arguments, by progressive
induction (Lemma 4.6), $F_{n}$ can be partitioned into
$\cup_{i=1}^{p}(B^{\prime}_{i}\cup C^{\prime}_{i})\cup E$ with $|E|=q-1$
satisfies the following.

  * •

$F_{n}[\cup_{i=1}^{p}B^{\prime}_{i}]=T_{p}(n_{4}p)$;

  * •

each vertex of $E$ is adjacent to each vertex of $T_{p}(n_{4}p)$;

  * •

each vertex of $C^{\prime}_{i}$ is adjacent to each vertex of
$B^{\prime}_{j\neq i}$;

  * •

$e(F_{n}[E])\leq\mbox{ex}(q-1,\mathcal{B})$.

It follows from Proposition 4.2 that $k=1$, and hence there is no edge in
$B^{\prime}_{i}\cup C^{\prime}_{i}$ for $i\in[p]$. Thus, by (14), the result
follows similarly as the proof of Theorem 2.3(i). $\square$

##  6 Proof of Theorem 1.4

We say a graph is factor-critical if
$\nu(G)=\nu(G-\\{v\\})=\lfloor|V(G)|/2\rfloor$ for all $v\in V(G)$. Clearly, a
factor-critical $n$-vertex graph has odd number of vertices and a matching on
$n-1$ vertices. We need the following well-known lemma of Gallai.

######  Lemma 6.1 (Gallai [12])

If graph $G$ is connected and $\nu(G-\\{v\\})=\nu(G)$ for each $v\in V(G)$,
then $G$ is factor-critical.

Denote by $K_{s,t}(a,b)$ be the graph obtained from taking a copy of $K_{s,t}$
and splitting $a$ and $b$ vertices in the partite sets of $K_{s,t}$ with sizes
$s$ and $t$ respectively.

By Theorem 2.2, we have

$f(k-1,k-1)=\left\\{\begin{array}[]{ll}k^{2}-k,&\hbox{for odd $k$;}\\\
k^{2}-3k/2,&\hbox{for even $k$.}\end{array}\right.$ (15)

Define

$g(k-1,k-1)=\left\\{\begin{array}[]{ll}(2k^{2}-3k-1)/2,&\hbox{for odd $k$;}\\\
k^{2}-2k+1,&\hbox{for even $k$.}\end{array}\right.$

###### Lemma 6.2

Let $\mathcal{F}=\\{S_{t+1},M_{2t},K_{2,t-1}(0,i):i=0,1,\ldots,t-1\\}$ with
$t\geq 3$. If $n$ is sufficiently large, then

$\emph{ex}(n,\mathcal{F})=g(t-1,t-1).$

Proof. Let $G$ be an extremal graph for $\mathcal{F}$. Clearly, by Theorem
2.2, we have $e(G)\leq f(t-1,t-1)$. Thus $e(G)$ is a constant depending on
$t$. Now we do not consider the isolated vertices of $G$. Let $F_{1}=K_{t}\cup
K_{t-1}$ when $t$ is even and $F_{2}=K_{t}\cup(K_{t}-E(S_{3}\cup M_{t-3}))$
when $t$ is odd. Then $F_{1}$ and $F_{2}$ are $\mathcal{F}$-free with
$g(t-1,t-1)$ edges. Thus we have $e(G)\geq g(t-1,t-1)$. From Theorem 2.2 and
$t\geq 3$, easy calculations show that $f(t-1,t-2)\leq g(t-1,t-1)$ and
$f(t-2,t-1)\leq g(t-1,t-1)$. Hence we may suppose $\Delta(G)=t-1$ and
$\nu(G)=t-1$.

Let $s(G)$ be the number of components of $G$ which are stars. We choose $G$
with $s(G)$ as large as possible. First we will show that each component of
$G$ is either factor-critical or a star. Suppose for contrary that there is a
component $C$ of $G$ which is neither factor-critical nor a star. Choose $x\in
V(C)$ such that $\nu(C-\\{x\\})=\nu(C)-1$. If $d_{G}(x)=t-1$, then
$\Delta(G-\\{x\\})\leq t-2$, as otherwise $G$ contains a copy of
$K_{2,t-1}(0,i)$ with $0\leq i\leq t-1$. Thus from (15), we have

$e(G-\\{x\\})\leq\left\\{\begin{array}[]{ll}f(t-2,t-2)=(t-1)^{2}-3(t-1)/2,&\hbox{for
odd $t$;}\\\ f(t-2,t-2)=(t-1)^{2}-(t-1),&\hbox{for even
$t$.}\end{array}\right.$

Hence $e(G)\leq(t-1)^{2}-3(t-1)/2+(t-1)\leq(2t^{2}-5t+3)/2<(2t^{2}-3t-1)/2$
for odd $t$ and $e(G)\leq(t-1)^{2}$ for even $t$. In both cases, we are done.
Now assume that $d_{G}(x)\leq t-2$. Let $G^{\prime}$ be the graph consisting
of vertex-disjoint union of $G-\\{x\\}$ and a copy of $S_{t-1}$. Then
$G^{\prime}$ is $\mathcal{F}$-free but with $s(G^{\prime})>s(G)$ and
$e(G^{\prime})\geq e(G)$, a contradiction to our choice of $G$. Thus each
component of $G$ is either factor-critical or a star.

If $G$ contains an $S_{t}$-component, then let $G^{\prime}=G-S_{t}$. Since $G$
is $\mathcal{F}$-free, we have $\nu(G^{\prime})\leq t-2$ and
$\Delta(G^{\prime})\leq t-2$. The result follows similarly as the last
paragraph (by (15) and $e(S_{t})=t-1$). Since $G$ is an extremal graph, we may
suppose that each star of $G$ is $S_{t-1}$.

Now, we may suppose that $C_{1},C_{2},\ldots,C_{m}$ are the components of $G$
such that $C_{i}$ are factor-critical. Moreover, suppose that
$\Delta(C_{1})=t-1$ and $\Delta(C_{i})\leq t-2$ for $i=2,\ldots,m$. Let
$V(C_{i})=n_{i}$ and let $s=s(G)$ be the number of $S_{t-1}$-components of
$G$. Hence, we have

$e(C_{i})\leq\min\left\\{{n_{i}\choose
2},\left\lfloor\frac{(t-2)n_{i}}{2}\right\rfloor\right\\}\mbox{ for
}i=2,\ldots,m.$

Since $n_{1}\geq 2\lfloor t/2\rfloor+1$ (by $\Delta(C_{1})=t-1$ and $n_{1}$ is
odd), by $\nu(G)=t-1$, we have $n_{i}\leq 2\lceil t/2\rceil-1$. If $n_{i}=t$
for some $i=2,\ldots,m$, then $t$ is odd and $m=2$. Hence $G$ consists of two
components with on $t$ vertices. Since $C_{1}$ and $C_{2}$ are factor-critical
graphs with $\Delta(C_{1})=t-1$ and $\Delta(C_{2})=t-2$, we have
$e(G)\leq(t(t-1)+(t-2)t-1)/2=(2t^{2}-3t-1)/2$. The result follows. Thus we may
suppose $n_{i}\leq t-1$ and hence $e(C_{i})={n_{i}\choose 2}$ by the
maximality of $G$ for $i=2,\ldots,m$. Let $\ell$ be the number of vertices in
$C_{1}$ with degree $t-1$. Since $G$ does not contain a copy of
$K_{2,t-1}(0,i)$ for $0\leq i\leq t-1$, the vertices of $G$ with degree $t-1$
form a clique in $G$ and $\ell\leq t$. Thus, we have

$e(C_{1})\leq\min\left\\{{\ell\choose 2}+\ell(t-\ell)+{n_{1}-\ell\choose
2},\left\lfloor\frac{\ell(t-1)+(n_{1}-\ell)(t-2)}{2}\right\rfloor\right\\}.$
(16)

Hence,

$e(G)=\max\left\\{e(C_{1})+\sum_{i=2}^{m}{n_{i}\choose
2}+s(t-2):\sum_{i=1}^{m}{\lfloor n_{i}/2\rfloor}+s=t-1\right\\}.$

We will estimate $e(G)$ by considering $e(C_{i})/\nu(C_{i})$ for each
component of $G$ in following two cases:

(1). $t$ is odd. Since $n_{i}\leq t-2$ for $i=2,\ldots,m$, it is easy to see
that $e(G)$ attains its maximum when $n_{1}=t$ ($\ell=t$), $m=1$ and
$s=\lfloor t/2\rfloor$.888There are other possible values of $n_{1}$, $m$ and
$s$. Hence, $e(G)\leq t(t-1)/2+\lfloor
t/2\rfloor(t-2)=(t-1)^{2}<(2t^{2}-3t-1)/2$, we are done.

(2). $t$ is even. Then, $e(G)$ attains its maximum when $n_{1}=2t-1$ and
$\ell=t$, or $n_{1}=t$ and $n_{2}=t-1$. Thus $e(G)\leq
t(t-1)/2+(t-1)(t-2)/2=(t-1)^{2}$. The proof of the lemma is complete.
$\square$

To establish the lower bound of Theorem 1.4, we need the following graphs. For
even $t$ with $t\geq 6$, let $X=\\{x_{1},\ldots,x_{t-1}\\}$ and
$Y=\\{y_{1},\ldots,y_{t-1}\\}$. Set $X_{1}=\\{x_{1},x_{2}\ldots,x_{t/2-1}\\}$,
$Y_{1}=\\{y_{1},y_{2},\ldots,y_{t/2-1}\\}$,
$X_{2}=\\{x_{t/2},x_{t/2+1},\ldots,x_{t-2}\\}$ and
$Y_{2}=\\{y_{t/2},y_{t/2+1},\ldots,y_{t-2}\\}$. The graph $H_{2t-1}$ is
obtained as following:

  * •

Taking two vertex-disjoint copies of $K_{t-1}$ with vertex sets $X$ and $Y$
respectively;

  * •

adding a matching with size $t/2-1$ between $X_{1}$ and $Y_{1}$, a cycle of
length $t-2$ between $X_{2}$ and $Y_{2}$ and the edge $x_{t-1}y_{t-1}$;

  * •

adding a new vertex $z$ and joining it to each vertex of $X_{1}$ and $Y_{1}$;

  * •

deleting a matching with size $t/2-1$ between $X_{1}$ and $X_{2}$ and between
$Y_{1}$ and $Y_{2}$ respectively.

For $t=4$, let $H_{7}$ be graph obtained from vertex-disjoint union of copies
of $K_{4}$ and $K_{3}$ by deleting an edge of $K_{4}$ and joining the incident
vertices of the deleted edge to $K_{3}$ by two independent edges.

###### Proposition 6.3

Let $t\geq 4$ be even and $\mathcal{K}(t)=\\{K_{a,b}(0,c):a+b=t+1,\mbox{ and
}a\geq 3\mbox{ or }c=0\\}$. Then $H_{2t-1}$ is $\mathcal{K}(t)$-free.

Proof. Clearly $H_{7}$ is $\mathcal{K}(4)$-free. Let $t\geq 6$. It is not hard
to check that $H_{2t-1}$ does not contain a complete bipartite graph on at
least $t+1$ vertices, i.e., $H_{2t-1}$ does not contain a copy of
$K_{a,b}(0,0)$ with $a+b=t+1$. Suppose that $H_{2t-1}$ contains a copy of
$K_{a,b}(0,c)$ with $a+b=t+1$, $a\geq 3$ and $c>0$. Then $H_{2t-1}$ contains a
copy of $K_{a,b-c}$. Let $A$ and $B$ be the classes of $K_{a,b-c}$ with sizes
$a$ and $b-c$ respectively. Clearly, we have

$|V(K_{a,b}(0,c))|=a+b-c+ac=t+1+(a-1)c.$ (17)

If $b-c=1$, then $c=t-a$. By $a\geq 3$ and $t\geq 6$, we have
$|V(K_{a,b}(0,c))|=t+1+(a-1)(t-a)\geq 2t>|V(H_{2t-1})|$, a contradiction. We
may suppose that $b-c\geq 2$. Assume that $t\geq 8$. Let $z$ be the vertex in
definition of $H_{2t-1}$. We will find contradictions in the following two
cases.

Case 1. $A\subseteq X\cup\\{z\\}$ or $A\subseteq Y\cup\\{z\\}.$ Without loss
of generality, let $A\subseteq X\cup\\{z\\}$. Since $a\geq 3$, it is obviously
that each vertex of $B$ belongs to $X\cup\\{z\\}$ (any three vertices of
$A\cup\\{z\\}$ have no common neighbours in $Y$). Note that the complement
graph of $H_{2t-1}[X\cup\\{z\\}]$ is connected. $H_{2t-1}[X\cup\\{z\\}]$
contains no complete bipartite graph on at least $t$ vertices. Thus we have
$a+b-c\leq t-1$, i.e., $c\geq 2$. Recall that $a\geq 3$. (a). $c\geq 4$, or
$c=3$ and $a\geq 4$. Then there are at most $t+c+2(a-1)<t+1+(a-1)c$ vertices
incident with a copy of $K_{a,b}(0,c)$ with $A\subseteq X\cup\\{z\\}$, a
contradiction . (b). $c=2$. Then $a+b-c=t-1$. If $z\notin V(K_{a,b-c})$, then
$V(K_{a,b-c})=X$. Note that there is a matching between $X_{1}$ and $X_{2}$ in
the complement graph of $H_{2t-1}$. There are at most $\lfloor a/2\rfloor$
vertices of $X_{2}$ belonging to $A$. Hence there are at most $t-1+2\lfloor
a/2\rfloor+\lceil a/2\rceil<t+1+2(a-1)$ (by $a\geq 3$) vertices incident with
a copy of $K_{a,b}(0,c)$ with $A\subseteq X\cup\\{z\\}$, a contradiction. If
$z\in V(K_{a,b-c})$, then an easy observation shows that
$K_{a,b-c}=K_{t-2,1}$, a contradiction to $b-c\geq 2$. (c) $c=3$ and $a=3$.
Then $a+b-c=t-2$. Clearly, $A$ consists of $z$ and two vertices of $X_{2}$,
otherwise we have $|V(K_{a,b-c})|<t+3+2+2=t+7$, a contradiction to (17). Now,
since $t\geq 8$, $A$ has at most $t-6$ common neighbors in $X$ and hence
$a+b-c\leq t-3$. This final contradiction completes our proof for Case 1.

Case 2. $A\cap X\neq\emptyset$ and $A\cap Y\neq\emptyset$.

If $z\in A$, then $|A\cap X|=|A\cap Y|=1$, and hence $a=3$, $b-c=2$ and
$c=t-4$. Thus by (17) and $t\geq 8$, we have $|V(K_{a,b}(0,c))|=t+1+2(t-4)\geq
2t>|V(H_{2t-1})|$, a contradiction. Let $z\notin A.$ Now, without loss of
generality, we may suppose that $|A\cap X|\geq 2$. Recall that any three
vertices of $X$ have no common neighbors in $Y$. It follows from $b-c\geq 2$
that $|A\cap X|=2$ and $1\leq|A\cap Y|\leq 2$. If $|A\cap Y|=1$, then $a=3$
and $b-c=2$ for $t=8$ and $a=3$ and $2\leq b-c\leq 3$ for $t\geq 10$. Thus
$c=t-4$ for $t=8$ and $c\geq t-5$ for $t\geq 10$. By (17), we have
$|V(K_{a,b}(0,c))|=t+1+2c\geq 2t>|V(H_{2t-1})|$, a contradiction. If $|A\cap
Y|=2$, then $a=4$, $b-c=2$ and $c=t-5$. By (17) and $t\geq 8$, we have
$|V(K_{a,b}(0,c))|=t+1+3(t-5)=4t-14\geq 2t>|V(H_{2t-1})|$, which is also a
contradiction. The proof of Case 2 is complete.

Let $t=6$. Recall that $b-c\geq 2$. Consider $K_{a,b-c}=K_{4,2}$,
$K_{a,b-c}=K_{3,2}$ and $K_{a,b-c}=K_{3,3}$ respectively, it is easy to see
that $H_{11}$ is $\mathcal{K}(6)$-free. The proof is complete. $\square$

Now, we are ready for the proof of Theorem 1.4.

Proof of Theorem 1.4:

Proof. Let $s\leq t$. If $t\leq 2$, then $K_{s,t}$ is a star or $C_{4}$. The
result follows by Corollaries 3.4 and 3.6. Thus we can assume that $t\geq 3$.
Let $F_{1}\in\mathcal{H}(n,p,s,t-1,t-1,S_{s-1})$ be the graph obtained from
taking a copy of $H^{\prime}(n,p,s)$, embedding a copy of $H_{2t-1}$ when $t$
is even (two vertex-disjoint copies of $K_{t}$ when $t$ is odd respectively.)
in one class of the copy of $T(n-s+1)$ in $H^{\prime}(n,p,s)$ and embedding an
extremal graph for $S_{s-1}$ on $s-1$ vertices in the copy of $K_{s-1}$ in
$H^{\prime}(n,p,s)$. Let $F_{2}$ be the graph obtained from taking a copy of
$H(n,p,s)$ and embedding an extremal graph in Lemma 6.2 into one class of the
copy of $T(n-s+1)$ in $H(n,p,s)$.

Lemma 3.1 implies that $\mathcal{M}(K_{s,t}^{p+1})=\\{K_{s,t}(i,j):0\leq i\leq
s,0\leq j\leq t\\}$. Careful observation shows that after deleting any $s-1$
vertices, say $X$, of any $M\in\mathcal{M}(K_{s,t}^{p+1})$ with
$S_{s-1}\nsubseteq M[X]$, the obtained graph satisfies one of the following:

  * •

contains a copy of $M_{t}$;

  * •

contains a copy of $S_{t}$;

  * •

contains a copy of $K_{a,b}$ with $a+b=t+1$;

  * •

contains a copy of $K_{a,b}(0,c)$ with $a+b=t+1$, where $a\geq 3$ when $s\neq
t-1$, and $a\geq 2$ when $s=t-1$; or

  * •

has at least $2t$ vertices.

Thus, by Proposition 3.2, if $s\neq t-1$, then both $F_{1}$ and $F_{2}$ are
$K_{s,t}^{p+1}$-free; if $s=t-1$, then $F_{2}$ is $K_{s,t}^{p+1}$-free. Hence,
we have $e(G)\geq\max\\{e(F_{1}),e(F_{2})\\}$ and if $s=t-1$, then $e(G)\geq
e(F_{2})$

Let $F_{n}$ be an extremal graph for $K_{s,t}^{p+1}$. Then, by the last
paragraph, we have

$e(F_{n})\geq h(n,p,s)+f(t-1,t-1)-\left\lceil\frac{s-1}{2}\right\rceil+i,$
(18)

where $i=1$ if $s=t$ is even and $i=0$ otherwise. By Theorem 1.1, $F_{n}$
contains a copy of $T_{p}(n_{1}p)$. Since $\mathcal{M}$ contains a matching,
as previous arguments in Section 5, by progressive induction (Lemma 4.6),
$F_{n}$ can be partitioned into $\cup_{i=1}^{p}(B^{\prime}_{i}\cup
C^{\prime}_{i})\cup E$ with $|B^{\prime}_{i}\cup
C^{\prime}_{i}|=n_{i}^{\prime}$ and $|E|=s-1$ satisfies the following.

  * •

$F_{n}[\cup_{i=1}^{p}B^{\prime}_{i}]=T_{p}(n_{4}p)$ is an induced subgraph of
$F_{n}$;

  * •

each vertex of $E$ is adjacent to each vertex of
$F_{n}[\cup_{i=1}^{p}B^{\prime}_{i}]$;

  * •

each vertex of $C^{\prime}_{i}$ is adjacent to each vertex of
$B^{\prime}_{j\neq i}$.

If two of $E(F_{n}[C^{\prime}_{i}])$ are non-empty, then by (9) in Lemma 4.5,
we have $e(F_{n})\leq h(n,p,s)+t^{2}-2t$, a contradiction to (18). Thus, we
may assume that $E(F_{n}[B^{\prime}_{i}\cup C^{\prime}_{i}])$ are empty for
$i=2,\ldots,p$. Hence by Proposition 3.2, we have $e(F_{n}[B^{\prime}_{1}\cup
C^{\prime}_{1}])\leq\mbox{ex}(n^{\prime}_{1}+s-1,\mathcal{M}(K_{s,t}^{p+1}))$.

Claim. Let $p(s,t)=\mbox{ex}(n,\mathcal{M}(K_{s,t}^{p+1}))-h^{\prime}(n,1,s)$.
Then there exists an $n_{0}$ such that $p(s,t)$ depends on $s$ and $t$, when
$n\geq n_{0}$.

Proof. Let $F$ be an extremal graph for $\mathcal{M}(K_{s,t}^{p+1})$ and
$n\geq n_{0}$. Clearly, $H(n,1,s)$ is $\mathcal{M}(K_{s,t}^{p+1})$-free, and
hence $e(F)\geq(s-1)(n-s+1)$. Note that $\mathcal{M}(K_{s,t}^{p+1})$ contains
$s$ vertex-disjoint copies of $S_{t+1}$. There is a set of vertices $X$ such
that each vertex in $X$ has degree at least $n-c(s,t)$, where $c(s,t)$ is a
constant. Let $Y$ be the isolated vertices of $V(F)-X$ and $Z=V(F)-X-Y$. Note
that there is a large complete bipartite graph between $X$ and $Y$ (by $n\geq
n_{0}$). Since $F$ is an extremal graph, $F[X,Y]$ is a complete bipartite
graph. Let $p(s,t)=e(F[X])+e(F[Z])-(|X||Z|-e(F[X,Z]))$. The result follows
since $e(F[X])$, $e(F[Z])$ $e(F[X,Z])$, $|X|$ and $|Z|$ depend on $s$ and $t$.
$\square$

Thus, since $n_{1}$ is sufficiently large, it follows from the claim that

$e(F_{n})\leq\max\left\\{(s-1)(n-s+1)+p(s,t)+\sum_{i\neq
j}n^{\prime}_{i}n_{j}^{\prime}:\sum_{i=1}^{p}n_{i}^{\prime}=n-s+1\right\\}.$
(19)

Embedding an extremal graph for $\mathcal{M}(K_{s,t}^{p+1})$ on $n_{1}$
vertices in the partite set of $K_{n_{1},\ldots,n_{p}}$ with size $n_{1}$,
where $n_{1}=\lceil(n-s+1)/p\rceil+s-1$ and
$n_{i}\in\\{\lceil(n-s+1)/p\rceil,\lfloor(n-s+1)/p\rfloor\\}$, by Proposition
3.2, we have

$\mbox{ex}(n,K_{s,t}^{p+1})\geq\mbox{ex}(n_{1},\mathcal{M}(K_{s,t}^{p+1}))+\sum_{i\neq
j}n_{i}n_{j}=h^{\prime}(n,p,s)+p(s,t).$

Combining with (19), we have
$\mbox{ex}(n,K_{s,t}^{p+1})=h^{\prime}(n,p,s)+p(s,t)$. The proof of Theorem
1.4 is complete. $\square$

##  7 Conclusion

By similar method as the proof of Theorem 2.3, one can obtain the following
corollary.

###### Corollary 7.1

Let $\mathcal{F}$ be a family of graphs with $p(\mathcal{F})=p\geq 2$. If
$\mathcal{M}(\mathcal{F})=\\{M_{2s}\\}$, then

$\emph{ex}(n,\mathcal{F})=h(n,p,s),$

provided $n$ is sufficiently large. Moreover, the unique graph in
$\mathcal{H}(n,p,s,0,0,K_{s})$ is the extremal graph for $\mathcal{F}$.

Remark. There are many interesting graphs that belong to the graphs set of
Corollary 7.1, including the Petersen graph, vertex-disjoint union of cliques
with same order and the dodecahedron $D_{20}$.

In Theorem 1.4, we do not determine $\mbox{ex}(n,\mathcal{M}(K^{p+1}_{s,t}))$.
So we may pose the following conjecture.

###### Conjecture 7.2

Let $n\geq s+2t$ and $p\geq 3$. Then

$\emph{ex}(n,\mathcal{M}(K^{p+1}_{s,t}))=h(n,1,s)+f(t-1,t-1)-\left\lceil\frac{s-1}{2}\right\rceil+i,$

where $i=1$ if $s=t$ is even and $i=0$ otherwise.

Now we will find a large family of non-bipartite graphs which are counter-
examples for Conjecture 1.5 999Chen, Ma, Qiu and Yuan [3] independently found
different counter-examples for Conjecture 1.5.. First, we need a lemma proved
in [26] (also see Lemma 3.2 in [15]). If an edge $e$ is not contained in any
monochromatic copy of a given graph $H$, then we call $e$ being NIM-$H$. If a
subgraph $G$ of $K_{n}$ consists of NIM-$H$ edges, then we call $G$ being
NIM-$H$.

###### Lemma 7.3

Let $p\geq 2$, $t\geq 1$ be given integers and $H$ be a given graph. Then
there exists an integer $n_{0}=n_{0}(p,t,H)$ such that if $G$ is an NIM-$H$
graph on $n\geq n_{0}$ vertices containing at least $t_{p}(n)$ edges, then $G$
contains a blue (or red) copy of $T_{p}(tp)$ such that the edges inside each
class are red (or blue), where $t\geq|V(H)|$.

Now we present the following theorem disproving Conjecture 1.5.

###### Theorem 7.4

Let $G$ be a bipartite graph with $q<|A|$ or a non-bipartite graph with
$2\leq\chi(G)\leq p-1$. Let $n$ be sufficiently large. Then the following
hold:
(a). If $\mathcal{B}=\\{K_{q}\\}$, then

$g(n,G^{p+1})=\emph{ex}(n,G^{p+1}).$

(b). If $\mathcal{B}\neq\\{K_{q}\\}$, then

$g(n,G^{p+1})=\emph{ex}(n,G^{p+1})+{q-1\choose 2}-\emph{ex}(q-1,\mathcal{B}).$

In particular, we have

$g(n,K_{t}^{p+1})=\emph{ex}(n,K_{t}^{p+1})+{{t-1\choose 2}\choose 2}.$

Proof. The proof is essentially the same as the proof of Theorem 2.3(ii) and
Theorem 2.4. Hence we sketch the proof as follows. Let $F_{n}$ be an extremal
NIM-$G^{p+1}$ graph. Clearly, we have $e(F_{n})\geq\mbox{ex}(n,G^{p+1})\geq
t_{p}(n)$. Without loss of generality, by Lemma 7.3, $F_{n}$ contains a blue
copy of $T_{p}(t_{0}p)$ such that the edges inside each class are red, where
$t_{0}$ is sufficiently large. Since $\mathcal{M}$ contains a matching, as
previous arguments, by Proposition 4.2, Lemmas 4.3(b) and 4.6, $F_{n}$ can be
partitioned into $(\cup_{i=1}^{p}(B_{i}\cup C_{i}))\cup E$ with $|E|=q-1$
satisfying the following;

  * •

$F_{n}[\cup_{i=1}^{p}B_{i}]=T_{p}(tp)\subseteq T_{p}(t_{0}p)$, where $t\leq
t_{0}$ is sufficiently large;

  * •

each vertex of $E$ is adjacent to each vertex of $T_{p}(tp)$ by a blue edge in
$F_{n}$;

  * •

each vertex of $C_{i}$ is adjacent to each vertex of $B_{j\neq i}$ (not
necessary colored by blue);

  * •

there is no NIM-edge (blue edge) in $F_{n}[B_{i}\cup C_{i}]$ for $i\in[p]$;

  * •

the blue edges inside $E$ are at most $\mbox{ex}(q-1,\mathcal{B})$.

Thus, we have

$e(F_{n})\leq h^{\prime}(n,p,q)+e(F_{n}[E])\leq h(n,p,q).$ (20)

We divide the following proof into two cases.

(a). $\mathcal{B}=\\{K_{q}\\}$.

Clearly, by Theorem 2.3(ii) and Theorem 2.4, we have
$g(n,G^{p+1})\geq\mbox{ex}(n,G^{p+1})=h(n,p,q)$. By $|E|=q-1$ and (20), we
have $e(F_{n})\leq h(n,p,q)$, and hence $g(n,G^{p+1})=\mbox{ex}(n,G^{p+1})$,
the result follows.

(b). $\mathcal{B}\neq\\{K_{q}\\}$.

Fist, we present lower bound of $g(n,G^{p+1})$. We color a copy of
$H^{\prime}(n,p,q)$ in $K_{n}$ blue and color other edges red. Clearly, each
blue edge is an NIM-edge. Note that $q-1<|V(G^{p+1})|$. The red edges inside
$\overline{K}_{q-1}$ of $H^{\prime}(n,p,q)$ are NIM-edges. Thus we have
$g(n,G^{p+1})\geq h(n,p,q)$. Combining with (20), we have
$g(n,G^{p+1})=h(n,p,q)$, i.e, $g(n,G^{p+1})=\mbox{ex}(n,G^{p+1})+{q-1\choose
2}-\mbox{ex}(q-1,\mathcal{B}).$ Note that ${q-1\choose
2}-\mbox{ex}(q-1,\mathcal{B})>0$ when $\mathcal{B}\neq\\{K_{q}\\}$. Thus we
find counter-examples for Conjecture 1.5. $\square$

Basing on Theorem 7.4, we may pose the revised conjecture.

###### Conjecture 7.5

Let $n$ be sufficiently large. Then there exist a constant $h_{G}$ depending
on $G$ such that $g(n,G)=\emph{ex}(n,g)+h_{G}$.

Acknowledgement. The author would like to thank the referee for his/her
suggestions and Xing Peng for his careful reading on a draft.

## References

  * [1] H. L. Abbott, D. Hanson, and H. Sauer, Intersection theorems for systems of sets, _J. Combin. Theory Ser. A_ 12 (1972), 381-389.
  * [2] N. Balachandran and N. Khare, Graphs with restricted valency and matching number, _Discrete Math._ 309 (2009), 4176-4180.
  * [3] C. Chen, J. Ma, Y. Qiu, and L. Yuan, Edges not in monochromatic copies of a non-bipartite graph, manuscript.
  * [4] G. Chen, R. J. Gould, F. Pfender, and B. Wei, Extremal graphs for intersecting cliques, _J. Combin. Theory Ser. B_ 89 (2003), 159-171.
  * [5] V. Chvátal and D. Hanson, Degrees and matchings, _J. Combin. Theory Ser. B_ 20 (1976), 128-138.
  * [6] P. Erdős and A. H. Stone, On the structure of linear graphs, _Bull. Amer. Math._ 52 (1946), 1089-1091.
  * [7] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, _Acta Math. Acad. Sci. Hungar._ 10 (3) (1959), 337-356.
  * [8] P. Erdős, über ein Extremalproblem in der Graphentheorie (German), _Arch. Math. (Basel)_ 13 (1962) 122-127.
  * [9] P. Erdős and M. Simonovits, A limit theorem in graph theory, _Studia Sci. Math. Hungar._ 1 (1966) 51-57.
  * [10] P. Erdős, Z. Füredi, R. J. Gould, and D. S. Gunderson, Extremal graphs for intersecting triangles, _J. Combin. Theory Ser. B_ 63 (1) (1995) 89-100.
  * [11] Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems. Erdős centennial, 169-264, _Bolyai Soc. Math. Stud._ 25, János Bolyai Math. Soc., Budapest, 2013.
  * [12] T. Gallai, Neuer Beweis eines Tutte’schen Satzes, _Magyar Tud. Akad. Mat. Kutató Int. Közl._ 8 (1963), 135-139.
  * [13] R. Glebov, Extremal graphs for clique-paths, arXiv:1111.7029v1, (2011).
  * [14] X. Hou, Y. Qiu, and B. Liu, Extremal graph for intersecting odd cycles. _Electron. J. Combin._ 23 (2016), no. 2, Paper 2.29, 9 pp.
  * [15] P. Keevash and B. Sudakov, On the number of edges not covered by monochromatic copies of a fixed graphs, _J. Combin. Theory Ser. B_ 108 (2004), 41-53.
  * [16] H. Liu, Extremal graphs for blow-ups of cycles and trees, _Electron. J. Combin._ 20 (1) (2013), Paper 65.
  * [17] H. Liu, O. Pikhurko, and M. Sharifzadeh, Edges not in any monochromatic copy of a fixed graph, _J. Combin. Theory Ser. B_ 135 (2019), 16-43.
  * [18] J. Ma, On edges not in monochromatic copies of a fixed bipartite graph, _J. Combin. Theory Ser. B_ 132 (2017), 240-248.
  * [19] J. W. Moon, On independent complete subgraphs in a graph, _Canad. J. Math._ 20 (1968), 95-102.
  * [20] Z. Ni, L. Kang, E. Shan, and H. Zhu, Extremal graphs for blow-ups of keyrings, _Graphs Combin._ 36 (2020), no. 6, 1827-1853.
  * [21] M. Simonovits, A method for solving extremal problems in graph theory, stability problems. In _Theory of Graphs (Proc. Colloq., Tihany, 1966),_ Academic Press, New York (1968), 279-319.
  * [22] M. Simonovits, Extremal graph problems with symmetrical extremal graphs. Additionnal chromatic conditions, _Discrete Math._ 7 (1974), 349-376.
  * [23] M. Simonovits, The extremal graph problem of the icosahedron, _J. Combin. Theory Ser. B_ 17 (1974), 69-79.
  * [24] P. Turán, On an extremal problem in graph theory (in Hungrarian), _Mat. es Fiz. Lapok._ 48 (1941), 436-452.
  * [25] A. Wang, X. Hou, B. Liu, and Y. Ma, The Turán number for the edge blow-up of trees, arXiv:2008.09998v1.
  * [26] L. Yuan, Extremal functions for odd wheels, submitted, (2020).
  * [27] L. Yuan, Extremal graphs for the $k$-flower, _J. Graph Theory_ 89 (1) (2018), 26-39.
  * [28] H. Zhu, L. Kang, and E. Shan, Extremal graphs for odd-ballooning of paths and cycles, _Graphs Combin._ 36 (2020), no. 3, 755-766.

##  Appendix A Proof of Lemma 7.3

We need the following well-known theorems. The first one due to Ramsey is one
of the most important results in combinatorics.

######  Theorem A.1 (Ramsey)

For every $t$ there exists $N=R(t)$ such that every $2$-coloring of the edges
of $K_{N}$ has a monochromatic $K_{t}$ subgraph.

In 1954, Kövári, Sós, and Turán proved the following theorem.

######  Theorem A.2 (Kövári, Sós, and Turán)

.

$\emph{ex}(n,K_{t,t})=O(n^{2-\frac{1}{t}}).$

Now we are ready to prove Lemma 7.3.
Proof. Since $G$ is an NIM-$H$ graph on $n$ vertices containing at least
$t_{p}(n)$ edges, by Theorem 1.1, $G$ contains $T_{p}(Np)$ as a subgraph with
a vertex partition $V_{1}\cup\ldots\cup V_{p}$, where $N$ is a large constant
depending on Theorems A.1, A.2, and $p$.

Claim 1. There exists a constant $m(t)$ depending on $t$ such that for any two
disjoint vertex sets $U,V$ of $K_{n}$ with $|V|=|U|=m(t)$, there is a
monochromatic copy of $K_{t,t}$ between $U$ and $V$.

Proof. Without lose of generality, suppose that there are at least
$\frac{1}{2}m(t)^{2}$ red edges between $U$ and $V$. Since
$\frac{1}{2}m(t)^{2}\geq O(2m(t))^{2-\frac{1}{t}}$ when $m(t)$ is large, the
result follows from Theorem A.2. $\square$

Claim 2. Any two monochromatic copies of $K_{\ell}$ with $\ell\geq m(t)$ in
different classes of $T_{p}(Np)$ have the same color.

Proof. Let $\ell\geq m(t)$. Suppose that there are a red copy of $K_{\ell}$ in
$V_{1}$ and a blue copy of $K_{\ell}$ in $V_{2}$. Then it follows from Claim 1
that there is a monochromatic copy of $K_{t,t}$ between the red $K_{\ell}$ and
the blue $K_{\ell}$. Since $t\geq|V(H)|$, the edges of $K_{t,t}$ are contained
in a monochromatic copy of $H$, contradicting that $G$ is an NIM-$H$ graph.
The proof is complete. $\square$

Applying Theorem A.1, there is monochromatic copy of $K_{m_{0}(t)}$ in each
class of $T_{p}(Np).$ By Claim 2, those $p$ monochromatic copies of
$K_{m_{0}(t)}$ have the same color, say red. Let $G^{\prime}$ be the subgraph
of $G$ induced by those $p$ copies of $K_{t}$. Then $G^{\prime}$ has a vertex
partition $V(G^{\prime})=V^{\prime}_{1}\cup\ldots\cup V^{\prime}_{p}$ such
that $V_{i}^{\prime}\subset V_{i}$ for each $i\in[p]$. We say a pair of
disjoint vertex sets is monochromatic (red/blue) if all the edges between them
have the same color (red/blue).

We will find a copy of $T_{p}(tp)$ with the property what we need by defining
a sequence of graphs. Let $G^{0}=G^{\prime}$. By Claim 1, we can define
$G^{i+1}$ from $G^{i}$ by taking $m_{i+1}(t)$ vertices of each class of
$G^{i}$ such that the number of monochromatic pairs in the classes of
$G^{i+1}$ is least $i+1$, where $m_{i+1}(t)<m_{i}(t)$ is a sufficiently large
constant depending Theorem A.2. Note that there are ${p\choose 2}$ pairs of
vertex sets between $V_{1},\ldots,V_{p}$. Since the edges between different
classes of $G^{p\choose 2}$ are NIM-edges, $G^{p\choose 2}$ has the property
needed in the lemma with $t=m_{p\choose 2}(t)$. The proof is complete.
$\square$