# Spectral extremal problem on $t$ copies of $\ell$-cycle111Supported by the
National Natural Science Foundation of China (Nos. 12171066, 12271162), Anhui
Provincial Natural Science Foundation (No. 2108085MA13) and Major Natural
Science Research Project of Universities in Anhui Province (No. 2022AH040151).

Longfei Fanga,b, Mingqing Zhaib, Huiqiu Lina
a School of Mathematics, East China University of Science and Technology,
Shanghai 200237, China
b School of Mathematics and Finance, Chuzhou University,
Chuzhou, Anhui 239012, China
Corresponding author<EMAIL_ADDRESS>(M. Zhai)

Abstract

Denote by $tC_{\ell}$ the disjoint union of $t$ cycles of length $\ell$. Let
$ex(n,F)$ and $spex(n,F)$ be the maximum size and spectral radius over all
$n$-vertex $F$-free graphs, respectively. In this paper, we shall pay
attention to the study of both $ex(n,tC_{\ell})$ and $spex(n,tC_{\ell})$. On
the one hand, we determine $ex(n,tC_{2\ell+1})$ and characterize the extremal
graph for any integers $t,\ell$ and $n\geq f(t,\ell)$, where
$f(t,\ell)=O(t\ell^{2})$. This generalizes the result on $ex(n,tC_{3})$ of
Erdős [Arch. Math. 13 (1962) 222–227] as well as the research on
$ex(n,C_{2\ell+1})$ of Füredi and Gunderson [Combin. Probab. Comput. 24 (2015)
641–645]. On the other hand, we focus on the spectral Turán-type function
$spex(n,tC_{\ell})$, and determine the extremal graph for any fixed $t,\ell$
and large enough $n$. Our results not only extend some classic spectral
extremal results on triangles, quadrilaterals and general odd cycles due to
Nikiforov, but also develop the famous spectral even cycle conjecture proposed
by Nikiforov (2010) and confirmed by Cioabă, Desai and Tait (2022).

Keywords: Extremal graph; Spectral radius; Vertex-disjoint cycles

AMS Classification: 05C35; 05C50

##  1 Introduction

Given a graph $F$, a graph is said to be $F$-free if it does not contain a
subgraph isomorphic to $F$. The _Turán number_ of $F$, denoted by $ex(n,F)$,
is the maximum number of edges in an $n$-vertex $F$-free graph. An $F$-free
graph is said to be extremal with respect to $ex(n,F)$, if it has $n$ vertices
and $ex(n,F)$ edges. Denote by $T_{n,r}$ the complete $r$-partite graph on $n$
vertices in which all parts are as equal in size as possible. An interesting
graph in Turán-type problem is perhaps a cycle. In 2015, Füredi and Gunderson
[13] determined $ex(n,C_{2\ell+1})$ for all $n$ and $\ell$, and specially,
$T_{n,2}$ is the unique extremal graph when $n\geq 4\ell$. However, up to now
the exact value of $ex(n,C_{2\ell})$ is still open. Given a graph $F$, we
denote by $tF$ the disjoint union of $t$ copies of $F$. The study of the Turán
number of $tC_{\ell}$ can be dated back to 1962, Erdős [9] determined
$ex(n,tC_{3})$ for $n>400(t-1)^{2}$, and characterized the unique extremal
graph $K_{t-1}+T_{n-t+1,2}$ (that is, the join of $K_{t-1}$ and
$T_{n-t+1,2}$). Subsequently, Moon [19] proved that Erdős’s result is still
valid whenever $n>\frac{9t-11}{2}$. In addition, Erdős and Pósa [11] also
showed that $ex(n,t\mathcal{C})=(2t-1)(n-t)$ for $t\geq 2$ and $n\geq 24t$,
where $t\mathcal{C}$ is the family of $t$ disjoint cycles. In this paper, we
further determine the Turán number $ex(n,tC_{2\ell+1})$ by the following
theorem. It should be noted that if $n$ is sufficiently large, our result is a
special case of Theorem 2.2 due to Simonovits [28].

######  Theorem 1.1.

Let $t,\ell,n$ be three integers with $t,\ell\geq 2$ and
$n\geq\Big{\lfloor}\frac{(8t\ell+4\ell+3t-6)^{2}}{4\lfloor\frac{t}{2}\rfloor}\Big{\rfloor}+8t\ell+4t+4\ell-5$.
Then $K_{t-1}+T_{n-t+1,2}$ is the unique extremal graph with respect to
$ex(n,tC_{2\ell+1})$.

Let $A(G)$ be the adjacency matrix of a graph $G$, and $\rho(G)$ be its
spectral radius, that is, the maximum modulus of eigenvalues of $A(G)$. The
spectral extremal value of a given graph $F$, denoted by $spex(n,F)$, is the
maximum spectral radius over all $n$-vertex $F$-free graphs. An $F$-free graph
on $n$ vertices with maximum spectral radius is called an extremal graph with
respect to $spex(n,F)$. Note that $\rho(G)\geq\frac{2m}{n}$ for each graph $G$
with $n$ vertices and $m$ edges. Thus we always have
$ex(n,F)\leq\frac{n}{2}spex(n,F).$

In recent years, the investigation on $spex(n,F)$ has become very popular (see
[6, 7, 8, 15, 16, 17, 18, 26, 29, 30, 32, 34] ). In this paper, we are
interested in studying $spex(n,tF)$ for some given $F$. Up to now,
$spex(n,tF)$ and its corresponding extremal graphs were studied for some
special cases (see $spex(n,tK_{2})$ [12], $spex(n,tP_{\ell})$ [2],
$spex(n,tS_{\ell})$ [3], $spex(n,tK_{\ell})$ [20]). In this paper, we consider
that $F$ is a cycle of given length.

We first investigate the case that $F$ is an odd cycle. Note that Nikiforov
[22] determined $spex(n,C_{2\ell+1})$ for sufficiently large $n$. Using
Theorem 1.1 and Nikiforov’s result on $spex(n,C_{2\ell+1})$, we prove the
following theorem.

######  Theorem 1.2.

For any two given positive integers $t,\ell$ and sufficiently large $n$,
$K_{t-1}+T_{n-t+1,2}$ is the unique extremal graph with respect to
$spex(n,tC_{2\ell+1})$.

Next, we focus on the case that $F$ is an even cycle. When $t=1$, it can be
reduced to a classic spectral Turán-type problem, that is,
$spex(n,C_{2\ell})$, which was initially investigated by Nikiforov [21, 25].
Denote by $S_{n,\ell}$ the join of an $\ell$-clique with an independent set of
size $n-\ell$. Furthermore, let $S_{n,\ell}^{+}$ be the graph obtained from
$S_{n,\ell}$ by adding an edge within its independent set, and
$S_{n,\ell}^{++}$ be the graph obtained from $S_{n,\ell}$ by embedding a
maximum matching within its independent set. Nikiforov [21] and Zhai et al.
[33] determined $spex(n,C_{4})$ as well as its unique extremal graph
$S_{n,1}^{++}$ for odd and even $n$ respectively. In 2010, Nikiforov [25]
posed the spectral even cycle conjecture as follows: $S_{n,\ell-1}^{+}$ is the
unique extremal graph with respect to $spex(n,C_{2\ell})$ for $\ell\geq 3$ and
$n$ large enough. This conjecture was completely resolved by Cioabă, Desai and
Tait [5] in 2022. In this paper, we develop the conjecture and obtain the
following result.

######  Theorem 1.3.

Let $t,\ell$ be given positive integers and $n$ be sufficiently large. Then
(i) $S_{n,2t-1}^{++}$ is the unique extremal graph with respect to
$spex(n,tC_{4})$;
(ii) $S_{n,\ell t-1}^{+}$ is the unique extremal graph with respect to
$spex(n,tC_{2\ell})$ for $\ell\geq 3$.

By the famous Erdős-Gallai theorem, every $C_{2\ell}$-free graph has a
property that there are at most $\ell n$ edges within the neighborhood of each
vertex. However, this does not hold for $tC_{2\ell}$-free graphs provided that
$t\geq 2$. Hence, spectral extremal problem on $tC_{2\ell}$-free graphs is
different from that on $C_{2\ell}$-free graphs. To this end, we use induction
to obtain a very important structural proposition on the spectral extremal
graph $G$, precisely, $G-\\{u\\}$ contains $t-1$ disjoint $2\ell$-cycles for
each vertex $u\in V(G)$. This presents a key approach to prove Theorem 1.3.

The remainder of this paper is organized as follows. In Section 2, some
preliminary results and lemmas are presented. In Section 3, we use Erdős-Moon
theorem on $ex(n,tC_{3})$ and more structural analysis to prove Theorem 1.1,
that is, obtain the exact Turán number of $tC_{2\ell+1}$ for $n\geq
f(t,\ell)$. In Section 4, we use Theorem 1.1 and a stability method to show
Theorem 1.2. In Section 5, we give the proof of Theorem 1.3 by using induction
and the spectral even cycle results in [5, 21, 33]. We try our best in dealing
with the induction procedure, which may be helpful for other spectral Turán-
type problems.

##  2 Preliminaries

Given a simple graph $G$, we use $V(G)$ to denote the vertex set, $E(G)$ the
edge set, $|G|$ the number of vertices, $e(G)$ the number of edges, $\nu(G)$
the matching number, $\Delta(G)$ the maximum degree, $\delta(G)$ the minimum
degree, respectively. For a vertex $v\in V(G)$, we denote by $N_{G}(v)$ its
neighborhood and $d_{G}(v)$ its degree in $G$. Given two disjoint vertex
subsets $S$ and $T$. Let $G[S]$ be the subgraph induced by $S$, $G-S$ be the
subgraph induced by $V(G)\setminus S$, and $G[S,T]$ be the bipartite subgraph
on the vertex set $S\cup T$ which consists of all edges with one endpoint in
$S$ and the other in $T$. For short, we write $e(S)=e(G[S])$ and
$e(S,T)=e(G[S,T])$. Let $K_{n_{1},\dots,n_{r}}$ be the complete $r$-partite
graph with classes of sizes $n_{1},\dots,n_{r}$. If $\sum_{i=1}^{r}n_{i}=n$
and $|n_{i}-n_{j}|\leq 1$ for any two integers $i,j\in\\{1,\dots,r\\}$, then
$K_{n_{1},\dots,n_{r}}$ is exactly the $n$-vertex $r$-partite Turán graph
$T_{n,r}$. Let $F+H$ be the join and $F\cup H$ be the union, of $F$ and $H$,
respectively. Particularly, we denote by $tF$ the disjoint union of $t$ copies
of $F$.

In this section, we introduce some lemmas which will be used in the proofs of
Theorems 1.1, 1.2 and 1.3. The first one is due to Erdős [9] and Moon [19].

######  Lemma 2.1.

_([9, 19])_ Let $t,n$ be two positive integers with
$n\geq\lfloor\frac{19t-9}{2}\rfloor$. Then

$ex(n,tC_{3})=\binom{t-1}{2}+(t-1)(n-t+1)+\Big{\lfloor}\frac{(n-t+1)^{2}}{4}\Big{\rfloor}.$

Furthermore, $K_{t-1}+T_{n-t+1,2}$ is the unique extremal graph with respect
to $ex(n,tC_{3})$.

Given two integers $\nu$ and $\Delta$, define
$f(\nu,\Delta)=\max\\{e(G)~{}|~{}\nu(G)\leq\nu,\Delta(G)\leq\Delta\\}$. In
1976, Chvátal and Hanson [4] obtained the following result.

######  Lemma 2.2.

_([4])_ For every two integers $\nu\geq 1$ and $\Delta\geq 1$, we have

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

The following stability theorem was given by Nikiforov [23].

######  Theorem 2.1.

_([23])_ Let $r\geq 2$, $\frac{1}{\ln n}<c<r^{-8(r+21)(r+1)}$,
$0<\varepsilon<2^{-36}r^{-24}$ and $G$ be an $n$-vertex graph. If
$\rho(G)>(1-\frac{1}{r}-\varepsilon)n$, then one of the following holds:
(i) $G$ contains a $K_{r+1}(\lfloor c\ln n\rfloor,\dots,\lfloor c\ln
n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
(ii) $G$ differs from $T_{n,r}$ in fewer than
$(\varepsilon^{\frac{1}{4}}+c^{\frac{1}{8r+8}})n^{2}$ edges.

From Theorem 2.1, Desai et al. [8] obtained the following stability result.
Theorem 2.1 and the following lemma present an efficient approach to study
spectral extremal problems.

######  Lemma 2.3.

_([8])_ Let $F$ be a graph with chromatic number $\chi(F)=r+1$. For every
$\varepsilon>0$, there exist $\delta>0$ and $n_{0}$ such that if $G$ is an
$F$-free graph on $n\geq n_{0}$ vertices with
$\rho(G)\geq(1-\frac{1}{r}-\delta)n$, then $G$ can be obtained from $T_{n,r}$
by adding and deleting at most $\varepsilon n^{2}$ edges.

The following spectral extremal result on odd cycles is due to Nikiforov [22].

######  Lemma 2.4.

_([22])_ Let $\ell$ be a given positive integer and $n$ be large enough.
Then, $T_{n,2}$ is the unique extremal graph with respect to
$spex(n,C_{2\ell+1})$.

The following result is known as Erdős-Gallai theorem.

######  Lemma 2.5.

_([10])_ Let $n$ and $\ell$ be two integers with $n\geq\ell\geq 2$. Then
$ex(n,P_{\ell})\leq\frac{(\ell-2)n}{2}$, with equality if and only if
$n=t(\ell-1)$ and $G\cong tK_{\ell-1}$.

We note that the best current bound for $ex(n,C_{2\ell})$ was given by He
[14], who improved on a bound
$ex(n,C_{2\ell})\leq\big{(}80\sqrt{\ell}\log\ell+o(1)\big{)}n^{1+\frac{1}{\ell}}$
of Bukh and Jiang [1] by reducing a factor of $\sqrt{5\log\ell}$. However, for
our purposes the dependence of the multiplicative constant on $\ell$ is not
important. For convenience, we use the following version, which improves a
best known bound of Verstraëte [31] by a factor $8+o(1)$.

######  Lemma 2.6.

_([27])_ For all $\ell\geq 2$ and $n\geq 1$, we have

$ex(n,C_{2\ell})\leq(\ell-1)n(n^{\frac{1}{\ell}}+16).$

##  3 Proof of Theorem 1.1

In this section, we give the proof of Theorem 1.1. More precisely, we will
extend the Turán-type result on disjoint triangles to the disjoint union of
general odd cycles. First of all, we shall prove two structural lemmas.

######  Lemma 3.1.

Let $t,\ell,n$ be three positive integers with $n\geq 8t\ell+4\ell+4t-6$. Let
$G$ be a graph on $n$ vertices with $\delta(G)\geq\lfloor\frac{n}{2}\rfloor$,
and $S\subseteq V(G)$ with $|S|\leq(t-1)(2\ell+1)$. If $G-S$ contains a
triangle $C^{*}$, then $G-S$ also contains a $(2\ell+1)$-cycle.

###### Proof.

The result holds trivially for $\ell=1$. Assume now that $\ell\geq 2$. Set
$G^{\prime}=G-S$ and $C^{*}=u_{0}v_{0}w_{0}u_{0}$. Note that
$\delta(G)\geq\lfloor\frac{n}{2}\rfloor$ and $n\geq 8t\ell+4\ell+4t-6$. Then,

$\delta(G^{\prime})\geq\delta(G)-|S|\geq\Big{\lfloor}\frac{n}{2}\Big{\rfloor}-(t-1)(2\ell+1)>3\ell.$

Hence, there exist three vertices $u_{1},v_{1},w_{1}$ such that $u_{1}\in
N_{G^{\prime}}(u_{0})\setminus V(C^{*})$, $v_{1}\in
N_{G^{\prime}}(v_{0})\setminus(V(C^{*})\cup\\{u_{1}\\})$ and $w_{1}\in
N_{G^{\prime}}(w_{0})\setminus(V(C^{*})\cup\\{u_{1},v_{1}\\})$. Now let
$H_{0}=C^{*}$. Moreover, we define a subgraph $H_{1}\subseteq G^{\prime}$ with
$V(H_{1})=V(H_{0})\cup\\{u_{1},v_{1},w_{1}\\}$ and
$E(H_{1})=E(H_{0})\cup\\{u_{0}u_{1},v_{0}v_{1},w_{0}w_{1}\\}$. Similarly,
there exist three vertices $u_{2},v_{2},w_{2}$ such that $u_{2}\in
N_{G^{\prime}}(u_{1})\setminus V(H_{1})$, $v_{2}\in
N_{G^{\prime}}(v_{1})\setminus(V(H_{1})\cup\\{u_{2}\\})$ and $w_{2}\in
N_{G^{\prime}}(w_{1})\setminus(V(H_{1})\cup\\{u_{2},v_{2}\\}).$ Repeat the
above steps, we can obtain a sequence of subgraphs $H_{0},\cdots,H_{\ell-1}$
such that $V(H_{i})=V(H_{i-1})\cup\\{u_{i},v_{i},w_{i}\\}$ and

$E(H_{i})=E(H_{i-1})\cup\\{u_{i-1}u_{i},v_{i-1}v_{i},w_{i-1}w_{i}\\}$

for $1\leq i\leq\ell-1$. Note that $|H_{i}|=3i+3$ for each
$i\in\\{0,\ldots,\ell-1\\}$. Then we can easily check that
$\frac{n+3}{4}\geq|S|+|H_{\ell-1}|+\frac{1}{4}$. Furthermore, for each
$x\in\\{u_{\ell-1},v_{\ell-1},w_{\ell-1}\\}\subseteq V(H_{\ell-1})$ we can see
that

$\displaystyle|N_{G^{\prime}}(x)\setminus V(H_{\ell-1})|$ $\displaystyle\geq$
$\displaystyle d_{G^{\prime}}(x)-(|H_{\ell-1}|-1)$ $\displaystyle\geq$
$\displaystyle\delta(G^{\prime})-|H_{\ell-1}|+1$ $\displaystyle\geq$
$\displaystyle\frac{n-1}{2}-|S|-|H_{\ell-1}|+1$ $\displaystyle=$
$\displaystyle\frac{1}{3}\Big{(}n-|S|-|H_{\ell-1}|\Big{)}+\frac{2}{3}\Big{(}\frac{n+3}{4}-|S|-|H_{\ell-1}|\Big{)}.$

Thus we have

$3|N_{G^{\prime}}(x)\setminus
V(H_{\ell-1})|>n-|S|-|H_{\ell-1}|=|V(G^{\prime})\setminus V(H_{\ell-1})|.$

By the pigeonhole principle, there exists some $y\in V(G^{\prime})\setminus
V(H_{{\ell-1}})$ such that $y$ is adjacent to at least two vertices, say
$v_{\ell-1}$ and $w_{\ell-1}$, of $\\{u_{\ell-1},v_{\ell-1},w_{\ell-1}\\}$.
Hence, $G^{\prime}[\\{y,v_{0},\ldots,v_{\ell-1},w_{0},\ldots,w_{\ell-1}\\}]$
contains a cycle of length $2\ell+1$, as $v_{0}w_{0}\in E(H_{0})$. The result
follows. ∎

######  Lemma 3.2.

Let $t,k,n$ be three integers with $t\geq 2$,
$k\geq\lfloor\frac{19t-9}{2}\rfloor$ and
$n\geq\left\lfloor\frac{(k-t)^{2}}{4\lfloor\frac{t+1}{2}\rfloor}\right\rfloor+(k+1)$.
If $G$ is a graph of order $n$ with $e(G)\geq ex(n,tC_{3})$ and
$\delta(G)\leq\lfloor\frac{n}{2}\rfloor-1$, then there exists an induced
subgraph $G^{\prime}\subseteq G$ on $n^{\prime}\geq k$ vertices with
$e(G^{\prime})\geq ex(n^{\prime},tC_{3})+1$ and
$\delta(G^{\prime})\geq\lfloor\frac{n^{\prime}}{2}\rfloor$.

###### Proof.

By Lemma 2.1, for any integer $n^{*}\geq\lfloor\frac{19t-7}{2}\rfloor$ we have

$\displaystyle
ex(n^{*},tC_{3})-ex(n^{*}-1,tC_{3})=\Big{\lfloor}\frac{n^{*}+t-1}{2}\Big{\rfloor}.$
(1)

Since $\delta(G)\leq\lfloor\frac{n}{2}\rfloor-1$, there is a vertex $u_{0}\in
V(G)$ such that $d_{G}(u_{0})\leq\lfloor\frac{n-2}{2}\rfloor$. Set $G_{0}=G$
and $G_{1}=G_{0}-\\{u_{0}\\}$. Combining $e(G_{0})\geq ex(n,tC_{3})$,
$d_{G_{0}}(u_{0})\leq\lfloor\frac{n-2}{2}\rfloor$ and (1) gives

$\displaystyle e(G_{1})=e(G_{0})-d_{G_{0}}(u_{0})\geq
ex(n-1,tC_{3})+\Big{\lfloor}\frac{t+1}{2}\Big{\rfloor},$ (2)

as
$\lfloor\frac{n+t-1}{2}\rfloor-\lfloor\frac{n-2}{2}\rfloor\geq\lfloor\frac{t+1}{2}\rfloor$.
Now, if $\delta(G_{1})\geq\lfloor\frac{n-1}{2}\rfloor$, then we define
$G^{\prime}=G_{1}$ and we are done. Otherwise, there is a vertex $u_{1}\in
V(G_{1})$ such that $d_{G_{1}}(u_{1})\leq\lfloor\frac{n-3}{2}\rfloor$. Then,
we set $G_{2}=G_{1}-\\{u_{1}\\}$. By (1) and (2), we obtain

$e(G_{2})=e(G_{1})-d_{G_{1}}(u_{1})\geq
ex(n-2,tC_{3})+2\Big{\lfloor}\frac{t+1}{2}\Big{\rfloor},$

as
$\lfloor\frac{n+t-2}{2}\rfloor-\lfloor\frac{n-3}{2}\rfloor\geq\lfloor\frac{t+1}{2}\rfloor$.
Repeating the above steps, we obtain either a $G_{i}$ for some $i\leq n-k-1$
such that it is a desired induced subgraph or a sequence of induced subgraphs
$G_{0},G_{1},\cdots,G_{n-k}$ such that $|G_{i}|=n-i$ and

$\displaystyle e({G_{i}})\geq
ex(n-i,tC_{3})+i\Big{\lfloor}\frac{t+1}{2}\Big{\rfloor}$ (3)

for $1\leq i\leq n-k$. Since
$n\geq\left\lfloor\frac{(k-t)^{2}}{4\lfloor\frac{t+1}{2}\rfloor}\right\rfloor+(k+1)$,
we have

$\displaystyle(n-k)\Big{\lfloor}\frac{t+1}{2}\Big{\rfloor}>\frac{(k-t)^{2}}{4}\geq\binom{k-t+1}{2}-\Big{\lfloor}\frac{(k-t+1)^{2}}{4}\Big{\rfloor}.$
(4)

From Lemma 2.1 we know that

$ex(k,tC_{3})=\binom{t-1}{2}+(t-1)(k-t+1)+\Big{\lfloor}\frac{(k-t+1)^{2}}{4}\Big{\rfloor}.$

Combining the above equality with (3) and (4), we obtain

$\displaystyle e(G_{n-k})\geq
ex(k,tC_{3})+(n-k)\Big{\lfloor}\frac{t+1}{2}\Big{\rfloor}>\binom{t-1}{2}+(t-1)(k-t+1)+\binom{k-t+1}{2}=\binom{k}{2},$

contradicting $|G_{n-k}|=k$. Hence, $G_{i}$ is a desired induced subgraph for
some $i\leq n-k-1.$ ∎

Having Lemmas 3.1 and 3.2, we are now ready to give the proof of Theorem 1.1.
Recall that $t\geq 2$, $\ell\geq 2$ and
$n\geq\left\lfloor\frac{(8t\ell+4\ell+3t-6)^{2}}{4\lfloor\frac{t}{2}\rfloor}\right\rfloor+8t\ell+4t+4\ell-5$.
For convenience, we denote $G^{*}=K_{t-1}+T_{n-t+1,2}$.

###### Proof.

By Lemma 2.1, we have $e(G^{*})=ex(n,tC_{3})$ for $t\geq 2$ and
$n\geq\lfloor\frac{19t-9}{2}\rfloor$. Moreover, we can easily check that
$G^{*}$ contains at most $t-1$ vertex-disjoint copies of $C_{2\ell+1}$ for
each positive integer $\ell$, as every odd cycle in $G^{*}$ must occupy at
least one vertex in the $(k-1)$-clique. Let $G$ be an extremal graph with
respect to $ex(n,tC_{2\ell+1})$. Then

$e(G)=ex(n,tC_{2\ell+1})\geq e(G^{*})=ex(n,tC_{3}).$

Set $k=8t\ell+4\ell+4t-6$. Since $\ell\geq 2$, we have
$k\geq\big{\lfloor}\frac{19t-9}{2}\big{\rfloor}.$ Suppose now that
$\delta(G)\leq\lfloor\frac{n}{2}\rfloor-1$. Then by Lemma 3.2, there exists an
induced subgraph $G^{\prime}\subseteq G$ on $n^{\prime}\geq k$ vertices such
that $e(G^{\prime})\geq ex(n^{\prime},tC_{3})+1$ and
$\delta(G^{\prime})\geq\lfloor\frac{n^{\prime}}{2}\rfloor$. Furthermore, by
Lemma 2.1, $G^{\prime}$ contains $t$ vertex-disjoint triangles
$C^{1},C^{2},\dots,C^{t}$.

Let $S_{1}=\cup_{i=2}^{t}V(C^{i})$. Then $|S_{1}|=3(t-1)\leq(t-1)(2\ell+1)$,
and $G^{\prime}-S_{1}$ contains a triangle $C^{1}$. By Lemma 3.1,
$G^{\prime}-S_{1}$ also contains a $(2\ell+1)$-cycle ${C^{1}}^{*}$. Let
$S_{2}=V({C^{1}}^{*})\cup(\cup_{i=3}^{t}V(C^{i}))$. Then
$|S_{2}|=(2\ell+1)+3(t-2)\leq(t-1)(2\ell+1)$, and $G^{\prime}-S_{2}$ contains
a triangle $C^{2}$. Again by Lemma 3.1, $G^{\prime}-S_{2}$ also contains a
$(2\ell+1)$-cycle ${C^{2}}^{*}$.

Repeating the above steps, we obtain a sequence of subsets
$S_{1},\cdots,S_{t}$ such that

$S_{j}=\big{(}\cup_{i=1}^{j-1}V({C^{i}}^{*})\big{)}\cup\big{(}\cup_{i=j+1}^{t}V(C^{i})\big{)}$

and $G^{\prime}-S_{j}$ contains a $(2\ell+1)$-cycle ${C^{j}}^{*}$ for $2\leq
j\leq t$. Hence, $G^{\prime}$ contains $t$ disjoint $(2\ell+1)$-cycles
${C^{1}}^{*},\dots,{C^{t}}^{*}$, contradicting the fact that $G$ is
$tC_{2\ell+1}$-free. Therefore, $\delta(G)\geq\lfloor\frac{n}{2}\rfloor$.

Recall that $e(G)\geq ex(n,tC_{3})$. Then by Lemma 2.1, if $G\not\cong G^{*}$,
then $G$ contains $t$ vertex-disjoint triangles. Furthermore, by Lemma 3.1 and
a similar way as above to $G^{\prime}$, we can find $t$ vertex-disjoint
$(2\ell+1)$-cycles in $G$, a contradiction. Therefore, $G\cong G^{*}$. This
completes the proof of Theorem 1.1. ∎

##  4 Proof of Theorem 1.2

In this section, we give a proof of Theorem 1.2. By Lemma 2.4, it holds
directly for $t=1$. In the following, assume that $t\geq 2$ and $G$ is an
extremal graph with respect to $spex(n,tC_{2\ell+1})$. Clearly, $G$ is
connected (otherwise, we can add a new edge between two distinct components of
$G$). By Perron-Frobenius theorem, there exists a positive unit eigenvector
$X=(x_{1},\ldots,x_{n})^{T}$ corresponding to $\rho(G)$. Assume that $u^{*}\in
V(G)$ with $x_{u^{*}}=\max\\{x_{i}~{}|~{}i\in V(G)\\}$. We also choose a
positive constant $\eta<\frac{1}{75}$, which will be frequently used in the
proof. Let $G^{*}=K_{t-1}+T_{n-t+1,2}$, where $G^{*}=T_{n,2}$ for $t=1$. We
shall prove $G\cong G^{*}$ for $n$ sufficiently large.

######  Lemma 4.1.

$\rho(G)\geq\frac{n}{2}+(t-1)-\frac{t^{2}}{2n}.$

###### Proof.

By Theorem 1.1, $G^{*}$ is an extremal graph with respect to
$ex(n,tC_{2\ell+1})$. Since
$e(T_{n-t+1,2})=\big{\lfloor}\frac{(n-t+1)^{2}}{4}\big{\rfloor}\geq\frac{(n-t+1)^{2}-1}{4},$
we have

$e(G^{*})=e(K_{t-1})+e(T_{n-t+1,2})+(t-1)(n-t+1)\geq\frac{1}{4}n^{2}+\frac{t-1}{2}n-\frac{t^{2}}{4}.$

Using the Rayleigh quotient gives

$\rho(G)\geq\rho(G^{*})\geq\frac{\mathbf{1}^{T}A(G^{*})\mathbf{1}}{\mathbf{1}^{T}\mathbf{1}}=\frac{2e(G^{*})}{n}\geq\frac{n}{2}+(t-1)-\frac{t^{2}}{2n},$

as desired. ∎

######  Lemma 4.2.

For $n$ sufficiently large,
$e(G)\geq\big{(}\frac{1}{4}-\frac{1}{2}\eta^{2}\big{)}n^{2}.$ Furthermore, $G$
admits a partition $V(G)=V_{1}\cup V_{2}$ such that $e(V_{1},V_{2})$ attains
the maximum, $e(V_{1})+e(V_{2})\leq\frac{1}{2}\eta^{2}n^{2}$ and
$\big{|}|V_{i}|-\frac{n}{2}\big{|}\leq\eta n$ for $i\in\\{1,2\\}.$

###### Proof.

Note that $\chi(tC_{2l+1})=3$ and $G$ is $tC_{2l+1}$-free. Moreover, by Lemma
4.1, $\rho(G)\geq\frac{n}{2}+(t-1)-\frac{t^{2}}{2n}$. Let $\varepsilon$ be a
positive constant with $\varepsilon<\frac{1}{2}\eta^{2}$. Then by Lemma 2.3,
$e(G)\geq\frac{1}{4}n^{2}-\frac{1}{2}\eta^{2}n^{2}$, and there exists a
bipartition $V(G)=U_{1}\cup U_{2}$ such that
$\lfloor\frac{n}{2}\rfloor\leq|U_{1}|\leq|U_{2}|\leq\lceil\frac{n}{2}\rceil$
and $e(U_{1})+e(U_{2})\leq\frac{1}{2}\eta^{2}n^{2}$. We now select a new
bipartition $V(G)=V_{1}\cup V_{2}$ such that $e(V_{1},V_{2})$ attains the
maximum. Then $e(V_{1})+e(V_{2})$ attains the minimum, and

$e(V_{1})+e(V_{2})\leq e(U_{1})+e(U_{2})\leq\frac{1}{2}\eta^{2}n^{2}.$

On the other hand, assume that $|V_{1}|=\frac{n}{2}-a$, then
$|V_{2}|=\frac{n}{2}+a$. Thus,

$e(G)\leq|V_{1}||V_{2}|+e(V_{1})+e(V_{2})\leq\frac{1}{4}n^{2}-a^{2}+\frac{1}{2}\eta^{2}n^{2}.$

Combining $e(G)\geq\frac{1}{4}n^{2}-\frac{1}{2}\eta^{2}n^{2}$ gives
$a^{2}\leq\eta^{2}n^{2}$, and so $|a|\leq\eta n$. ∎

In the following, we shall define two vertex subsets $U$ and $W$ of $G$.

######  Lemma 4.3.

Let $U=\\{v\in V(G)~{}|~{}d_{G}(v)\leq\big{(}\frac{1}{2}-4\eta\big{)}n\\}.$
Then we have $|U|\leq\eta n$.

###### Proof.

Suppose to the contrary that $|U|>\eta n$, then there exists
$U^{\prime}\subseteq U$ with $|U^{\prime}|=\lfloor\eta n\rfloor$. Moreover, by
Lemma 4.2, we have
$e(G)\geq\big{(}\frac{1}{4}-\frac{1}{2}\eta^{2}\big{)}n^{2}$. Now set
$n^{\prime}=|G-U^{\prime}|=n-\lfloor\eta n\rfloor$. Then
$n^{\prime}-1<\big{(}1-\eta)n$. Thus,

$\displaystyle e(G-U^{\prime})$ $\displaystyle\geq$ $\displaystyle
e(G)-\sum_{v\in U^{\prime}}d_{G}(v)$ $\displaystyle\geq$
$\displaystyle\Big{(}\frac{1}{4}-\frac{\eta^{2}}{2}\Big{)}n^{2}-\eta
n\Big{(}\frac{1}{2}-4\eta\Big{)}n$ $\displaystyle=$
$\displaystyle\frac{1}{4}\big{(}1-2\eta+14\eta^{2}\big{)}n^{2}$
$\displaystyle>$ $\displaystyle\frac{1}{4}\big{(}n^{\prime}-1+t\big{)}^{2}$

for sufficiently large $n$. We can further check that
$\frac{1}{4}(n^{\prime}+t-1)^{2}>e(K_{t-1}+T_{n^{\prime}-t+1,2}).$ Hence,
$e(G-U^{\prime})>e(K_{t-1}+T_{n^{\prime}-t+1,2})$. By Theorem 1.1,
$G-U^{\prime}$ contains $t$ vertex-disjoint $(2\ell+1)$-cycles, contradicting
the fact that $G$ is $tC_{2\ell+1}$-free. ∎

######  Lemma 4.4.

Let $W=W_{1}\cup W_{2}$, where $W_{i}=\\{v\in V_{i}~{}|~{}d_{V_{i}}(v)\geq
2\eta n\\}$ and $d_{V_{i}}(v)=|N_{G}(v)\cap V_{i}|$ for $i\in\\{1,2\\}$. Then
we have $|W|\leq\frac{1}{2}\eta n$.

###### Proof.

For $i\in\\{1,2\\}$,

$2e(V_{i})=\sum_{v\in V_{i}}d_{V_{i}}(v)\geq\sum_{v\in
W_{i}}d_{V_{i}}(v)\geq|W_{i}|\cdot 2\eta n.$

Combining Lemma 4.2, we have

$\frac{1}{2}\eta^{2}n^{2}\geq
e(V_{1})+e(V_{2})\geq\big{(}|W_{1}|+|W_{2}|\big{)}\eta n=|W|\eta n.$

Therefore, $|W|\leq\frac{1}{2}\eta n$. ∎

In the following three lemmas, we focus on constructing $(2\ell+1)$-cycles in
distinct induced subgraphs of the spectral extremal graph $G$.

######  Lemma 4.5.

For arbitrary $R\subseteq V(G)$ with $|R|\leq t(2\ell+1)$, if there exists an
edge within $V_{i}\setminus(U\cup W\cup R)$ for some $i\in\\{1,2\\}$, then
$G-(U\cup W\cup R)$ contains a $(2\ell+1)$-cycle.

###### Proof.

Let $V^{\prime}=V_{1}^{\prime}\cup V_{2}^{\prime}$, where
$V_{i}^{\prime}=V_{i}\setminus(U\cup W\cup R)$ for $i\in\\{1,2\\}$. Moreover,
we may assume that $\widehat{i}\in\\{1,2\\}\setminus\\{i\\}$. We first claim
that for each vertex $u\in V_{i}^{\prime}$,

$\displaystyle|N_{V^{\prime}}(u)|\geq|N_{V_{\widehat{i}}^{\prime}}(u)|>\frac{2}{5}n,$
(5)

where $N_{V^{\prime}}(u)=N_{G}(u)\cap V^{\prime}$. Since $u\notin U\cup W$, we
know that $d_{V_{i}}(u)<2\eta n$ and $d_{G}(u)>(\frac{1}{2}-4\eta)n$. Recall
that $V_{1}\cup V_{2}$ is a bipartition of $V(G)$. Thus
$d_{V_{\widehat{i}}}(u)=d_{G}(u)-d_{V_{i}}(u)>(\frac{1}{2}-6\eta)n$. Combining
Lemmas 4.3 and 4.4 gives

$|N_{V_{\widehat{i}}^{\prime}}(u)|\geq|N_{V_{\widehat{i}}}(u)|-\big{(}|U|+|W|+|R|\big{)}>\Big{(}\frac{1}{2}-6\eta\Big{)}n-\frac{3}{2}\eta
n-t(2\ell+1)>\frac{2}{5}n,$

as the constant $\eta<\frac{1}{75}$ and $n$ is sufficiently large. Thus, (5)
follows.

Now let $u_{0}v_{0}$ be an arbitrary edge within $V_{i}^{\prime}$. From (5) we
know that both $|N_{V_{\widehat{i}}^{\prime}}(u_{0})|>\frac{2}{5}n$ and
$|N_{V_{\widehat{i}}^{\prime}}(v_{0})|>\frac{2}{5}n$. Moreover, by Lemma 4.2,
$|V_{\widehat{i}}^{\prime}|\leq|V_{\widehat{i}}|\leq\frac{n}{2}+\eta n$. Thus,

$\big{|}N_{V_{\widehat{i}}^{\prime}}(u_{0})\cap
N_{V_{\widehat{i}}^{\prime}}(v_{0})\big{|}\geq\big{|}N_{V_{\widehat{i}}^{\prime}}(u_{0})\big{|}+\big{|}N_{V_{\widehat{i}}^{\prime}}(v_{0})\big{|}-\big{|}V_{\widehat{i}}^{\prime}\big{|}>\frac{3}{10}n-\eta
n>0,$

and hence there exists a vertex $w_{0}\in
N_{V_{\widehat{i}}^{\prime}}(u_{0})\cap N_{V_{\widehat{i}}^{\prime}}(v_{0})$.
Since $w_{0}\in V_{\widehat{i}}^{\prime}$, it follows from (5) that
$|N_{V^{\prime}}(w_{0})|\geq|N_{V_{i}^{\prime}}(u)|>\frac{2}{5}n$.

Let $H_{0}=G[\\{u_{0},v_{0},w_{0}\\}]$. Then $H_{0}\cong C_{3}$ and
$H_{0}\subseteq G-(U\cup W\cup R)$. If $\ell=1$, then $H_{0}$ is a desired
$(2\ell+1)$-cycle. Assume now that $\ell\geq 2$. Since
$|N_{V^{\prime}}(u)|>\frac{2}{5}n$ for each $u\in V(H_{0})$, there exist
$u_{1},v_{1},w_{1}\in V^{\prime}$ such that $u_{1}\in
N_{V^{\prime}}(u_{0})\setminus V(H_{0})$, $v_{1}\in
N_{V^{\prime}}(v_{0})\setminus(V(H_{0})\cup\\{u_{1}\\})$ and $w_{1}\in
N_{V^{\prime}}(w_{0})\setminus(V(H_{0})\cup\\{u_{1},v_{1}\\})$. Then, we
define a subgraph $H_{1}\subseteq G$ with
$V(H_{1})=V(H_{0})\cup\\{u_{1},v_{1},w_{1}\\}$ and
$E(H_{1})=E(H_{0})\cup\\{u_{0}u_{1},v_{0}v_{1},w_{0}w_{1}\\}$. Similarly,
there exist $u_{2},v_{2},w_{2}$ such that $u_{2}\in
N_{V^{\prime}}(u_{1})\setminus V(H_{1})$, $v_{2}\in
N_{V^{\prime}}(v_{1})\setminus(V(H_{1})\cup\\{u_{2}\\})$ and $w_{2}\in
N_{V^{\prime}}(w_{1})\setminus(V(H_{1})\cup\\{u_{2},v_{2}\\}).$ Repeating the
above steps, we obtain a sequence of subgraphs $H_{0},H_{1},\cdots,H_{\ell-1}$
such that $V(H_{j})=V(H_{j-1})\cup\\{u_{j},v_{j},w_{j}\\}$ and
$E(H_{j})=E(H_{j-1})\cup\\{u_{j-1}u_{j},v_{j-1}v_{j},w_{j-1}w_{j}\\}$ for
$1\leq j\leq\ell-1$. Then, $|H_{\ell-1}|=3\ell$ and $H_{\ell-1}\subseteq
G-(U\cup W\cup R)$. Set $V^{\prime\prime}=V^{\prime}\setminus V(H_{\ell-1})$.
For each $u\in\\{u_{\ell-1},v_{\ell-1},w_{\ell-1}\\}$, we have
$|N_{V^{\prime\prime}}(u)|\geq|N_{V^{\prime}}(u)|-|H_{\ell-1}|+1>\frac{2}{5}n-3\ell+1,$
and thus

$|N_{V^{\prime\prime}}(u_{\ell-1})|+|N_{V^{\prime\prime}}(v_{\ell-1})|+|N_{V^{\prime\prime}}(w_{\ell-1})|>n>|V^{\prime\prime}|$

for $n$ sufficiently large. This implies that there exists $w\in
V^{\prime\prime}$ such that $w$ is adjacent to at least two vertices, say
$u_{\ell-1}$ and $v_{\ell-1}$, of $\\{u_{\ell-1},v_{\ell-1},w_{\ell-1}\\}$.
Therefore, $G-(U\cup W\cup R)$ contains a $(2\ell+1)$-cycle $u_{0}\ldots
u_{\ell-1}wv_{\ell-1}\ldots v_{0}u_{0}$. The proof is completed. ∎

######  Lemma 4.6.

For arbitrary $R\subseteq V(G)$ with $|R|\leq t(2\ell+1)$, if there exists a
vertex $u_{0}\in W\setminus U$, then $G-\big{(}(U\cup W\cup
R)\setminus\\{u_{0}\\}\big{)}$ contains a $(2\ell+1)$-cycle.

###### Proof.

Since $V(G)=V_{1}\cup V_{2}$, we may assume without loss of generality that
$u_{0}\in V_{1}$. Then by the definitions of $U$ and $W$, we have

$d_{G}(u_{0})>\Big{(}\frac{1}{2}-4\eta\Big{)}n~{}~{}~{}\mbox{and}~{}~{}~{}d_{V_{1}}(u_{0})\geq
2\eta n.$

Moreover, by Lemmas 4.3 and 4.4, $|U|\leq\eta n$ and $|W|\leq\frac{1}{2}\eta
n$. Thus,

$\big{|}N_{V_{1}\setminus(U\cup W\cup R)}(u_{0})\big{|}\geq
d_{V_{1}}(u_{0})-(|U|+|W|+|R|)\geq\frac{1}{2}\eta n-t(2\ell+1)>0.$

Then, there exists a vertex $v_{0}$ in $N_{V_{1}}(u_{0})\setminus(U\cup W\cup
R)$. Again by the definitions of $U$ and $W$, we can see that
$d_{G}(v_{0})>(\frac{1}{2}-4\eta)n$ and $d_{V_{1}}(v_{0})<2\eta n$. It follows
that

$\displaystyle
d_{V_{2}}(v_{0})=d_{G}(v_{0})-d_{V_{1}}(v_{0})>\Big{(}\frac{1}{2}-6\eta\Big{)}n.$
(6)

Recall that $V(G)=V_{1}\cup V_{2}$ is a bipartition of $V(G)$ such that
$e(V_{1},V_{2})$ attains the maximum. Hence,
$d_{V_{1}}(u_{0})\leq\frac{1}{2}d_{G}(u_{0})$. Since
$d_{G}(u_{0})>(\frac{1}{2}-4\eta)n$, we get that

$\displaystyle
d_{V_{2}}(u_{0})=d_{G}(u_{0})-d_{V_{1}}(u_{0})\geq\frac{1}{2}d_{G}(u_{0})>\Big{(}\frac{1}{4}-2\eta\Big{)}n.$
(7)

Furthermore, Lemma 4.2 gives $|V_{2}|\leq\frac{n}{2}+\eta n.$ Combining with
(6) and (7), we obtain

$\left|N_{V_{2}}(u_{0})\cap
N_{V_{2}}(v_{0})\right|\geq|N_{V_{2}}(u_{0})|+|N_{V_{2}}(v_{0})|-|V_{2}|\geq\Big{(}\frac{1}{4}-9\eta\Big{)}n.$

Note that $\eta<\frac{1}{75}$ and $n$ is sufficiently large. It follows that

$\Big{|}\big{(}N_{V_{2}}(u_{0})\cap N_{V_{2}}(v_{0})\big{)}\setminus(U\cup
W\cup R)\Big{|}\geq\Big{(}\frac{1}{4}-9\eta\Big{)}n-\frac{3}{2}\eta
n-t(2\ell+1)>0.$

Hence, there exists $w_{0}\in\big{(}N_{V_{2}}(u_{0})\cap
N_{V_{2}}(v_{0})\big{)}\setminus(U\cup W\cup R)$. Let
$H_{0}=G[\\{u_{0},v_{0},w_{0}\\}]$. Then $H_{0}\cong C_{3}$ and
$H_{0}\subseteq G-\big{(}(U\cup W\cup R)\setminus\\{u_{0}\\}\big{)}$. For
$\ell=1$, $H_{0}$ is a $(2\ell+1)$-cycle. For $\ell\geq 2$, using the same
method as in the proof of Lemma 4.5, we can find a $(2\ell+1)$-cycle in
$G-\big{(}(U\cup W\cup R)\setminus\\{u_{0}\\}\big{)}$. ∎

######  Lemma 4.7.

Let $\nu=\sum_{i=1}^{2}\nu\big{(}G[V_{i}\setminus(U\cup W)]\big{)}$. Then
$\nu\leq t-1$. Moreover, $G-(U\cup W)$ contains at least $\nu$ disjoint
$(2\ell+1)$-cycles.

###### Proof.

The case $\nu=0$ is trivial. Now assume that $\nu\geq 1$, and let
$u_{1}u_{2},\ldots,u_{2\nu-1}u_{2\nu}$ be $\nu$ independent edges in
$G[V_{1}\setminus(U\cup W)]\cup G[V_{2}\setminus(U\cup W)]$. Then, we set
$R_{0}=\\{u_{j}~{}|~{}j=1,2,\ldots,2\lambda\\}$ and
$R_{1}=R_{0}\setminus\\{u_{1},u_{2}\\}$, where $\lambda=\min\\{\nu,t\\}$.
Since $u_{1}u_{2}$ is an edge within $V_{i}\setminus(U\cup W\cup R_{1})$ for
some $i\in\\{1,2\\}$, Lemma 4.5 indicates that $G-(U\cup W\cup R_{1})$
contains a $(2\ell+1)$-cycle $C^{1}$. Let
$R_{2}=\big{(}R_{1}\setminus\\{u_{3},u_{4}\\}\big{)}\cup V(C^{1})$. Again by
Lemma 4.5, $G-(U\cup W\cup R_{2})$ contains a $(2\ell+1)$-cycle $C^{2}$, as
$u_{3}u_{4}$ is an edge within $V_{i}\setminus(U\cup W\cup R_{2})$ for some
$i\in\\{1,2\\}$.

Repeating the above steps, we obtain a sequence of vertex subsets
$R_{1},\cdots,R_{\lambda}$ such that
$R_{j}=\big{(}R_{j-1}\setminus\\{u_{2j-1},u_{2j}\\}\big{)}\cup\big{(}\cup_{k=1}^{j-1}V(C^{k})\big{)}$
and $G-(U\cup W\cup R_{j})$ contains a $(2\ell+1)$-cycle $C^{j}$ for each
$j\in\\{2,\dots,\lambda\\}$. Clearly, $|R_{j}|\leq(\lambda-1)(2\ell+1)$ for
$1\leq j\leq\lambda$; moreover, $C^{1},C^{2},\dots,C^{\lambda}$ are disjoint
cycles in $G-(U\cup W)$. Since $G$ is $tC_{2\ell+1}$-free, we have
$\lambda\leq t-1$. Combining $\lambda=\min\\{\nu,t\\}$ gives $\nu=\lambda\leq
t-1$, and thus $C^{1},C^{2},\dots,C^{\nu}$ are disjoint $(2\ell+1)$-cycles in
$G-(U\cup W)$. ∎

In the following two lemmas, we shall give two local structural properties of
$G$.

######  Lemma 4.8.

For $i\in\\{1,2\\}$, we have $\Delta\big{(}G[V_{i}\setminus(U\cup
W)]\big{)}<t(2\ell+1)$.

###### Proof.

Our proof is by contradiction. Without loss of generality, suppose that there
exists a vertex $u_{0}\in V_{1}\setminus(U\cup W)$ such that
$d_{V_{1}\setminus(U\cup W)}(u_{0})\geq t(2\ell+1)$. Since $u_{0}\notin W$, we
get $d_{V_{1}}(u_{0})<2\eta n$ by the definition of $W$. On the other hand, by
Lemma 4.2, $|V_{1}|\geq\frac{n}{2}-\eta n$, and so

$|V_{1}\setminus(U\cup
W)|\geq|V_{1}|-|U|-|W|\geq\Big{(}\frac{1}{2}-\frac{5}{2}\eta\Big{)}n.$

Hence, $|V_{1}\setminus(U\cup W)|>d_{V_{1}}(u_{0})$, as $\eta<\frac{1}{75}.$
This implies that there exist vertices in $V_{1}\setminus(U\cup W)$ which are
not adjacent to $u_{0}$. Let $G^{\prime}$ be the graph obtained from $G$ by
adding all possible edges from $u_{0}$ to $V_{1}\setminus(U\cup W)$. Then
$\rho(G^{\prime})>\rho(G)$. Since $G$ is extremal with respect to
$spex(n,tC_{2\ell+1})$, $G^{\prime}$ must contain a subgraph $H$ isomorphic to
$tC_{2\ell+1}$. From the construction of $G^{\prime}$, we can further see that
$u_{0}\in V(C)$ for some $(2\ell+1)$-cycle $C$ in $H$. Set
$H^{\prime}=H-V(C).$ Then $H^{\prime}\subseteq G$. Since
$d_{V_{1}\setminus(U\cup W)}(u_{0})\geq t(2\ell+1)$ while
$|H^{\prime}|=(t-1)(2\ell+1)$, there exists a vertex $v_{0}$ with $v_{0}\in
N_{V_{1}\setminus(U\cup W)}(u_{0})$ and $v_{0}\notin V(H^{\prime})$ in $G$.

Now setting $R=V(H^{\prime})$ in Lemma 4.5, and noticing that $u_{0}v_{0}$ is
an edge within $V_{1}\setminus(U\cup W\cup R)$, we obtain that $G-(U\cup W\cup
R)$ contains a $(2\ell+1)$-cycle $C^{\prime}$. Clearly, $V(C^{\prime})\cap
V(H^{\prime})=\varnothing$. Therefore, $C^{\prime}\cup H^{\prime}$ is a copy
of $tC_{2\ell+1}$ in $G$, which contradicts the fact that $G$ is
$tC_{2\ell+1}$-free. ∎

######  Lemma 4.9.

For $i\in\\{1,2\\}$, $G[V_{i}\setminus(U\cup W)]$ contains an independent set
$I_{i}$ with $|I_{i}|>|V_{i}\setminus(U\cup W)|-2(t-1)t(2\ell+1)$.

###### Proof.

Assume that $\nu_{i}=\nu\big{(}G[V_{i}\setminus(U\cup W)]\big{)}$ for
$i\in\\{1,2\\}$. If $\nu_{i}=0$, then $V_{i}\setminus(U\cup W)$ is a desired
independent set. Now assume that $\nu_{i}\geq 1$, and let
$u_{1}u_{2},\ldots,u_{2\nu_{i}-1}u_{2\nu_{i}}$ be $\nu_{i}$ independent edges
in $G[V_{i}\setminus(U\cup W)]$. Let

$I_{i}=\big{(}V_{i}\setminus(U\cup
W)\big{)}\setminus\big{(}\cup_{j=1}^{2\nu_{i}}N_{V_{i}\setminus(U\cup
W)}(u_{j})\big{)}.$

Then, every vertex in $I_{i}$ is not adjacent to any vertex in
$\\{u_{1},u_{2},\dots,u_{2\nu_{i}}\\}$. Now, if $G[I_{i}]$ contains an edge,
then $\nu\big{(}G[V_{i}\setminus(U\cup W)]\big{)}\geq\nu_{i}+1$, a
contradiction. Therefore, $I_{i}$ is an independent set.

From Lemma 4.8 we know that $\Delta\big{(}G[V_{i}\setminus(U\cup
W)]\big{)}<t(2\ell+1)$. Moreover, $\nu_{i}\leq\nu\leq t-1$ by Lemma 4.7. Thus,
we can see that

$|V_{i}\setminus(U\cup
W)|-|I_{i}|=|\cup_{j=1}^{2\nu_{i}}N_{V_{i}\setminus(U\cup W)}(u_{j})|\leq
2\nu_{i}\Delta\big{(}G[V_{i}\setminus(U\cup W)]\big{)}<2(t-1)t(2\ell+1).$

The result follows. ∎

In the following three lemmas, we will give exact characterizations of $U$ and
$W$. Since $|W|\leq\frac{1}{2}\eta n<n$ by Lemma 4.4, we may choose a vertex
$v^{*}$ such that $x_{v^{*}}=\max\\{x_{v}~{}|~{}v\in V(G)\setminus W\\}$. We
will see that $v^{*}\notin U$. Recall that $x_{u^{*}}=\max\\{x_{v}~{}|~{}v\in
V(G)\\}$. Then $\rho(G)x_{u^{*}}\leq|W|x_{u^{*}}+(n-|W|)x_{v^{*}}.$ Moreover,
$\rho(G)>\frac{n}{2}$ by Lemma 4.1. It follows that

$\displaystyle
x_{v^{*}}\geq\frac{\rho(G)-|W|}{n-|W|}x_{u^{*}}\geq\frac{\rho(G)-|W|}{n}x_{u^{*}}>\frac{1}{2}\big{(}1-\eta\big{)}x_{u^{*}}.$
(8)

Since $\eta<\frac{1}{75}$, we have $x_{v^{*}}>\frac{2}{5}x_{u^{*}}$. On the
other hand,

$\rho(G)x_{v^{*}}=\sum_{v\in N_{W}(v^{*})}x_{v}+\sum_{v\in
N_{G-W}(v^{*})}x_{v}\leq|W|x_{u^{*}}+d_{G}(v^{*})x_{v^{*}}.$

Combining with $x_{v^{*}}>\frac{2}{5}x_{u^{*}}$, $\rho(G)>\frac{n}{2}$ and
$|W|\leq\frac{1}{2}\eta n$, we obtain

$d_{G}(v^{*})\geq\rho(G)-\frac{x_{u^{*}}}{x_{v^{*}}}|W|\geq\rho(G)-\frac{5}{2}|W|>\Big{(}\frac{1}{2}-\frac{5}{4}\eta\Big{)}n.$

Recall that $U=\\{v\in
V(G)~{}|~{}d_{G}(v)\leq\big{(}\frac{1}{2}-4\eta\big{)}n\\}$. Then $v^{*}\notin
U$, and so $v^{*}\in V(G)\setminus(U\cup W)$.

Assume now that $v^{*}\in V_{i^{*}}\setminus(U\cup W)$ for some
$i^{*}\in\\{1,2\\}$, and set
$\widehat{i^{*}}\in\\{1,2\\}\setminus\\{i^{*}\\}$. Then by Lemma 4.8,
$|N_{V_{i^{*}}}(v^{*})\setminus(U\cup W)|<t(2\ell+1)$. Thus,

$\displaystyle\rho(G)x_{v^{*}}$ $\displaystyle=$ $\displaystyle\sum_{v\in
N_{U\cup W}(v^{*})}x_{v}+\sum_{v\in N_{V_{i^{*}}}(v^{*})\setminus(U\cup
W)}x_{v}+\sum_{v\in N_{V_{\widehat{i^{*}}}}(v^{*})\setminus(U\cup W)}x_{v}$
$\displaystyle<$
$\displaystyle\big{(}|W|x_{u^{*}}+|U|x_{v^{*}}\big{)}+t(2\ell+1)x_{v^{*}}+\sum_{v\in
V_{\widehat{i^{*}}}\setminus(U\cup W\cup I_{\widehat{i^{*}}})}x_{v}+\sum_{v\in
I_{\widehat{i^{*}}}}x_{v}$ $\displaystyle\leq$
$\displaystyle\big{(}|W|x_{u^{*}}+|U|x_{v^{*}}\big{)}+(2t-1)t(2\ell+1)x_{v^{*}}+\sum_{v\in
I_{\widehat{i^{*}}}}x_{v},$

where $I_{\widehat{i^{*}}}$ is an independent set of
$G[V_{\widehat{i^{*}}}\setminus(U\cup W)]$ such that
$\big{|}V_{\widehat{i^{*}}}\setminus(U\cup W\cup
I_{\widehat{i^{*}}})\big{|}<2(t-1)t(2\ell+1)$ (see Lemma 4.9). Subsequently,

$\displaystyle\sum_{v\in
I_{\widehat{i^{*}}}}x_{v}>\big{(}\rho(G)-|U|-(2t-1)t(2\ell+1)\big{)}x_{v^{*}}-|W|x_{u^{*}}.$
(9)

######  Lemma 4.10.

We have $U=\varnothing$.

###### Proof.

Suppose to the contrary that there exists $u_{0}\in U$. Let $G^{\prime}$ be
the graph obtained from $G$ by deleting edges incident to $u_{0}$ and joining
all possible edges from $I_{\widehat{i^{*}}}$ to $u_{0}$.

We claim that $G^{\prime}$ is $tC_{2\ell+1}$-free. Otherwise, $G^{\prime}$
contains a subgraph $H$ isomorphic to $tC_{2\ell+1}$. From the construction of
$G^{\prime}$, we can see that $H$ must contain a $(2\ell+1)$-cycle
$C^{\prime}$ with $u_{0}\in V(C^{\prime})$. Set $H^{\prime}=H-V(C^{\prime})$.
Then $H^{\prime}\subseteq G$. Assume that
$N_{C^{\prime}}(u_{0})=\\{u_{1},u_{2}\\}$, then $u_{1},u_{2}\in
I_{\widehat{i^{*}}}$ by the definition of $G^{\prime}$. Since
$I_{\widehat{i^{*}}}\subseteq V_{\widehat{i^{*}}}\setminus(U\cup W)$, we have
$u_{1},u_{2}\notin U\cup W$. By the definitions of $U$ and $W$, we know that
$d_{G}(u_{j})>\big{(}\frac{1}{2}-4\eta\big{)}n$ and
$d_{V_{\widehat{i^{*}}}}(u_{j})<2\eta n$ for $j\in\\{1,2\\}$. Hence,
$|N_{V_{i^{*}}}(u_{1})|=d_{G}(u_{1})-d_{V_{\widehat{i^{*}}}}(u_{1})>\big{(}\frac{1}{2}-6\eta\big{)}n$.
Similarly, $|N_{V_{i^{*}}}(u_{2})|>\big{(}\frac{1}{2}-6\eta\big{)}n$.
Moreover, $|V_{i^{*}}|\leq\frac{n}{2}+\eta n$ by Lemma 4.2. It follows that

$|N_{V_{i^{*}}}(u_{1})\cap
N_{V_{i^{*}}}(u_{2})|\geq|N_{V_{i^{*}}}(u_{1})|+|N_{V_{i^{*}}}(u_{2})|-|V_{i^{*}}|>\Big{(}\frac{1}{2}-13\eta\Big{)}n.$

Now, note that $|H|=t(2\ell+1).$ Then $|N_{V_{i^{*}}}(u_{1})\cap
N_{V_{i^{*}}}(u_{2})|>|H|$, and hence we can find a vertex
$u\in\big{(}N_{V_{i^{*}}}(u_{1})\cap N_{V_{i^{*}}}(u_{2})\big{)}\setminus
V(H)$. This implies that $G-V(H^{\prime})$ contains a $(2\ell+1)$-cycle
$C^{\prime\prime}$, which is obtained from $C^{\prime}$ by replacing
$\\{u_{0}u_{1},u_{0}u_{2}\\}$ with $\\{uu_{1},uu_{2}\\}$. Hence,
$C^{\prime\prime}\cup H^{\prime}$ is a copy of $tC_{2\ell+1}$ in $G$, a
contradiction. Therefore, the above claim holds.

Now, $d_{G}(u_{0})\leq(\frac{1}{2}-4\eta)n$ by the definition of $U$. Recall
that $\rho(G)>\frac{n}{2}$ and $|U|\leq\eta n$. Then

$\displaystyle\rho(G)-d_{G}(u_{0})-|U|>3\eta n.$ (10)

Moreover,

$\displaystyle\sum_{v\in N_{G}(u_{0})}x_{v}=\sum_{v\in
N_{W}(u_{0})}x_{v}+\sum_{v\in
N_{G-W}(u_{0})}x_{v}\leq|W|x_{u^{*}}+d_{G}(u_{0})x_{v^{*}}.$ (11)

Recall that $x_{v^{*}}>\frac{2}{5}x_{u^{*}}$ and $|W|\leq\frac{1}{2}\eta n$.
Combining (9), (10) and (11), we get that

$\displaystyle\sum_{v\in I_{\widehat{i^{*}}}}x_{v}\\!\\!-\\!\\!\sum_{v\in
N_{G}(u_{0})}x_{v}$ $\displaystyle\geq$ $\displaystyle\sum_{v\in
I_{\widehat{i^{*}}}}x_{v}-\big{(}|W|x_{u^{*}}+d_{G}(u_{0})x_{v^{*}}\big{)}$
$\displaystyle>$
$\displaystyle\big{(}\rho(G)\\!-\\!d_{G}(u_{0})\\!-\\!|U|\\!-\\!(2t-1)t(2\ell+1)\big{)}x_{v^{*}}\\!-\\!2|W|x_{u^{*}}$
$\displaystyle>$ $\displaystyle\big{(}3\eta
n-(2t-1)t(2\ell+1)\big{)}\frac{2}{5}x_{u^{*}}-\eta nx_{u^{*}}$
$\displaystyle>$ $\displaystyle\frac{1}{10}\eta nx_{u^{*}}$

for $n$ sufficiently large. Thus,

$\rho(G^{\prime})-\rho(G)\geq
X^{T}\big{(}A(G^{\prime})-A(G)\big{)}X=2x_{u_{0}}\Big{(}\sum_{v\in
I_{\widehat{i^{*}}}}x_{v}-\sum_{v\in N_{G}(u_{0})}x_{v}\Big{)}>0,$

contradicting the fact that $G$ is extremal with respect to
$spex(n,tC_{2\ell+1})$. Hence, $U=\varnothing$. ∎

######  Lemma 4.11.

For each $v\in V(G)$, we have $x_{v}>\frac{2}{5}x_{u^{*}}$.

###### Proof.

Recall that $\rho(G)>\frac{n}{2}$ and $|W|\leq\frac{1}{2}\eta n$. Then
$|W|<\eta\rho(G)$. Moreover, $U=\varnothing$ by Lemma 4.10. Combining (9), we
obtain that

$\sum_{v\in
I_{\widehat{i^{*}}}}x_{v}>\big{(}\rho(G)-(2t-1)t(2\ell+1)\big{)}x_{v_{0}}-\eta\rho(G)x_{u^{*}}.$

From (8) we know that $x_{v^{*}}>\frac{1}{2}\big{(}1-\eta\big{)}x_{u^{*}}.$
Thus, for $n$ sufficiently large,

$\sum_{v\in
I_{\widehat{i^{*}}}}x_{v}>\Big{(}\frac{1}{2}-2\eta\Big{)}\rho(G)x_{u^{*}}.$

Now, suppose to the contrary that there exists $u_{0}\in V(G)$ such that
$x_{u_{0}}\leq\frac{2}{5}x_{u^{*}}$. Let $G^{\prime}$ be the graph obtained
from $G$ by deleting edges incident to $u_{0}$ and joining all edges from
$I_{\widehat{i^{*}}}$ to $u_{0}$. By a similar discussion as in the proof of
Lemma 4.10, we claim that $G^{\prime}$ is $tC_{2\ell+1}$-free. However,

$\sum_{v\in I_{\widehat{i^{*}}}}x_{v}\\!\\!-\\!\\!\sum_{v\in
N_{G}(u_{0})}x_{v}=\sum_{v\in
I_{\widehat{i^{*}}}}x_{v}-\rho(G)x_{u_{0}}>\left(\frac{1}{2}-2\eta-\frac{2}{5}\right)\rho(G)x_{u^{*}}>0,$

which implies that

$\rho(G^{\prime})-\rho(G)\geq
X^{T}\big{(}A(G^{\prime})-A(G)\big{)}X=2x_{u_{0}}\Big{(}\sum_{v\in
I_{\widehat{i^{*}}}}x_{v}-\sum_{v\in N_{G}(u_{0})}x_{v}\Big{)}>0,$

contradicting the fact that $G$ is extremal with respect to
$spex(n,tC_{2\ell+1})$. ∎

######  Lemma 4.12.

$|W|=t-1$ and $\nu=0$.

###### Proof.

Note that $U=\varnothing$. By Lemma 4.7,
$\nu=\nu(\cup_{i=1}^{2}G[V_{i}\setminus W])\leq t-1$; and if $\nu\geq 1$, then
$G-W$ contains $\nu$ disjoint $(2\ell+1)$-cycles $C^{1},C^{2},\dots,C^{\nu}$.

We first claim that $|W|\leq t-1-\nu$. Otherwise, $|W|\geq t-\nu$. Let
$R_{0}=\\{u_{1},u_{2},\dots,u_{t-\nu}\\}$ be a subset of $W$. Furthermore, we
define $R_{1}=R_{0}\setminus\\{u_{1}\\}$ if $\nu=0$; and
$R_{1}=(R_{0}\setminus\\{u_{1}\\})\cup(\cup_{i=1}^{\nu}V(C^{i}))$ if $\nu\geq
1$. Then $|R_{1}|\leq(t-1)(2\ell+1).$ By Lemma 4.6, $G-\big{(}(W\cup
R_{1})\setminus\\{u_{1}\\}\big{)}$ contains a $(2\ell+1)$-cycle $C^{\nu+1}$,
where $V(C^{\nu+1})\cap R_{0}\subseteq\\{u_{1}\\}$. If $t-\nu\geq 2$, then we
further define $R_{2}=\big{(}R_{1}\setminus\\{u_{2}\\}\big{)}\cup
V(C^{\nu+1})$. Clearly, $|R_{2}|\leq(t-1)(2\ell+1).$ Again by Lemma 4.6,
$G-\big{(}(W\cup R_{2})\setminus\\{u_{2}\\}\big{)}$ contains a
$(2\ell+1)$-cycle $C^{\nu+2}$, where $V(C^{\nu+2})\cap
R_{0}\subseteq\\{u_{2}\\}$. Repeating the above steps, we obtain a sequence of
vertex subsets $R_{1},R_{2},\ldots,R_{t-\nu}$ with
$R_{j}=\big{(}R_{j-1}\setminus\\{u_{j}\\}\big{)}\cup\big{(}\cup_{k=1}^{j-1}V(C^{\nu+k})\big{)}$
and $|R_{j}|\leq(t-1)(2\ell+1)$ such that $G-\big{(}(W\cup
R_{j})\setminus\\{u_{j}\\}\big{)}$ contains a $(2\ell+1)$-cycle $C^{\nu+j}$
for each $j\in\\{1,\dots,t-\nu\\}$. Furthermore, $V(C^{\nu+j})\cap
R_{0}\subseteq\\{u_{j}\\}$ for $1\leq j\leq t-\nu$. Thus we can observe that
$C^{1},C^{2},\dots,C^{t}$ are disjoint, which contradicts the fact that $G$ is
$tC_{2\ell+1}$-free.

Now define $H=\cup_{i=1}^{2}G[V_{i}\setminus W]$. Then $\nu(H)=\nu$. We
further claim that

$\displaystyle e(H)\leq(t-1)(2t\ell+t+1).$ (12)

The case $\nu=0$ is trivial. Assume that $\nu\geq 1$. By Lemma 4.8,
$\Delta(H)<t(2\ell+1)$. Recall that
$f(\nu,\Delta)=\max\\{e(G)~{}|~{}\nu(G)\leq\nu,\Delta(G)\leq\Delta\\}$, and by
Lemma 2.2 $f(\nu,\Delta)\leq\nu(\Delta+1)$. Thus,

$e(H)\leq f\big{(}\nu(H),\Delta(H)\big{)}\leq
f(\nu,t(2\ell+1))\leq\nu\cdot(2t\ell+t+1).$

Note that $\nu\leq t-1$. Therefore, (12) holds.

Note that $|W|\leq t-1-\nu\leq t-1$. It suffices to prove $|W|=t-1$, as it
implies that $\nu=0$. Suppose to the contrary that $|W|\leq t-2$. Take
$S\subseteq V_{1}\setminus W$ with $|S|=t-1-|W|$, and let $G^{\prime}$ be the
graph obtained from $G$ by deleting all edges in $E(H)$ and adding all
possible edges from $S$ to $V_{1}\setminus(W\cup S)$. Clearly, $G^{\prime}$ is
a spanning subgraph of $K_{|W\cup S|}+K_{|V_{1}\setminus(W\cup
S)|,|V_{2}\setminus W|}$. Since $|W\cup S|=t-1$, $G^{\prime}$ contains at most
$t-1$ disjoint odd cycles, and so $G^{\prime}$ is $tC_{2\ell+1}$-free.

Recall that $|V_{1}|\geq\frac{1}{2}n-\eta n$, and by Lemma 4.11,
$x_{v}>\frac{2}{5}x_{u^{*}}$ for each $v\in V(G)$. Combining (12), we have

$\displaystyle\rho(G^{\prime})-\rho(G)$ $\displaystyle\geq$ $\displaystyle
X^{T}\big{(}A(G^{\prime})-A(G)\big{)}X\geq\sum_{u\in S,v\in
V_{1}\setminus(W\cup S)}2x_{u}x_{v}-\sum_{uv\in E(H)}2x_{u}x_{v}$
$\displaystyle\geq$ $\displaystyle|S|\big{(}\frac{n}{2}\\!-\\!\eta
n\\!-\\!t\\!+1\big{)}\frac{8}{25}x_{u^{*}}^{2}\\!-\\!(t-1)(2t\ell\\!+\\!t\\!+\\!1)2x_{u^{*}}^{2}$
$\displaystyle>$ $\displaystyle 0,$

contradicting the fact that $G$ is an extremal graph with respect to
$spex(n,tC_{2\ell+1})$. ∎

In the following, we complete the proof of Theorem 1.2.

###### Proof.

Recall that $G^{*}=K_{t-1}+T_{n-t+1,2}$ and we shall prove $G\cong G^{*}$. We
first look for a $(t-1)$-clique in which each vertex dominates all vertices of
$G$. By Lemma 4.12, we know that $|W|=t-1$. It suffices to show that
$d_{G}(u)=n-1$ for each $u\in W$.

Suppose to the contrary that there exists a vertex $u\in W$ with $d(u)<n-1$.
Then we can select a non-neighbor $v$ of $u$ in $G$. Let
$G^{\prime}=G+\\{uv\\}$. Then $\rho(G^{\prime})>\rho(G)$. Since $G$ is
extremal with respect to $spex(n,tC_{2\ell+1})$, $G^{\prime}$ contains a
subgraph $H$ isomorphic to $tC_{2\ell+1}$, where $uv\in E(H)$. More precisely,
$H$ contains a $(2\ell+1)$-cycle $C$ with $uv\in V(C)$. Set
$H^{\prime}=H-V(C)$. Then $H^{\prime}\subseteq G$, and by Lemma 4.6,
$G-\big{(}(W\cup V(H^{\prime}))\setminus\\{u\\}\big{)}$ contains a
$(2\ell+1)$-cycle $C^{\prime}$. Since $u\notin V(H^{\prime})$, $H^{\prime}\cup
C^{\prime}$ is a copy of $tC_{2\ell+1}$ in $G$, a contradiction. Therefore,
$d_{G}(u)=n-1$ for each $u\in W$.

Let $|V_{i}\setminus W|=n_{i}$ for $i\in\\{1,2\\}$. Assume without loss of
generality that $n_{1}\geq n_{2}$. By Lemma 4.12,
$\nu=\nu(\cup_{i=1}^{2}G[V_{i}\setminus W])=0$, and thus $G-W\subseteq
K_{n_{1},n_{2}}$. Since $G$ is extremal, we have $G-W\cong K_{n_{1},n_{2}}$.
To show $G\cong G^{*}$, it suffices to show $G-W\cong T_{n-t+1,2}$, or
equivalently, $n_{1}-n_{2}\leq 1$.

Suppose to the contrary that $n_{1}\geq n_{2}+2$. By symmetry, we may assume
$x_{u}=x_{i}$ for each $u\in V_{i}\setminus W$ and $i\in\\{1,2\\}$. Moreover,
let $x_{u}=x_{3}$ for each $u\in W$. Thus,

$\displaystyle\rho(G)x_{1}=n_{2}x_{2}+(t-1)x_{3},~{}\rho(G)x_{2}=n_{1}x_{1}+(t-1)x_{3},$

and $\rho(G)x_{3}=n_{1}x_{1}+n_{2}x_{2}+(t-2)x_{3}.$ It follows that

$\displaystyle
x_{1}=\frac{\rho(G)+1}{\rho(G)+n_{1}}x_{3}~{}~{}\text{and}~{}~{}x_{2}=\frac{\rho(G)+1}{\rho(G)+n_{2}}x_{3}.$
(13)

Select $u_{0}\in V_{1}\setminus W$. Let $G^{\prime\prime}$ be the graph
obtained from $G$ by deleting edges from $u_{0}$ to $V_{2}\setminus W$ and
adding all edges from $u_{0}$ to $V_{1}\setminus(W\cup\\{u_{0}\\})$. Then
$G^{\prime\prime}\cong K_{t-1}+K_{n_{1}-1,n_{2}+1}$, and thus
$G^{\prime\prime}$ is still $tC_{2\ell+1}$-free. Moreover,

$\rho(G^{\prime\prime})-\rho(G)\geq\sum_{v\in
V_{1}\setminus(W\cup\\{u_{0}\\})}2x_{u_{0}}x_{v}-\sum_{v\in V_{2}\setminus
W}2x_{u_{0}}x_{v}=2x_{1}\big{(}(n_{1}-1)x_{1}-n_{2}x_{2}\big{)}.$

In view of (13), we have

$(n_{1}-1)x_{1}-n_{2}x_{2}=\frac{(\rho(G)+1)\left((n_{1}-n_{2}-1)\rho(G)-n_{2}\right)}{(\rho(G)+n_{1})(\rho(G)+n_{2})}x_{3}>0,$

since $n_{1}\geq n_{2}+2$ and $\rho(G)>\frac{n}{2}>n_{2}$. It follows that
$\rho(G^{\prime\prime})>\rho(G),$ a contradiction. Therefore, $n_{1}-n_{2}\leq
1$ and $G\cong K_{t-1}+T_{n-t+1,2}$. This completes the proof. ∎

##  5 Proof of Theorem 1.3

In this section, we will often assume that $n$ is sufficiently large without
saying so explicitly. We first give the lower and upper bounds of
$\rho(S_{n,\ell}^{+})$ and $\rho(S_{n,\ell}^{++})$.

######  Lemma 5.1.

For fixed $\ell$ and sufficiently large $n$,
(i)
$\rho(S_{n,\ell}^{++})\geq\rho(S_{n,\ell}^{+})\geq\frac{\ell-1+\sqrt{(\ell-1)^{2}+4\ell(n-\ell)}}{2}\geq\sqrt{\ell
n}$ if $\ell\geq 2$;
(ii) $\rho(S_{n,\ell}^{++})\leq\sqrt{\big{(}\ell+\frac{1}{4\ell}\big{)}n}$ if
$\ell\geq 1$.

###### Proof.

(i) By a straightforward calculation, we have
$\rho(S_{n,\ell})=\frac{\ell-1+\sqrt{(\ell-1)^{2}+4\ell(n-\ell)}}{2}.$ Since
$S_{n,\ell}\subseteq S_{n,\ell}^{+}\subseteq S_{n,\ell}^{++}$, the inequality
holds obviously for $\ell\geq 2$.

(ii) By Perron-Frobenius theorem, there exists a positive unit eigenvector
$X=(x_{1},\ldots,x_{n})^{T}$ corresponding to $\rho$, where
$\rho=\rho(S_{n,\ell}^{++})$. Let $W$ be the set of dominating vertices in
$S_{n,\ell}^{++}$, and $\overline{W}=V(S_{n,\ell}^{++})\setminus W$. Choose
$u_{0}\in W$ and $v_{0}\in\overline{W}$ with $x_{u_{0}}=\max_{u\in W}x_{u}$
and $x_{v_{0}}=\max_{v\in\overline{W}}x_{v}$. Note that $|W|=\ell$. Then,
$\rho x_{u_{0}}\leq(\ell-1)x_{u_{0}}+(n-\ell)x_{v_{0}}$ and $\rho
x_{v_{0}}\leq\ell x_{u_{0}}+x_{v_{0}}$. Combining these two inequalities, we
obtain

$(\rho-\ell+1)(\rho-1)\leq(n-\ell)\ell.$

If $\rho>\sqrt{\big{(}\ell+\frac{1}{4\ell}\big{)}n}$, then
$(\rho-\ell+1)(\rho-1)>(n-\ell)\ell$, a contradiction. Thus,
$\rho\leq\sqrt{\big{(}\ell+\frac{1}{4\ell}\big{)}n}$. ∎

Recall that $\ell\geq 2$ in Theorem 1.3. We shall proceed the proof by
induction on $t$. When $t=1$, the result holds immediately by [5, 21, 33]. In
the following, we assume that $t\geq 2$.

For convenience, set $\lambda=\ell t-1$, then $\lambda\geq 2\ell-1$. Let $G$
be an extremal graph with respect to $spex(n,tC_{2\ell})$. Clearly, $G$ is
connected. By Perron-Frobenius theorem, there exists a positive unit
eigenvector $X=(x_{1},\ldots,x_{n})^{T}$ corresponding to $\rho(G)$. Choose
$u^{*}\in V(G)$ with $x_{u^{*}}=\max\\{x_{i}~{}|~{}i=1,2,\dots,n\\}$. For a
vertex $u$ and a positive integer $i$, let $N_{i}(u)$ denote the set of
vertices at distance $i$ from $u$ in $G$. By the induction hypothesis, we
obtain that for $n^{\prime}$ sufficiently large,

$\displaystyle
spex\big{(}n^{\prime},(t-1)C_{2\ell}\big{)}=\left\\{\begin{array}[]{ll}\rho(S_{n^{\prime},\lambda-\ell}^{++})&\hbox{if
$\ell=2$,}\\\ \rho(S_{n^{\prime},\lambda-\ell}^{+})&\hbox{if $\ell\geq
3$.}\end{array}\right.$ (16)

We then show that for each $u\in V(G)$, $G-\\{u\\}$ contains $t-1$ disjoint
copies of $C_{2\ell}$ through Lemmas 5.2 and 5.3. This will be used to bound
$\rho(G)$ in Lemma 5.4, to bound $\sum_{v\in V(G)}d_{G}^{2}(v)$ in Lemma 5.5
and to prove a key property in Lemma 5.6.

######  Lemma 5.2.

Let $H$ be a graph on $n-1$ vertices. Then
$\rho(H)\geq\rho(K_{1}+H)-\frac{n-1}{\rho(K_{1}+H)}$.

###### Proof.

Let $\overline{u}$ be the dominating vertex of $K_{1}+H$ corresponding to
$K_{1}$. Set $\overline{\rho}=\rho(K_{1}+H)$ and $Y=(y_{u})$ be an eigenvector
to $\overline{\rho}$. Using the Rayleigh quotient gives

$\overline{\rho}=\frac{2\sum_{uv\in E(K_{1}+H)}y_{u}y_{v}}{\sum_{u\in
V(K_{1}+H)}y_{u}^{2}}=\frac{2\sum_{uv\in
E(H)}y_{u}y_{v}+2y_{\overline{u}}\sum_{u\in
V(H)}y_{u}}{y_{\overline{u}}^{2}+\sum_{u\in V(H)}y_{u}^{2}}.$

Since $\overline{\rho}y_{\overline{u}}=\sum_{u\in V(H)}y_{u}$, we have
$y_{\overline{u}}\sum_{u\in
V(H)}y_{u}=\overline{\rho}y_{\overline{u}}^{2}=\frac{1}{\overline{\rho}}\big{(}\sum_{u\in
V(H)}y_{u}\big{)}^{2}.$ Thus,

$2\sum_{uv\in E(H)}y_{u}y_{v}=\overline{\rho}\sum_{u\in
V(H)}y_{u}^{2}-\overline{\rho}y_{\overline{u}}^{2}=\overline{\rho}\sum_{u\in
V(H)}y_{u}^{2}-\frac{1}{\overline{\rho}}\Big{(}\sum_{u\in
V(H)}y_{u}\Big{)}^{2}.$

From Cauchy-Schwarz inequality that $\big{(}\sum_{u\in
V(H)}y_{u}\big{)}^{2}\leq(n-1)\sum_{u\in V(H)}y_{u}^{2}$. It follows that

$\rho(H)\geq\frac{2\sum_{uv\in E(H)}y_{u}y_{v}}{\sum_{u\in
V(H)}y_{u}^{2}}\geq\overline{\rho}-\frac{n-1}{\overline{\rho}},$

as desired. ∎

######  Lemma 5.3.

For every vertex $u\in V(G)$, $G-\\{u\\}$ contains $t-1$ disjoint
$2\ell$-cycles.

###### Proof.

Suppose to the contrary that there exists a vertex $u$ such that $G-\\{u\\}$
is $(t-1)C_{2\ell}$-free. Then $\rho(G-\\{u\\})\leq
spex\big{(}n-1,(t-1)C_{2\ell}\big{)}$. It follows from (16) that

$\displaystyle\rho\big{(}G-\\{u\\}\big{)}\leq\rho\big{(}S_{n-1,\lambda-\ell}^{++}\big{)},$
(17)

as $\rho(S_{n-1,\lambda-\ell}^{+})\leq\rho(S_{n-1,\lambda-\ell}^{++}).$

Recall that $t,\ell\geq 2$ and $\lambda\geq 2\ell-1\geq 3$. We can easily
check that
$\sqrt{\lambda}-\frac{1}{\sqrt{\lambda}}>\sqrt{\lambda-\ell+\frac{1}{4(\lambda-\ell)}}.$
By Lemma 5.1 (ii), we further have

$\displaystyle\sqrt{\lambda n}-\frac{n}{\sqrt{\lambda
n}}>\sqrt{\Big{(}\lambda-\ell+\frac{1}{4(\lambda-\ell)}\Big{)}n}\geq\rho(S_{n,\lambda-\ell}^{++})>\rho(S_{n-1,\lambda-\ell}^{++}).$
(18)

On the one hand, $u$ is a dominating vertex of $G$. Otherwise, there exists a
vertex $v$ not adjacent to $u$. Let $G^{*}$ be the graph obtained from $G$ by
adding the edge $uv$. Since $G^{*}-\\{u\\}=G-\\{u\\}$, $G^{*}-\\{u\\}$ is also
$(t-1)C_{2\ell}$-free, and thus $G^{*}$ is $tC_{2\ell}$-free. However,
$G\subset G^{*}$ indicates that $\rho(G)<\rho(G^{*})$, contradicting the fact
that $G$ is extremal with respect to $spex(n,tC_{2\ell})$.

On the other hand, notice that $S_{n,\lambda}^{+}$ is $tC_{2\ell}$-free, then
$\rho(G)\geq\rho(S_{n,\lambda}^{+})$, and so $\rho(G)\geq\sqrt{\lambda n}$ by
Lemma 5.1 (i). Since $u$ is a dominating vertex of $G$, one can see $G\cong
K_{1}+(G-\\{u\\})$. Combining $\rho(G)\geq\sqrt{\lambda n}$ and (18) with
Lemma 5.2, we have

$\rho\big{(}G-\\{u\\}\big{)}\geq\rho(G)-\frac{n-1}{\rho(G)}\geq\sqrt{\lambda
n}-\frac{n}{\sqrt{\lambda n}}>\rho\big{(}S_{n-1,\lambda-\ell}^{++}\big{)},$

which contradicts (17). Therefore, the lemma holds. ∎

Choose $u\in V(G)$ arbitrarily. By Lemma 5.3, $G-\\{u\\}$ contains $t-1$
disjoint ${2\ell}$-cycles, say $C^{1},\dots,C^{t-1}$. Let
$V^{\prime}=\cup_{j=1}^{t-1}V(C^{j})$ and $G^{\prime}=G-V^{\prime}$. Then
$G^{\prime}$ is $C_{2\ell}$-free. Set $N_{i}^{\prime}(u)=N_{i}(u)\setminus
V^{\prime}$ for $i\in\\{1,2\\}$. Clearly, $G^{\prime}[N_{1}^{\prime}(u)]$ is
$P_{2\ell-1}$-free. By Lemma 2.5,
$e(N_{1}^{\prime}(u))\leq(\ell-\frac{3}{2})|N_{1}^{\prime}(u)|\leq(\ell-\frac{3}{2})|N_{1}(u)|$
and so

$\displaystyle e\big{(}N_{1}(u)\big{)}$ $\displaystyle\leq$ $\displaystyle
e\big{(}N_{1}^{\prime}(u)\big{)}+|N_{1}(u)\cap
V^{\prime}||N_{1}(u)|\leq\Big{(}\ell-\frac{3}{2}+2\ell(t-1)\Big{)}|N_{1}(u)|$
(19) $\displaystyle\leq$
$\displaystyle\Big{(}2\lambda-\frac{3}{2}\Big{)}|N_{1}(u)|,$

as $\ell\geq 2$ and $\lambda=\ell t-1$. Furthermore, let $W_{0}$ be an
arbitrary subset of $V(G)$. Then, the bipartite subgraph
$G[N_{1}^{\prime}(u),N_{2}^{\prime}(u)\cap W_{0}]$ is $P_{2\ell+1}$-free
(otherwise, we can find a $P_{2\ell-1}$ with both endpoints in
$N_{1}^{\prime}(u)$ and thus a $C_{2\ell}$ in $G^{\prime}$). By Lemma 2.5,
$e(N_{1}^{\prime}(u),N_{2}^{\prime}(u)\cap
W_{0})\leq(\ell-\frac{1}{2})(|N_{1}(u)|+|N_{2}(u)\cap W_{0}|).$ Since both
$N_{1}(u)\setminus N_{1}^{\prime}(u)$ and $(N_{2}(u)\cap
W_{0})\setminus(N_{2}^{\prime}(u)\cap W_{0})$ are subsets of $V^{\prime}$, we
have

$\displaystyle e\big{(}N_{1}(u),N_{2}(u)\cap W_{0}\big{)}$ $\displaystyle\leq$
$\displaystyle e\big{(}N_{1}^{\prime}(u),N_{2}^{\prime}(u)\cap
W_{0}\big{)}+|V^{\prime}|(|N_{1}(u)|+|N_{2}(u)\cap W_{0}|)$ (20)
$\displaystyle\leq$
$\displaystyle\Big{(}\ell-\frac{1}{2}+2\ell(t-1)\Big{)}(|N_{1}(u)|+|N_{2}(u)\cap
W_{0}|)$ $\displaystyle\leq$
$\displaystyle\Big{(}2\lambda-\frac{1}{2}\Big{)}\big{(}|N_{1}(u)|+|N_{2}(u)\cap
W_{0}|\big{)}.$

######  Lemma 5.4.

$\sqrt{\lambda n}\leq\rho(G)\leq\sqrt{6\lambda n}.$

###### Proof.

Recall that $S_{n,\lambda}^{+}$ is $tC_{2\ell}$-free. Then
$\rho(G)\geq\rho(S_{n,\lambda}^{+})$, and the lower bound follows from Lemma
5.1 (i). We then prove the upper bound. Note that

$\rho^{2}(G)x_{u^{*}}=\\!\\!\sum_{u\in N_{1}(u^{*})}\sum_{w\in
N_{1}(u)}\\!\\!x_{w}\leq|N_{1}(u^{*})|x_{u^{*}}+2e\big{(}N_{1}(u^{*})\big{)}x_{u^{*}}+e\big{(}N_{1}(u^{*}),N_{2}(u^{*})\big{)}x_{u^{*}}.$

Setting $u=u^{*}$ and $W_{0}=N_{2}(u^{*})$ in (19) and (20), we obtain
$\rho^{2}(G)\leq\big{(}6\lambda-\frac{5}{2}\big{)}n\leq 6\lambda n.$ ∎

In [24], Nikiforov studied an extremal problem on degree power, which is an
extension of Turán’s problem. He showed that $\sum_{u\in V(H)}d_{H}^{2}(u)\leq
2(\ell-1)e(H)+(\ell-1)(|H|-1)|H|$ for every $C_{2\ell}$-free graph $H$.
Inspired by this result, we obtain the following one on $tC_{2\ell}$-free
graphs.

######  Lemma 5.5.

We have $e(G)\leq\ell n^{1+\frac{1}{\ell}}$ and $\sum_{v\in
V(G)}d_{G}^{2}(v)<2\lambda n^{2}$.

###### Proof.

From the above definition of $G^{\prime}$, we know that
$|G^{\prime}|=n-2\ell(t-1)$ and $G^{\prime}$ is $C_{2\ell}$-free. By Lemma
2.6, we have

$e(G^{\prime})\leq
ex\big{(}n-2\ell(t-1),C_{2\ell}\big{)}\leq(\ell-1)(n-2\ell(t-1))^{1+\frac{1}{\ell}}+16(\ell-1)n.$

It follows that

$\displaystyle e(G)\leq e(G^{\prime})+\sum_{v\in V^{\prime}}d_{G}(v)\leq
e(G^{\prime})+2\ell(t-1)n\leq\ell n^{1+\frac{1}{\ell}}.$ (21)

Hence, the first statement holds. For an arbitrary vertex $u\in V(G)$,

$\sum_{v\in
N_{1}(u)}d_{G}(v)=|N_{1}(u)|+2e\big{(}N_{1}(u)\big{)}+e\big{(}N_{1}(u),N_{2}(u)\big{)}.$

Combining with (19) and (20), where $W_{0}$ is defined as $N_{2}(u)$, we get
that

$\sum_{v\in
N_{1}(u)}d_{G}(v)<(4\lambda-2)|N_{1}(u)|+\Big{(}2\lambda-\frac{1}{2}\Big{)}n.$

Summing the above inequality over all vertices $u\in V(G)$ and using (21), we
obtain

$\displaystyle\sum_{u\in V(G)}\sum_{v\in N_{1}(u)}d_{G}(v)$ $\displaystyle<$
$\displaystyle(4\lambda-2)\sum_{u\in
V(G)}d_{G}(u)+\Big{(}2\lambda-\frac{1}{2}\Big{)}n^{2}$ $\displaystyle=$
$\displaystyle(8\lambda-4)e(G)+\Big{(}2\lambda-\frac{1}{2}\Big{)}n^{2}$
$\displaystyle<$ $\displaystyle 2\lambda n^{2}.$

Observe that $\sum_{v\in V(G)}d_{G}^{2}(v)=\sum_{u\in V(G)}\sum_{v\in
N_{1}(u)}d_{G}(v).$ The second statement follows. ∎

Choose a positive constant $\eta<\frac{1}{20000\lambda^{5}}$, and define
$W=\\{u\in V(G)~{}|~{}x_{u}\geq\eta x_{u^{*}}\\}.$ We shall give an upper
bound for $|W|$ and a lower bound for degrees of vertices in $W$ (see Lemmas
5.8 and 5.9). However, we are in trouble when we deal with the case $\ell=2$.
Hence, we have to prove an extra structural property (see Lemma 5.6).

######  Lemma 5.6.

For $\ell=2$, we have $\Delta(G)\geq(1-\frac{\eta}{40\lambda})n$.

###### Proof.

Set $\alpha=1-\frac{\eta}{40\lambda}$ and suppose to the contrary that
$\Delta(G)<\alpha n$. Specially, we have $d_{G}(u^{*})<\alpha n$. By Lemma
5.3, $G-\\{u^{*}\\}$ contains $t-1$ disjoint quadrilaterals
$C^{1},\dots,C^{t-1}$. Given an arbitrary $i\in\\{1,2,\dots,t-1\\}$, we assume
that $V(C^{i})=\\{u_{ij}~{}|~{}j=1,2,3,4\\}$. We then define
$M_{i}=\\{u_{ij_{1}},u_{ij_{2}}\\}$ if there exist two distinct vertices
$u_{ij_{1}},u_{ij_{2}}\in V(C^{i})$ with $|N_{1}(u_{ij_{1}})\cap
N_{1}(u_{ij_{2}})|\geq(1-\alpha)n$, and $M_{i}=V(C^{i})$ otherwise.
Furthermore, let $M=\cup_{i=1}^{t-1}M_{i}$ and $G^{\prime}=G-M$.

If $M_{i}=\\{u_{ij_{1}},u_{ij_{2}}\\}$ for some $u_{ij_{1}},u_{ij_{2}}\in
V(C^{i})$, then $e\big{(}M_{i},V(G^{\prime})\big{)}\leq
d_{G}(u_{ij_{1}})+d_{G}(u_{ij_{2}})<2\alpha n$. If $M_{i}=V(C^{i})$, then

$e\big{(}M_{i},V(G^{\prime})\big{)}\leq\Big{|}\cup_{j=1}^{4}N_{1}(u_{ij})\Big{|}+\\!\\!\sum_{1\leq
j_{1}<j_{2}\leq 4}\Big{|}N_{1}(u_{ij_{1}})\cap
N_{1}(u_{ij_{2}})\Big{|}<n+6(1-\alpha)n<2\alpha n,$

which the last inequality follows from $a>\frac{7}{8}.$ Hence, we always have

$\displaystyle
e\big{(}M,V(G^{\prime})\big{)}=\sum_{i=1}^{t-1}e\big{(}M_{i},V(G^{\prime})\big{)}<2(t-1)\alpha
n.$ (22)

Recall that $G^{\prime}=G-M=G-\cup_{i=1}^{t-1}M_{i}$. We will see that
$G^{\prime}$ is $C_{4}$-free. Otherwise, let ${\widetilde{C}}^{t}$ be a
4-cycle in $G^{\prime}$. If $M_{1}=V(C^{1})$, then we define a 4-cycle
${\widetilde{C}}^{1}=C^{1}$, where $V({\widetilde{C}}^{1})\cap
V({\widetilde{C}}^{t})=\varnothing$ obiviously. If
$M_{1}=\\{u_{1j_{1}},u_{1j_{2}}\\}$ for some $u_{1j_{1}},u_{1j_{2}}\in
V(C^{1})$, then $|N_{1}(u_{1j_{1}})\cap N_{1}(u_{1j_{2}})|\geq(1-\alpha)n$,
and thus there exists a 4-cycle
${\widetilde{C}}^{1}=u_{1j_{1}}v_{1}u_{1j_{2}}w_{1}u_{1j_{1}}$ such that
$v_{1},w_{1}\notin M\cup V({\widetilde{C}}^{t}).$ Similarly, if
$M_{2}=V(C^{2})$, then we define ${\widetilde{C}}^{2}=C^{2}$; otherwise,
$M_{2}=\\{u_{2j_{1}},u_{2j_{2}}\\}$, then we can find a 4-cycle
${\widetilde{C}}^{2}=u_{2j_{1}}v_{2}u_{2j_{2}}w_{2}u_{2j_{1}}$ such that
$v_{2},w_{2}\notin M\cup V({\widetilde{C}}^{1})\cup V({\widetilde{C}}^{t}).$
Repeating the above steps, we obtain a sequence of disjoint 4-cycles
${\widetilde{C}}^{1},\cdots,{\widetilde{C}}^{t-1}$ such that
$V({\widetilde{C}}^{i})\cap V(\widetilde{C}^{t})=\varnothing$ for $1\leq i\leq
t-1$. Consequently, we find $t$ disjoint 4-cycles in $G$, a contradiction.
Therefore, $G^{\prime}$ is $C_{4}$-free.

We know that

$\displaystyle\rho^{2}(G)x_{u^{*}}=\sum_{v\in N_{1}(u^{*})}\sum_{w\in
N_{1}(v)}x_{w}.$ (23)

In the following, we distinguish (23) into the following three cases.

Case (i) $v,w\in V(G^{\prime})$. Let $\widetilde{N}_{i}(u^{*})$ be the set of
vertices at distance $i$ from $u^{*}$ in $G^{\prime}$. Then
$\widetilde{N}_{i}(u^{*})\subseteq N_{i}(u^{*})$ for $i\in\\{1,2\\}$ as
$G^{\prime}$ is an induced subgraph of $G$. We evaluate the following term.

$\sum_{v\in\widetilde{N}_{1}(u^{*})}\sum_{w\in\widetilde{N}_{1}(v)}x_{w}=\sum_{v\in\widetilde{N}_{1}(u^{*})}\Big{(}x_{u^{*}}+\\!\\!\\!\\!\sum_{w\in\widetilde{N}_{1}(v)\cap\widetilde{N}_{1}(u^{*})}x_{w}+\\!\\!\\!\\!\sum_{w\in\widetilde{N}_{1}(v)\cap\widetilde{N}_{2}(u^{*})}x_{w}\Big{)}.$

Since $G^{\prime}$ is $C_{4}$-free, $G^{\prime}[\widetilde{N}_{1}(u^{*})]$ is
$P_{3}$-free, that is,
$\Delta\big{(}G^{\prime}[\widetilde{N}_{1}(u^{*})]\big{)}\leq 1$. Thus

$\sum_{v\in\widetilde{N}_{1}(u^{*})}\sum_{w\in\widetilde{N}_{1}(v)\cap\widetilde{N}_{1}(u^{*})}x_{w}\leq\sum_{v\in\widetilde{N}_{1}(u^{*})}x_{v}\leq\sum_{v\in
N_{1}(u^{*})}x_{v}=\rho(G)x_{u^{*}}.$

Moreover, any two vertices in $\widetilde{N}_{1}(u^{*})$ have no common
neighbors in $\widetilde{N}_{2}(u^{*})$, which implies that
$e\big{(}\widetilde{N}_{1}(u^{*}),\widetilde{N}_{2}(u^{*})\big{)}=|\widetilde{N}_{2}(u^{*})|$.
It follows that

$\sum_{v\in\widetilde{N}_{1}(u^{*})}\sum_{w\in\widetilde{N}_{1}(v)\cap\widetilde{N}_{2}(u^{*})}x_{w}\leq
e\big{(}\widetilde{N}_{1}(u^{*}),\widetilde{N}_{2}(u^{*})\big{)}x_{u^{*}}=|\widetilde{N}_{2}(u^{*})|x_{u^{*}}.$

Combining above three inequalities, we obtain

$\displaystyle\sum_{v\in\widetilde{N}_{1}(u^{*})}\sum_{w\in\widetilde{N}_{1}(v)}x_{w}\leq\big{(}|\widetilde{N}_{1}(u^{*})|+\rho(G)+|\widetilde{N}_{2}(u^{*})|\big{)}x_{u^{*}}<(\rho(G)+n-|M|\big{)}x_{u^{*}}.$
(24)

Case (ii) $v\in V(G)$ and $w\in M$. We shall evaluate $\sum_{v\in
N_{1}(u^{*})}\sum_{w\in N_{1}(v)\cap M}x_{w}.$ Note that
$N_{1}(u^{*})\setminus M=\widetilde{N}_{1}(u^{*}).$ On the one hand,
$\sum_{v\in N_{1}(u^{*})\setminus M}\sum_{w\in N_{1}(v)\cap M}x_{w}\leq
e\big{(}\widetilde{N}_{1}(u^{*}),M\big{)}x_{u^{*}}.$ On the other hand,

$\displaystyle\sum_{v\in N_{1}(u^{*})\cap M}\sum_{w\in N_{1}(v)\cap
M}x_{w}\leq 2e(M)x_{u^{*}}\leq 2\binom{|M|}{2}x_{u^{*}}<(1-\alpha)nx_{u^{*}}.$

Thus we have

$\displaystyle\sum_{v\in N_{1}(u^{*})}\sum_{w\in N_{1}(v)\cap
M}x_{w}<\Big{(}e\big{(}\widetilde{N}_{1}(u^{*}),M\big{)}+(1-\alpha)n\Big{)}x_{u^{*}}.$
(25)

Case (iii) $v\in M$ and $w\in V(G^{\prime})$. We shall calculate $\sum_{v\in
N_{1}(u^{*})\cap M}\sum_{w\in N_{1}(v)\cap V(G^{\prime})}x_{w}.$ Now set
$\widetilde{N}_{2^{+}}(u^{*})=V(G^{\prime})\setminus\big{(}\\{u^{*}\\}\cup\widetilde{N}_{1}(u^{*})\big{)}.$
We can observe that

$\displaystyle\sum_{v\in N_{1}(u^{*})\cap M}\sum_{w\in N_{1}(v)\cap
V(G^{\prime})}x_{w}$ $\displaystyle=$ $\displaystyle\sum_{v\in
N_{1}(u^{*})\cap M}\Big{(}x_{u^{*}}+\\!\\!\\!\\!\sum_{w\in
N_{1}(v)\cap\widetilde{N}_{1}(u^{*})}\\!\\!\\!\\!x_{w}+\\!\\!\\!\\!\sum_{w\in
N_{1}(v)\cap\widetilde{N}_{2^{+}}(u^{*})}\\!\\!\\!\\!x_{w}\Big{)}$ (26)
$\displaystyle\leq$ $\displaystyle\sum_{v\in
M}\Big{(}x_{u^{*}}+\\!\\!\\!\\!\sum_{w\in\widetilde{N}_{1}(u^{*})}\\!\\!\\!\\!x_{w}+\\!\\!\\!\\!\sum_{w\in
N_{1}(v)\cap\widetilde{N}_{2^{+}}(u^{*})}\\!\\!\\!\\!x_{w}\Big{)}$
$\displaystyle\leq$
$\displaystyle|M|\big{(}1+\rho(G)\big{)}x_{u^{*}}+e\big{(}\widetilde{N}_{2^{+}}(u^{*}),M\big{)}x_{u^{*}}.$

Summing (24), (25) and (26) into (23), we obtain

$\rho^{2}(G)<(|M|+1)\rho(G)+(2-\alpha)n+e\big{(}V(G^{\prime}),M\big{)}.$

Note that $|M|=4(t-1)$, and by Lemma 5.4, $\rho(G)\leq\sqrt{6\lambda n}$.
Thus, $(|M|+1)\rho(G)\leq(4t-3)\sqrt{6\lambda n}<(1-\alpha)n$. Moreover,
$e\big{(}V(G^{\prime}),M\big{)}<2(t-1)\alpha n$ by (22). Consequently,

$\rho^{2}(G)<\big{(}3+(2t-4)\alpha\big{)}n\leq(2t-1)n,$

as $t\geq 2$ and $\alpha=1-\frac{\eta}{40\lambda}<1$. However, by Lemma 5.4 we
have $\rho^{2}(G)\geq\lambda n=(\ell t-1)n\geq(2t-1)n,$ a contradiction,
Therefore, $\Delta(G)\geq\alpha n$, completing the proof. ∎

######  Lemma 5.7.

Let $W^{\prime}=\\{u\in V(G)~{}|~{}x_{u}\geq\frac{\eta}{5}x_{u^{*}}\\}$. Then
$|W^{\prime}|\leq\frac{\eta}{20\lambda}n$.

###### Proof.

We first consider the case $\ell\geq 3$. By Lemma 5.4,
$\rho(G)\geq\sqrt{\lambda n}$. Hence,

$\sqrt{\lambda n}\frac{\eta}{5}x_{u^{*}}\leq\sqrt{\lambda
n}x_{u}\leq\rho(G)x_{u}=\sum_{v\in N_{1}(u)}x_{v}\leq d_{G}(u)x_{u^{*}}$

for each $u\in W^{\prime}$. Summing this inequality over all vertices $u\in
W^{\prime}$, we obtain

$\displaystyle|W^{\prime}|\sqrt{\lambda
n}\frac{\eta}{5}x_{u^{*}}\leq\sum_{u\in
W^{\prime}}d_{G}(u)x_{u^{*}}\leq\sum_{u\in V(G)}d_{G}(u)x_{u^{*}}\leq
2e(G)x_{u^{*}}.$ (27)

Combining (21) and (27), we get $|W^{\prime}|\leq\frac{10\ell
n^{1+\frac{1}{\ell}}}{\sqrt{\lambda n}\eta}\leq\frac{\eta}{20\lambda}n$ for
$n$ large enough.

Now, it remains the case $\ell=2$. By Lemma 5.6, there exists a vertex
$v^{*}\in V(G)$ with $d_{G}(v^{*})\geq(1-\frac{\eta}{40\lambda})n$. Hence,

$|W^{\prime}\setminus N_{1}(v^{*})|\leq|V(G)\setminus
N_{1}(v^{*})|=n-d_{G}(v^{*})\leq\frac{\eta}{40\lambda}n.$

Let $W^{*}=\\{v\in
N_{1}(v^{*})~{}|~{}x_{v}\geq\sqrt{6\lambda}n^{-0.4}x_{u^{*}}\\}$. Note that
$\rho(G)\leq\sqrt{6\lambda n}$ by Lemma 5.4. Thus

$\big{|}W^{*}\big{|}\sqrt{6\lambda}n^{-0.4}x_{u^{*}}\leq\sum_{v\in
N_{1}(v^{*})}x_{v}=\rho(G)x_{v^{*}}\leq\sqrt{6\lambda n}x_{u^{*}},$

yielding $|W^{*}|\leq n^{0.9}\leq\frac{\eta}{40\lambda}n$. Since
$\frac{\eta}{5}x_{u^{*}}>\sqrt{6\lambda}n^{-0.4}x_{u^{*}}$, we have
$W^{\prime}\cap N_{1}(v^{*})\subseteq W^{*}$, and so $|W^{\prime}\cap
N_{1}(v^{*})|\leq|W^{*}|\leq\frac{\eta}{40\lambda}n$. Combining
$|W^{\prime}\setminus N_{1}(v^{*})|\leq\frac{\eta}{40\lambda}n$ gives
$|W^{\prime}|\leq\frac{\eta}{20\lambda}n,$ as claimed. ∎

######  Lemma 5.8.

$|W|\leq\frac{128\lambda^{3}}{\eta^{2}}$.

###### Proof.

We first prove that $d_{G}(u)>\frac{\eta}{8\lambda}n$ for each $u\in W$.
Suppose to the contrary that there exists a vertex $\widetilde{u}\in W$ with
$d_{G}(\widetilde{u})\leq\frac{\eta}{8\lambda}n$. Then
$x_{\widetilde{u}}\geq\eta x_{u^{*}}$ as $\widetilde{u}\in W$, and by Lemma
5.4 $\rho(G)\geq\sqrt{\lambda n}$. Thus we have

$\displaystyle\eta\lambda
nx_{u^{*}}\leq\rho^{2}(G)x_{\widetilde{u}}=|N_{1}(\widetilde{u})|x_{\widetilde{u}}+\sum_{u\in
N_{1}(\widetilde{u})}\\!\\!\\!d_{N_{1}(\widetilde{u})}(u)x_{u}+\\!\\!\\!\sum_{u\in
N_{2}(\widetilde{u})}\\!\\!\\!d_{N_{1}(\widetilde{u})}(u)x_{u}.$ (28)

In view of (19), we have
$e(N_{1}(\widetilde{u}))\leq(2\lambda-\frac{3}{2})d_{G}(\widetilde{u})$. Note
that $|N_{1}(\widetilde{u})|\leq\frac{\eta}{8\lambda}n$. Thus,

$|N_{1}(\widetilde{u})|x_{\widetilde{u}}+\\!\\!\\!\sum_{u\in
N_{1}(\widetilde{u})}\\!\\!\\!d_{N_{1}(\widetilde{u})}(u)x_{u}\leq\big{(}|N_{1}(\widetilde{u})|+2e(N_{1}(\widetilde{u}))\big{)}x_{u^{*}}\leq(4\lambda-2)|N_{1}(\widetilde{u})|x_{u^{*}}\leq\frac{1}{2}\eta
nx_{u^{*}}.$

Combining the above inequality with (28), we obtain

$\displaystyle\sum_{u\in
N_{2}(\widetilde{u})}d_{N_{1}(\widetilde{u})}(u)x_{u}\geq(\lambda-\frac{1}{2})\eta
nx_{u^{*}}.$ (29)

Now, setting $u=\widetilde{u}$ and $W_{0}=W^{\prime}$ in (20), we have

$e\big{(}N_{1}(\widetilde{u}),N_{2}(\widetilde{u})\cap
W^{\prime}\big{)}\leq\big{(}2\lambda-\frac{1}{2}\big{)}\big{(}|N_{1}(\widetilde{u})|+|N_{2}(\widetilde{u})\cap
W^{\prime}|\big{)}\leq
2\lambda\big{(}|N_{1}(\widetilde{u})|+|W^{\prime}|\big{)}.$

Since $|N_{1}(\widetilde{u})|\leq\frac{\eta}{8\lambda}n$, and
$|W^{\prime}|\leq\frac{\eta}{20\lambda}n$ by Lemma 5.7, it follows that

$\displaystyle\sum_{u\in N_{2}(\widetilde{u})\cap
W^{\prime}}d_{N_{1}(\widetilde{u})}(u)x_{u}\leq
e\big{(}N_{1}(\widetilde{u}),N_{2}(\widetilde{u})\cap
W^{\prime}\big{)}x_{u^{*}}\leq\frac{7}{20}\eta nx_{u^{*}}.$ (30)

Note that $x_{u}<\frac{\eta}{5}x_{u^{*}}$ for each $u\in V(G)\setminus
W^{\prime}$. Setting $u=\widetilde{u}$ and $W_{0}=V(G)\setminus W^{\prime}$ in
(20), we get $e\big{(}N_{1}(\widetilde{u}),N_{2}(\widetilde{u})\setminus
W^{\prime}\big{)}\leq(2\lambda-\frac{1}{2})n.$ Consequently,

$\sum_{u\in N_{2}(\widetilde{u})\setminus
W^{\prime}}d_{N_{1}(\widetilde{u})}(u)x_{u}\leq
e\big{(}N_{1}(\widetilde{u}),N_{2}(\widetilde{u})\setminus
W^{\prime}\big{)}\frac{\eta}{5}x_{u^{*}}\leq(2\lambda-\frac{1}{2})n\frac{\eta}{5}x_{u^{*}}.$

Combining (30) gives

$\sum_{u\in
N_{2}(\widetilde{u})}d_{N_{1}(\widetilde{u})}(u)x_{u}\leq\Big{(}\frac{7}{20}+\frac{4\lambda-1}{10}\Big{)}\eta
nx_{u^{*}}<(\lambda-\frac{1}{2})\eta nx_{u^{*}}$

as $\lambda=\ell t-1>\frac{5}{4}$, contradicting (29). Therefore,
$d_{G}(u)>\frac{\eta}{8\lambda}n$ for each $u\in W$. It follows that
$\sum_{u\in V(G)}d_{G}^{2}(u)\geq\sum_{u\in
W}d_{G}^{2}(u)\geq|W|\big{(}\frac{\eta}{8\lambda}n\big{)}^{2}$. Moreover,
$\sum_{u\in V(G)}d_{G}^{2}(u)<2\lambda n^{2}$ by Lemma 5.5. Thus,
$|W|\leq\frac{128\lambda^{3}}{\eta^{2}}$, as claimed. ∎

######  Lemma 5.9.

For each $u\in W$, we have
$d_{G}(u)\geq\big{(}\frac{x_{u}}{x_{u^{*}}}-20\eta\big{)}n$.

###### Proof.

Let $u$ be an arbitrary vertex in $W$. For convenience, we use $W_{i}$ and
$\overline{W_{i}}$ instead of $N_{i}(u)\cap W$ and $N_{i}(u)\setminus W$,
respectively. In view of (19) and (20), we have
$\max\\{e(N_{1}(u)),e(N_{1}(u),N_{2}(u))\\}\leq 2\lambda n$. Since
$W_{i}\cup\overline{W_{i}}=N_{i}(u)$ for $i\in\\{1,2\\}$, we can see that

$\displaystyle\max\\{e(\overline{W_{1}}),e(W_{1},\overline{W_{1}}),e(W_{1},\overline{W_{2}}),e(\overline{W_{1}},\overline{W_{2}})\\}\leq
2\lambda n.$ (31)

Recall that $\rho(G)\geq\sqrt{\lambda n}$. We also have

$\displaystyle\lambda nx_{u}\leq\rho^{2}(G)x_{u}=\sum_{v\in
N_{1}(u)}\sum_{w\in N_{1}(v)}x_{w}=|N_{1}(u)|x_{u}+\sum_{v\in
N_{1}(u)}\sum_{w\in N_{1}(v)\setminus\\{u\\}}x_{w}.$ (32)

Note that $N_{1}(u)=W_{1}\cup\overline{W_{1}}$ and for any $v\in N_{1}(u)$,

$N_{1}(v)\setminus\\{u\\}=N_{1}(v)\cap\big{(}N_{1}(u)\cup
N_{2}(u)\big{)}=N_{1}(v)\cap(W_{1}\cup\overline{W_{1}}\cup
W_{2}\cup\overline{W_{2}}).$

We now calculate the term $\sum_{v\in N_{1}(u)}\sum_{w\in
N_{1}(v)\setminus\\{u\\}}x_{w}$ in (32). We first consider the case $v\in
W_{1}$. Note that $x_{w}\leq x_{u^{*}}$ for $w\in W_{1}\cup W_{2}$ and
$x_{w}\leq\eta x_{u^{*}}$ for $w\in\overline{W_{1}}\cup\overline{W_{2}}$.
Thus,

$\sum_{v\in W_{1}}\sum_{w\in
N_{1}(v)\setminus\\{u\\}}\\!\\!\\!x_{w}\leq\big{(}2e(W_{1})+e(W_{1},W_{2})\big{)}x_{u^{*}}+\big{(}e(W_{1},\overline{W_{1}})+e(W_{1},\overline{W_{2}})\big{)}\eta
x_{u^{*}}.$

On the one hand, $|W|<\frac{128\lambda^{3}}{\eta^{2}}$ by Lemma 5.8. Note that
$W_{1}\cup W_{2}\subseteq W$. Thus, $2e(W_{1})+e(W_{1},W_{2})\leq
2\binom{|W|}{2}\leq\eta\lambda n.$ On the other hand, we have
$e(W_{1},\overline{W_{1}})+e(W_{1},\overline{W_{2}})\leq 4\lambda n$ by (31).
Therefore,

$\displaystyle\sum_{v\in W_{1}}\sum_{w\in N_{1}(v)\setminus\\{u\\}}x_{w}\leq
5\lambda\eta nx_{u^{*}}.$ (33)

Now, we consider the case $v\in\overline{W_{1}}$. We can see that

$\displaystyle\sum_{v\in\overline{W_{1}}}\sum_{w\in
N_{1}(v)\setminus\\{u\\}}x_{w}$ $\displaystyle\leq$
$\displaystyle\sum_{v\in\overline{W_{1}}}\sum_{w\in N_{1}(v)\cap(W_{1}\cup
W_{2})}x_{w}+\sum_{v\in\overline{W_{1}}}\sum_{w\in
N_{1}(v)\cap(\overline{W_{1}}\cup\overline{W_{2}})}x_{w}$ (34)
$\displaystyle\leq$ $\displaystyle e(\overline{W_{1}},W_{1}\cup
W_{2})x_{u^{*}}+\big{(}2e(\overline{W_{1}})+e(\overline{W_{1}},\overline{W_{2}})\big{)}\eta
x_{u^{*}}$ $\displaystyle\leq$ $\displaystyle e(\overline{W_{1}},W_{1}\cup
W_{2})x_{u^{*}}+6\lambda\eta nx_{u^{*}},$

where the last inequality follows from (31). In the following, we shall
evaluate $e(\overline{W_{1}},W_{1}\cup W_{2})$. Since $W_{1}\cup
W_{2}\subseteq W$, it suffices to calculate $e(\overline{W_{1}},W)$.

Let $\overline{W_{1}}^{\prime}$ be the subset of $\overline{W_{1}}$ in which
each vertex has at least $\lambda$ neighbors in $W_{1}\cup W_{2}$. If
$|W_{1}\cup W_{2}|\leq\lambda-1$, then $|\overline{W_{1}}^{\prime}|=0$. If
$|W_{1}\cup W_{2}|\geq\lambda$, then we claim that
$|\overline{W_{1}}^{\prime}|<(\lambda+1)\binom{|W_{1}\cup W_{2}|}{\lambda}$.
Otherwise, since there are only $\binom{|W_{1}\cup W_{2}|}{\lambda}$ options
for all vertices in $\overline{W_{1}}^{\prime}$ to choose a set of $\lambda$
neighbors from $W_{1}\cup W_{2}$, we can find $\lambda$ vertices in $W_{1}\cup
W_{2}$ with at least $|\overline{W_{1}}^{\prime}|/\binom{|W_{1}\cup
W_{2}|}{\lambda}\geq\lambda+1$ common neighbors in
$\overline{W_{1}}^{\prime}$. Moreover, note that $u\notin W_{1}\cup W_{2}$ and
$\overline{W_{1}}^{\prime}\subseteq\overline{W_{1}}\subseteq N_{1}(u)$. Hence,
$G$ contains a copy of $K_{\lambda+1,\lambda+1}$, and thus $t$ disjoint
$2\ell$-cycles, a contradiction. Therefore, we always have
$|\overline{W_{1}}^{\prime}|<(\lambda+1)\binom{|W_{1}\cup
W_{2}|}{\lambda}\leq(\lambda+1)\binom{|W|}{\lambda}$.

By Lemma 5.8, $|W|$ is constant. Now $|\overline{W_{1}}^{\prime}|$ is also
constant. Thus, $|\overline{W_{1}}^{\prime}||W_{1}\cup W_{2}|\leq 9\lambda\eta
n$. Moreover, from the definition of $\overline{W_{1}}^{\prime}$ we know
$e(\overline{W_{1}}\setminus\overline{W_{1}}^{\prime},W_{1}\cup
W_{2})\leq(\lambda-1)|\overline{W_{1}}\setminus\overline{W_{1}}^{\prime}|.$
Thus

$\displaystyle e(\overline{W_{1}},W_{1}\cup W_{2})\leq
e(\overline{W_{1}}^{\prime},W_{1}\cup
W_{2})+e(\overline{W_{1}}\setminus\overline{W_{1}}^{\prime},W_{1}\cup
W_{2})\leq 9\lambda\eta n+(\lambda-1)|N_{1}(u)|.$ (35)

Back to (34), we obtain $\sum_{v\in\overline{W_{1}}}\sum_{w\in
N_{1}(v)\setminus\\{u\\}}x_{w}\leq\big{(}15\lambda\eta
n+(\lambda-1)|N_{1}(u)|\big{)}x_{u^{*}}.$ Combining this with (32) and (33),
we get that

$\lambda nx_{u}\leq|N_{1}(u)|x_{u}+20\lambda\eta
nx_{u^{*}}+(\lambda-1)|N_{1}(u)|x_{u^{*}}\leq\big{(}20\lambda\eta
n+\lambda|N_{1}(u)|\big{)}x_{u^{*}},$

which yields $|N_{1}(u)|\geq\big{(}\frac{x_{u}}{x_{u^{*}}}-20\eta\big{)}n$, as
desired. ∎

Now, we define $W^{\prime\prime}=\\{u\in V(G)~{}|~{}x_{u}\geq
5000\lambda^{4}\eta x_{u^{*}}\\}$. Recall that
$\eta<\frac{1}{20000\lambda^{5}}$ and $W=\\{u\in V(G)~{}|~{}x_{u}\geq\eta
x_{u^{*}}\\}$. Clearly, $u^{*}\in W^{\prime\prime}$ and
$W^{\prime\prime}\subseteq W.$

######  Lemma 5.10.

For every $v\in W^{\prime\prime}$, we have
$x_{v}\geq(1-\frac{1}{200\lambda^{3}})x_{u^{*}}$ and
$d_{G}(v)\geq(1-\frac{1}{100\lambda^{3}})n$. Moreover, we have
$|W^{\prime\prime}|=\lambda$.

###### Proof.

Suppose to the contrary that there exists $v_{0}\in W^{\prime\prime}$ with
$x_{v_{0}}<(1-\frac{1}{200\lambda^{3}})x_{u^{*}}$. We use $W_{i}$ and
$\overline{W_{i}}$ to denote $N_{i}(u^{*})\cap W$ and $N_{i}(u^{*})\setminus
W$, respectively. We first prove that $|\overline{W_{1}}\cap N_{1}(v_{0})|\geq
4000\lambda^{4}\eta n$. By Lemma 5.9, we have

$|N_{1}(u^{*})|\geq(1-20\eta)n~{}~{}~{}\text{and}~{}~{}~{}|N_{1}(v_{0})|\geq(5000\lambda^{4}\eta-20\eta)n,$

as $x_{v_{0}}\geq 5000\lambda^{4}\eta nx_{u^{*}}$. Moreover, by Lemma 5.8, we
have $|W|\leq\frac{128\lambda^{3}}{\eta^{2}}\leq 10\eta n$. Hence,
$|\overline{W_{1}}|=|N_{1}(u^{*})\setminus W|\geq(1-30\eta)n,$ and so

$\displaystyle\big{|}\overline{W_{1}}\cap
N_{1}(v_{0})\big{|}\geq\big{|}\overline{W_{1}}\big{|}+\big{|}N_{1}(v_{0})\big{|}-n\geq(5000\lambda^{4}\eta-50\eta)n>4000\lambda^{4}\eta
n.$ (36)

In view of (36), $v_{0}$ has neighbors in $\overline{W_{1}}$. Then $v_{0}$ is
of distance at most two from $u^{*}$, that is, $v_{0}\in N_{1}(u^{*})\cup
N_{2}(u^{*})$. Note that $v_{0}\in W^{\prime\prime}\subseteq W$. Thus,
$v_{0}\in W_{1}\cup W_{2}$. Recall that
$x_{v_{0}}<(1-\frac{1}{200\lambda^{3}})x_{u^{*}}$. Now, setting $u=u^{*}$ in
(32)-(34), we can observe that

$\displaystyle\lambda nx_{u^{*}}\\!$ $\displaystyle\leq$
$\displaystyle\\!|N_{1}(u^{*})|x_{u^{*}}+11\lambda\eta
nx_{u^{*}}+e\big{(}\overline{W_{1}},(W_{1}\cup
W_{2})\setminus\\{v_{0}\\}\big{)}x_{u^{*}}+e\big{(}\overline{W_{1}},\\{v_{0}\\}\big{)}x_{v_{0}}$
$\displaystyle<$ $\displaystyle\\!|N_{1}(u^{*})|x_{u^{*}}+11\lambda\eta
nx_{u^{*}}+e\big{(}\overline{W_{1}},(W_{1}\cup
W_{2})\big{)}x_{u^{*}}-e\big{(}\overline{W_{1}},\\{v_{0}\\}\big{)}\frac{x_{u^{*}}}{200\lambda^{3}}.$

From (35) we know that $e(\overline{W_{1}},W_{1}\cup W_{2})\leq 9\lambda\eta
n+(\lambda-1)|N_{1}(u^{*})|.$ Thus,

$\lambda n\leq\lambda|N_{1}(u^{*})|+20\lambda\eta
n-\frac{e\big{(}\overline{W_{1}},\\{v_{0}\\}\big{)}}{200\lambda^{3}}<\lambda
n+20\lambda\eta
n-\frac{e\big{(}\overline{W_{1}},\\{v_{0}\\}\big{)}}{200\lambda^{3}}.$

Consequently, $e\big{(}\overline{W_{1}},\\{v_{0}\\}\big{)}<4000\lambda^{4}\eta
n,$ contradicting (36). Thus $x_{v}\geq(1-\frac{1}{200\lambda^{3}})x_{u^{*}}$
for $v\in W^{\prime\prime}$.

Recall that $\eta<\frac{1}{20000\lambda^{5}}$. Then by Lemma 5.9, we can see
that for each $v\in W^{\prime\prime}$,

$d_{G}(v)\geq\big{(}\frac{x_{v}}{x_{u^{*}}}-20\eta\big{)}n\geq\Big{(}1-\frac{1}{200\lambda^{3}}-20\eta\Big{)}n\geq\Big{(}1-\frac{1}{100\lambda^{3}}\Big{)}n.$

It remains to show $|W^{\prime\prime}|=\lambda$. We first suppose that
$|W^{\prime\prime}|\geq\lambda+1$. Note that every $v\in W^{\prime\prime}$ has
at most $\frac{n}{100\lambda^{3}}$ non-neighbors. It follows that any
$\lambda+1$ vertices in $W^{\prime\prime}$ have at least
$n-\frac{(\lambda+1)n}{100\lambda^{3}}\geq\lambda+1$ common neighbors. Thus,
$G$ contains $K_{\lambda+1,\lambda+1}$ as a subgraph. Recall that
$\lambda=\ell t-1$. Thus $G$ also contains $tC_{2\ell}$, a contradiction.
Therefore, $|W^{\prime\prime}|\leq\lambda$.

Next, suppose that $|W^{\prime\prime}|\leq\lambda-1$. Since $u^{*}\in
W^{\prime\prime}\setminus(W_{1}\cup W_{2})$, we have
$|W^{\prime\prime}\cap(W_{1}\cup W_{2})|\leq\lambda-2$. Moreover, recall that
$W_{i}\cup\overline{W_{i}}=N_{i}(u^{*})$ for $i\in\\{1,2\\}$, then

$\displaystyle e\big{(}\overline{W_{1}},(W_{1}\cup W_{2})\setminus
W^{\prime\prime}\big{)}\leq
e\big{(}\overline{W_{1}},W_{1}\big{)}+e\big{(}\overline{W_{1}},W_{2}\big{)}\leq
e(N_{1}(u^{*}))+e(N_{1}(u^{*}),N_{2}(u^{*})).$

Setting $u=u^{*}$ and $W_{0}=N_{2}(u^{*})$ in (19) and (20), we have
$e(N_{1}(u^{*}))+e(N_{1}(u^{*}),N_{2}(u^{*}))\leq(4\lambda-2)n,$ and thus
$e(\overline{W_{1}},(W_{1}\cup W_{2})\setminus
W^{\prime\prime})\leq(4\lambda-2)n.$ Furthermore, we shall note that
$x_{w}<5000\lambda^{4}\eta x_{u^{*}}$ for each $w\in(W_{1}\cup W_{2})\setminus
W^{\prime\prime}.$ Now, setting $u=u^{*}$ in (32)-(34) and dividing both sides
of (32) by $x_{u^{*}}$, we can see that

$\displaystyle\lambda n\\!$ $\displaystyle\leq$
$\displaystyle\\!|N_{1}(u^{*})|\\!+\\!11\lambda\eta
n\\!+\\!e\big{(}\overline{W_{1}},(W_{1}\cup W_{2})\cap
W^{\prime\prime}\big{)}\\!+\\!e\big{(}\overline{W_{1}},(W_{1}\cup
W_{2})\setminus W^{\prime\prime}\big{)}5000\lambda^{4}\eta$
$\displaystyle\leq$ $\displaystyle\\!n+11\lambda\eta
n+(\lambda-2)n+5000\lambda^{4}\eta(4\lambda-2)n$ $\displaystyle<$
$\displaystyle\\!\lambda n,$

as $\eta<\frac{1}{20000\lambda^{5}}$. This gives a contradiction. Therefore,
$|W^{\prime\prime}|=\lambda$. ∎

In the following, we complete the proof of Theorem 1.3.

###### Proof.

By Lemma 5.10, we see that $|W^{\prime\prime}|=\lambda=\ell t-1$ and every
vertex in $W^{\prime\prime}$ has at most $\frac{n}{100\lambda^{3}}$ non-
neighbors. Now, let $U$ be the subset of $V(G)\setminus W^{\prime\prime}$ in
which every vertex is a non-neighbor of some vertex in $W^{\prime\prime}$ and
$U^{\prime}=V(G)\setminus(W^{\prime\prime}\cup U)$. Then,
$G[W^{\prime\prime},U^{\prime}]\cong K_{|W^{\prime\prime}|,|U^{\prime}|}$.
Note that
$|U|\leq|W^{\prime\prime}|\frac{n}{100\lambda^{3}}=\frac{n}{100\lambda^{2}}$,
and thus $|U^{\prime}|\geq n-\lambda-\frac{n}{100\lambda^{2}}\geq\frac{n}{2}.$

We will see that $U=\varnothing$. Suppose to the contrary that
$U\neq\varnothing$. Given $u\in U$ arbitrarily. Then, $u$ has at most one
neighbor in $U^{\prime}$ (otherwise, $u$ has two neighbors $w_{1},w_{2}\in
U^{\prime}$, then $G[W^{\prime\prime},U^{\prime}]$ together with
$uw_{1},uw_{2}$ gives a copy of $tC_{2\ell}$, a contradiction). Moreover, by
the definition of $U$, $|N_{1}(u)\cap
W^{\prime\prime}|\leq|W^{\prime\prime}|-1=\lambda-1$. It follows that

$\displaystyle\sum_{w\in N_{1}(u)\cap(W^{\prime\prime}\cup
U^{\prime})}\\!\\!\\!\\!x_{w}=\\!\\!\sum_{w\in N_{1}(u)\cap
W^{\prime\prime}}\\!\\!x_{w}+\\!\\!\sum_{w\in N_{1}(u)\cap
U^{\prime}}\\!\\!x_{w}\leq(\lambda-1)x_{u^{*}}+5000\lambda^{4}\eta x_{u^{*}}.$
(37)

We now claim that
$\rho(G)x_{u}\geq(\lambda-\frac{1}{200\lambda^{2}})x_{u^{*}}$. Otherwise, let
$G^{*}$ be the graph obtained from $G$ by deleting all edges incident to $u$
and joining $u$ to all vertices in $W^{\prime\prime}$. Note that
$|U^{\prime}|\geq\frac{n}{2}$ and $N_{G^{*}}(u)\subseteq N_{G^{*}}(v)$ for any
$v\in U^{\prime}$. Then $G^{*}$ is $tC_{2\ell}$-free (otherwise,
$G^{*}-\\{u\\}$ contains $tC_{2\ell}$, and thus $G-\\{u\\}$ too, a
contradiction). Moreover,

$\rho(G^{*})-\rho(G)\geq
X^{T}\big{(}A(G^{*})-A(G)\big{)}X=2x_{u}\Big{(}\sum_{w\in
W^{\prime\prime}}x_{w}-\sum_{w\in N_{1}(u)}x_{w}\Big{)}.$

Note that $\sum_{w\in
W^{\prime\prime}}x_{w}\geq|W^{\prime\prime}|(1-\frac{1}{200\lambda^{3}})x_{u^{*}}=(\lambda-\frac{1}{200\lambda^{2}})x_{u^{*}}$
by Lemma 5.10, but $\sum_{w\in
N_{1}(u)}x_{w}=\rho(G)x_{u}<(\lambda-\frac{1}{200\lambda^{2}})x_{u^{*}}$ by
assumption. Thus, $\rho(G^{*})>\rho(G)$, a contradiction.

Now we have

$\Big{(}\lambda-\frac{1}{200\lambda^{2}}\Big{)}x_{u^{*}}\leq\rho(G)x_{u}=\\!\\!\sum_{w\in
N_{1}(u)\cap(W^{\prime\prime}\cup U^{\prime})}\\!\\!x_{w}+\\!\\!\sum_{w\in
N_{1}(u)\cap U}\\!\\!x_{w}.$

Combining (37) gives

$\frac{\sum_{w\in N_{1}(u)\cap
U}x_{w}}{\rho(G)x_{u}}\geq\frac{(\lambda-\frac{1}{200\lambda^{2}})x_{u^{*}}-(\lambda-1+5000\lambda^{4}\eta)x_{u^{*}}}{(\lambda-\frac{1}{200\lambda^{2}})x_{u^{*}}}\geq\frac{4}{5\lambda},$

as
$\eta<\frac{1}{20000\lambda^{5}}<\frac{1}{5000\lambda^{4}}(\frac{1}{5}-\frac{1}{200\lambda^{2}}+\frac{1}{250\lambda^{3}})$.
Thus, $\sum_{w\in N_{1}(u)\cap U}x_{w}\geq\frac{4}{5\lambda}\rho(G)x_{u}$.

Now consider the matrix $A^{\prime}=A(G[U])$ and the vector
$X^{\prime}=X|_{U}$ (the restriction of $X$ to $U$). We can observe that

$(A^{\prime}X^{\prime})_{u}=\sum_{w\in N_{1}(u)\cap
U}x_{w}\geq\frac{4}{5\lambda}\rho(G)x_{u}$

for each $u\in U$. Since $X$ is the Perron vector of $G$, $X^{\prime}$ is a
positive vector and thus
$A^{\prime}X^{\prime}\geq\frac{4}{5\lambda}\rho(G)X^{\prime}$ entrywise.
Moreover, $\rho(G)\geq\sqrt{\lambda n}$ by Lemma 5.4. Hence,

$\rho(G[U])\geq\frac{X^{\prime T}A^{\prime}X^{\prime}}{X^{\prime
T}X^{\prime}}\geq\frac{4}{5\lambda}\rho(G)\geq\frac{4}{5}\sqrt{\frac{n}{\lambda}},$

which also implies that $|U|=\Omega(\sqrt{n}).$ Since $G[U]$ is
$tC_{2\ell}$-free, we have $\rho(G[U])\leq\sqrt{6\lambda|U|}$ by Lemma 5.4.
Recall that $|U|\leq\frac{n}{100\lambda^{2}}$. It follows that

$\rho(G[U])\leq\sqrt{\frac{6\lambda
n}{100\lambda^{2}}}<\frac{4}{5}\sqrt{\frac{n}{\lambda}},$

a contradiction. Therefore, $U=\varnothing$.

$w_{1}$$w_{2}$$w_{l-2}$$w_{l-1}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{l}$$u_{l+1}$$w_{1}$$w_{2}$$w_{l-2}$$w_{l-1}$$u_{1}$$u_{2}$$u_{3}$$u_{l-1}$$u_{l}$$u_{l+1}$$W^{\prime\prime}$$U^{\prime}$$W^{\prime\prime}$$U^{\prime}$
Figure 1: A special $2\ell$-cycle in $G$.

Now we have $V(G)=W^{\prime\prime}\cup U^{\prime}$ and
$G[W^{\prime\prime},U^{\prime}]\cong K_{\lambda,n-\lambda}$. In the following,
we consider two cases of Theorem 1.3.

(i) $\ell=2$. Since $|W^{\prime\prime}|=\lambda=\ell t-1=2t-1$, we can see
that $G[U^{\prime}]$ is $P_{3}$-free (otherwise, we can find $tC_{4}$ in $G$).
Thus, $G[U^{\prime}]$ consists of independent edges and isolated vertices.
Since $G$ is extremal with respect to $spex(n,tC_{4})$, we know that $G$ is
edge-maximal, which implies that $W^{\prime\prime}$ is a $(2t-1)$-clique and
$G\cong S_{n,2t-1}^{++}$.

(ii) $\ell\geq 3$. Since $|W^{\prime\prime}|=\lambda=\ell t-1$, we will see
that $e(U^{\prime})\leq 1$. Otherwise, whether $G[U^{\prime}]$ contains a
$P_{3}$ or two independent edges, we can always find $t$ disjoint copies of
$C_{2\ell}$, which consist of $t-1$ $2\ell$-cycles in
$G[W^{\prime\prime},U^{\prime}]$, and a special $2\ell$-cycle (see Figure 1).
Since $G$ is edge-maximal, we similarly have $G\cong S_{n,2t-1}^{+}$.

This completes the proof. ∎

## References

  * [1] B. Bukh, Z.L. Jiang, A bound on the number of edges in graphs without an even cycle, Combin. Probab. Comput. 26 (2017), no. 1, 1–15.
  * [2] M.-Z. Chen, A.-M. Liu, X.-D. Zhang, Spectral extremal results with forbidding linear forests, Graphs Combin. 35 (2019), no. 1, 335–351.
  * [3] M.-Z. Chen, A.-M. Liu, X.-D. Zhang, On the spectral radius of graphs without a star forest, Discrete Math. 344 (2021), no. 4, Paper No. 112269, 12 pp.
  * [4] V. Chvátal, D. Hanson, Degrees and matchings, J. Combinatorial Theory Ser. B 20 (1976), no. 2, 128–138.
  * [5] S. Cioabă, D.N. Desai, M. Tait, The spectral even cycle problem, arxiv:2205.00990v1 (2022).
  * [6] S. Cioabă, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, European J. Combin. 99 (2022), Paper No. 103420, 19 pp.
  * [7] S. Cioabă, L.H. Feng, M. Tait, X.-D. Zhang, The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Combin. 27 (2020), no. 4, Paper No. 4.22, 19 pp.
  * [8] D.N. Desai, L.Y. Kang, Y.T. Li, Z.Y. Ni, M. Tait, J. Wang, Spectral extremal graphs for intersecting cliques, Linear Algebra Appl. 644 (2022), 234–258.
  * [9] P. Erdős, Über ein Extremal problem in der Graphentheorie, Arch. Math. 13 (1962), 222–227.
  * [10] P. Erdős, T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356.
  * [11] P. Erdős, L. Pósa, On the maximal number of disjoint circuits of a graph, Publ. Math. Debrecen 9 (1962), 3–12.
  * [12] L.H. Feng, G.H. Yu, X.-D. Zhang, Spectral radius of graphs with given matching number, Linear Algebra Appl. 422 (2007), no. 1, 133–138.
  * [13] Z. Füredi, D.S. Gunderson, Extremal numbers for odd cycles, Combin. Probab. Comput. 24 (2015), no. 4, 641–645.
  * [14] Z.Y. He, A new upper bound on the Turán number of even cycles, Electron. J. Combin. 28 (2021), no. 2, Paper No. 2.41, 18 pp.
  * [15] Y.T. Li, Y.J. Peng, The spectral radius of graphs with no intersecting odd cycles, Discrete Math. 345 (2022), no. 8, Paper No. 112907, 16 pp.
  * [16] Y.T. Li, Y.J. Peng, The maximum spectral radius of non-bipartite graphs forbidding short odd cycles, Electron. J. Combin. 29 (2022), no. 4, Paper No. 4.2.
  * [17] H.Q. Lin, B. Ning, B. Wu, Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2021), 258–270.
  * [18] H.Q. Lin, B. Ning, A complete solution to the Cvetković-Rowlinson conjecture, J. Graph Theory 97 (2021), no. 3, 441–450.
  * [19] J.W. Moon, On independent complete subgraphs in a graph, Canadian J. Math. 20 (1968), 95–102.
  * [20] Z.Y. Ni, J. Wang, L.Y. Kang, Spectral extremal graphs for disjoint cliques, Electron. J. Combin. 30 (2023), no. 1, Paper No. 1.20.
  * [21] V. Nikiforov, Bounds on graph eigenvalues II, Linear Algebra Appl. 427 (2007), no. 2-3, 183–189.
  * [22] V. Nikiforov, A spectral condition for odd cycles in graphs, Linear Algebra Appl. 428 (2008), no. 7, 1492–1498.
  * [23] V. Nikiforov, Stability for large forbidden subgraphs, J. Graph Theory 62 (2009), no. 4, 362–368.
  * [24] V. Nikiforov, Degree powers in graphs with a forbidden even cycle, Electron. J. Combin. 16 (2009), no. 1, Research Paper 107, 9 pp.
  * [25] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432 (2010), no. 9, 2243–2256.
  * [26] V. Nikiforov, On a theorem of Nosal, arXiv:2104.12171 (2021).
  * [27] O. Pikhurko, A note on the Turán function of even cycles, Proc. Amer. Math. Soc. 140 (2012), 3687–3692.
  * [28] M. Simonovits, Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions, Discrete Math. 7 (1974), 349–376.
  * [29] M. Tait, J. Tobin, Three conjectures in extremal spectral graph theory, J. Comb. Theory, Ser. B 126 (2017), 137–161.
  * [30] M. Tait, The Colin de Verdiere parameter, excluded minors, and the spectral radius, J. Comb. Theory, Ser. A 166 (2019), 42–58.
  * [31] J. Verstraëte, On arithmetic progressions of cycle lengths in graphs, Combin. Probab. Comput. 9 (2000), no. 4, 369–373.
  * [32] J. Wang, L.Y. Kang, Y.S. Xue, On a conjecture of spectral extremal problems, J. Combin. Theory Ser. B 159 (2023), 20–41.
  * [33] M.Q. Zhai, B. Wang, Proof of a conjecture on the spectral radius of $C_{4}$-free graphs, Linear Algebra Appl. 437 (2012), no. 7, 1641–1647.
  * [34] M.Q. Zhai, H.Q. Lin, Spectral extrema of $K_{s,t}$-minor free graphs–on a conjecture of M. Tait, J. Combin. Theory Ser. B 157 (2022), 184–215.