# Spectral radius, edge-disjoint cycles and cycles of the same length
111Supported by the National Natural Science Foundation of China (11771141,
12171066 and 12011530064).

Huiqiu Lina, Mingqing Zhaib and Yanhua Zhaoa
aSchool of Mathematics, East China University of Science and Technology,
Shanghai 200237, China
b School of Mathematics and Finance, Chuzhou University, Chuzhou, Anhui
239012, China E-mail<EMAIL_ADDRESS>(H.Q. Lin<EMAIL_ADDRESS>(M.
Zhai<EMAIL_ADDRESS>(Y.H. Zhao)

Abstract:

In this paper, we give spectral conditions to guarantee the existence of two
edge disjoint cycles and two cycles of the same length. These two results can
be seen as spectral analogues of Erdős and Posa’s size condition and Erdős’
classic problem on non existence of two cycles of the same length. By using
double leading eigenvectors skill, we further give spectral condition to
guarantee the existence of $k$ edge disjoint triangles.

Keywords: Spectral radius; two edge disjoint cycles; two cycles of the same
lengths; $k$ edge disjoint triangles

AMS Classification: 05C50; 05C35

##  1 Introduction

The study of cycles has a rich history in graph theory. A folklore result
states that every graph with minimum degree at least 2 has a cycle. On the
other hand, a connected graph on $n$ vertices without any cycle is a tree. Let
${\Omega_{k}}^{\prime}$ be the family of graphs with $k$ edge-disjoint cycles,
and $\overline{\Omega^{\prime}_{k}}$ be the family of graphs out of
${\Omega_{k}}^{\prime}$. Erdős and Posa proved the following theorem.

######  Theorem 1 (Erdős and Posa [10]).

Let $G$ be a graph on $n$ vertices and $m$ edges. If
$G\in\overline{\Omega^{\prime}_{2}}$, then $m\leq n+3$. Furthermore, if
$G\in\overline{\Omega^{\prime}_{2}}$ and $m=n+3$, then $G$ is obtained from a
subdivision $G_{0}$ of $K_{3,3}$ by adding a forest and exactly one edge,
joining each tree of the forest to $G_{0}$.

Bollobás in his classic book [2] posed a more general problem as follows: What
is the maximum size of a graph $G\in\overline{\Omega^{\prime}_{k}}$ of order
$n$? Up to now, this problem is still widely open.

Another classic problem involves cycles of the same length. Let $f(n)$ be the
maximum number of edges in a graph on $n$ vertices without two cycles of the
same length. Erdős posed the problem of determining $f(n)$, which was listed
as one of $50$ unsolved problems in the textbook by Bondy and Murty (see [1,
p.247, Problem 11]). It has attracted the attention of many scholars. In 1988,
Shi [31] gave a lower bound of $f(n)$, which was improved by Lai [21] in 2017.
Boros, Caro, Füredi and Yuster [3] showed that $\sqrt{n}-o(\sqrt{n})\leq
f(n)-n\leq 1.98\sqrt{n}(1+o(1))$, and they further conjectured that
$\lim\limits_{n\rightarrow\infty}\frac{f(n)-n}{\sqrt{n}}=1$. Very recently, Ma
and Yang [24] confirmed their conjecture by showing that
$f(n)<n+\sqrt{n}+o(n)$ for any $n$-vertex 2-connected graph. However, the
exactly value of $f(n)$ is still unknown. For more related results, we refer
the interested readers to [9, 20, 22].

One main purpose of this paper is to investigate these two problems from a
spectral perspective. The eigenvalue conditions for cycles have been studied
by a plenty of researchers (see [37]) and two surveys [6, 29] for more
fruitful results. In 1995, Favaron, Mahéo and Saclé [11] proved that every
graph on $n$ vertices with $\rho(G)>\rho(S_{n,1})=\sqrt{n-1}$ contains a
$C_{3}$ or a $C_{4}$. Generalizing this theorem, Nikiforov [28] conjectured
that: (a) every graph of sufficiently large order $n$ with
$\rho(G)\geq\rho(S_{n,k})$ contains a $C_{2k+1}$ or a $C_{2k+2}$, unless
$G=S_{n,k}$. He [28] also conjectured that: (b) every graph of sufficiently
large order $n$ with $\rho(G)\geq\rho(S^{+}_{n,k})$ contains a $C_{2k+2}$,
unless $G=S^{+}_{n,k}$. The conjecture (a) was confirmed for $k=2$ in [33] and
conjecture (b) was confirmed recently for $k=2$ in [34]. For $C_{4}$,
Nikiforov [27] and Zhai and Wang [36] characterized the extremal graphs on odd
$n$ and even $n$, respectively. For consecutive cycles, see Nikiforov [25],
Ning and Peng [30], Zhai and Lin [35] and Li and Ning [18]. Only very
recently, confirming the first open case of a conjecture due to Bollobás and
Nikiforov, Lin, Ning and Wu [19] obtained a new eigenvalue condition for
triangles. Furthermore, they obtained a spectral analogue of a theorem of
Erdős, which states that a non-bipartite graph $G$ with
$\rho(G)\geq\rho(S(K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil}))$
contains a triangle unless $G\cong
S(K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil})$ where
$S(K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil})$ denotes a
subdivision of $K_{\lfloor\frac{n-1}{2}\rfloor,\lceil\frac{n-1}{2}\rceil}$ on
one edge. There are also quite a lot of references on eigenvalues and large
cycles, we refer the reader to [12, 13, 18].

It seems that the study of cycles in terms of eigenvalues is closely related
to extremal graph theory. For example, in order to solve an open problem
raised by Caro and Yuster on degree powers in graphs with a forbidden even
cycle, Nikiforov [26] proved an extension of the classical Erdős-Gallai
theorem on cycles. Interestingly, he also used it as a tool to study a
spectral problem, showing that $\rho^{2}(G)-k\rho(G)\leq k(n-1)$ if $G$ is
$C_{2k}$-free. Only very recently, it is also shown that the spectral theorem
on consecutive cycles [25] is a tool for studying some generalized Turán-type
problems, such as estimating ex$(n,P_{l},C_{2k+1})$ (see [14]).

In this paper, we continue the project of studying cycles in spectral
prospective. Compared with [19], we focus on eigenvalues conditions for edge-
disjoint cycles, cycles of the same length.

As usual, we denote by $K_{r}$ the complete graph on $r$ vertices, by
$S_{n,k}$ the graph obtained by joining $n-k$ isolated vertices with each
vertex in $K_{k}$, and by $K_{a,b}$ the complete bipartite graph with two
parts of orders $a$ and $b$, respectively. Let $H\in\\{C_{r},K_{r},K_{r,r}\\}$
where $C_{r}$ denotes the cycle of length $r$. We denote by $H\bullet K_{a,b}$
the graph obtained by coalescing a vertex of $K_{a,b}$ belonging to the part
of size $a$ with a vertex in $H$ and retaining the connection of edges in $H$
and $K_{a,b}$. Let $K_{1,n-1}^{+}$ be the graph obtained by adding an edge
within the independent set of $K_{1,n-1}$.

It is rather surprising that we find a spectral analogue of $f(n)$ and the
extremal graph is also determined.

######  Theorem 2.

Let $G$ be a graph of order $n\geq 26$. If $\rho(G)\geq\rho(K^{+}_{1,n-1})$,
then $G$ contains two cycles with the same length unless $G\cong
K_{1,n-1}^{+}$.

In the following, we give a spectral analogue of Theorem 1.

######  Theorem 3.

Let $G$ be a graph of order $n\geq 17$. If $\rho(G)\geq\rho(K_{4}\bullet
K_{1,n-4})$, then $G$ contains two edge-disjoint cycles unless $G\cong
K_{4}\bullet K_{1,n-4}$.

It is a natural wish to determine the maximum spectral radius of
$\Omega^{\prime}_{k}$-free graphs of order $n$, which is stated as follows.

######  Problem 1.1.

What is the maximum spectral radius of $\Omega^{\prime}_{k}$-free graphs of
order $n$?

However, it seems difficult to solve Problem 1.1, even for giving a conjecture
on $k\geq 3$. Therefore, we turn out this problem in a special version, i.e.,
the Brualdi-Solheid-Turán type problem for $k$ edge-disjoint triangles graphs,
which also has an interesting history. Let $\mathcal{F}$ be a family of
graphs. A graph $G$ is called $\mathcal{F}$-free if it contains no any graph
in $\mathcal{F}$ as a subgraph. The Turán number of $\mathcal{F}$, denote by
ex$(n,\mathcal{F})$, is the maximum number of edges in an $\mathcal{F}$-free
graph of order $n$. Let EX$(n,\mathcal{F})$ be the family of
$\mathcal{F}$-free graphs with ex$(n,\mathcal{F})$ edges. In particular, if
$\mathcal{F}$ contains the unique element, i.e., $\mathcal{F}=\\{F\\}$, then
we denote by ex$(n,F)$ and EX$(n,F)$, for short. Let $\Gamma_{k}$ be the
family of graphs containing $k$-edge-disjoint triangles. Győri [16] determined
the Turán number ex$(n,\Gamma_{k})$ as follows.

######  Theorem 4.

([16]) Let $G$ be a graph of order $n$ that does not contain a subgraph
belonging to $\Gamma_{k}$, $k\geq 1$. Then $e(G)\leq
ex(n,\Gamma_{k})=\lfloor\frac{n^{2}}{4}\rfloor+k-1$, and the extremal graph is
obtained from a complete bipartite graph with color classes of size
$\lceil\frac{n}{2}\rceil$ and $\lfloor\frac{n}{2}\rfloor$ by embedding edges
of size $k-1$.

As usual, given a graph $H$, let SPEX$(n,H)$ be the family of $H$-free graphs
with the maximum spectral radius. A $k$-fan, denoted by $F_{k}$, is the graph
obtained from $k$ triangles by sharing a common vertex. Cioabă, Feng, Tait and
Zhang [8] proved that SPEX$(n,F_{k})\subseteq\mbox{EX}(n,F_{k})$. To
generalize their result, Li and Peng [23] showed that
SPEX$(n,H_{s,k})\subseteq\mbox{EX}(n,H_{s,k})$ where $H_{s,k}$ is the graph
obtained from $s$ triangles and $k$ odd cycles of lengths at least 5 by
sharing a common vertex. The odd wheel $W_{2k+1}$ is the graph formed by
joining a vertex to a cycle of length $2k$. Very recently, Cioabă, Desai and
Tait [7] showed that $\mbox{SPEX}(n,W_{5})\subseteq\mbox{EX}(n,W_{5})$ and
SPEX$(n,W_{2k+1})$ for $k\geq 3$ and $k\notin\\{4,5\\}$ is obtained from a
complete bipartite graph with parts $L$ and $R$ of size $n+s$ and $n-s$ with
$|s|\leq 1$ by embedding a $(k-1)$-regular or nearly $(k-1)$-regular in $G[L]$
and exactly one edge in $G[R]$. They posed the following interesting
conjecture for further research.

######  Conjecture 1.

[7] Let $F$ be any graph such that the graphs in EX$(n,F)$ are Turán graphs
plus $O(1)$ edges. Then SPEX$(n,F)\subseteq\mbox{EX}(n,F)$ for $n$ large
enough.

In this paper, we give a spectral version of Theorem 4, in which the extremal
graph is completely characterized. This also provides a support for Cioabă,
Desai and Tait’s conjecture.

######  Theorem 5.

Let $k\geq 2$ and $G$ be a $\Gamma_{k}$-free graph of order $n$ sufficiently
large. If $G$ attains the maximum spectral radius, then

$G\in\mbox{EX}(n,\Gamma_{k}).$

More precisely, $G$ is obtained from
$K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$ by embedding a graph
$H$ of size $k-1$ in the $\lfloor\frac{n}{2}\rfloor$-vertex partition set,
where $H\cong C_{3}$ for $k=4$ and $H\cong K_{1,k-1}$ otherwise.

##  2 Spectral condition on two cycles with the same length

Before beginning our proof, we first give some notation not defined in the
above section. Let $G$ be a graph and $d_{G}(v_{i})$ be the degree of the
vertex $v_{i}$ in $G$. For $u,v\in V(G)$, denote by $d_{G}(u,v)$ the distance
between $u$ and $v$, i.e. the length of a shortest path between $u$ and $v$.
Set $N_{G}^{d}(u)=\\{v\mid v\in V(G),d_{G}(v,u)=d\\}$. Specially, we use
$N_{G}(u)$ instead of $N_{G}^{1}(u)$ and $N_{G}[u]=\\{v\mid v\in
N_{G}(u)\\}\cup\\{u\\}$. Denote by $E_{G}(V_{1},V_{2})$ the set of edges
between $V_{1}$ and $V_{2}$, and denoted $|E_{G}(V_{1},V_{2})|$ by
$e_{G}(V_{1},V_{2})$. For the sake of simplicity, we shall omit all the
subscripts if $G$ is clear from the context.

Denote by $G_{uv}$ the graph obtained from $G$ by subdividing the edge $uv$,
that is, introducing a new vertex on the edge $uv$. Let $Y_{n}$ be the graph
obtained from a path $v_{1}v_{2}\cdots v_{n-4}$ by attaching two pendant
vertices to $v_{1}$ and two pendant vertices to $v_{n-4}$. Hoffman and Smith
[17] proved the following result, which is an important tool in spectral graph
theory.

######  Lemma 1.

([17]) Let $G$ be a connected graph with $uv\in E(G)$. If $uv$ belongs to an
internal path of $G$ and $G\ncong Y_{n}$, then $\rho(G_{uv})<\rho(G)$.

Now we are in a position to give the proof of Theorem 2.

Proof of Theorem 2. Let $G^{\star}$ be a graph with the maximum spectral
radius among all graphs without two cycles with the same length. Then
$G^{\star}$ is connected, otherwise we add cut edges between components, the
resulting graph will increase the spectral radius but will not produce a new
cycle, which is impossible. Now let $Z=(z_{1},z_{2},\ldots,z_{n})^{t}$ be the
Perron vector of $A(G^{\star})$ and $z_{u^{\star}}=\max\\{z_{i}:1\leq i\leq
n\\}$. Note that $K_{1,n-1}^{+}$ does not contain two cycles with the same
length and
$X=\left(\frac{\sqrt{2}}{2},\frac{1}{\sqrt{2(n-1)}},\ldots,\frac{1}{\sqrt{2(n-1)}}\right)^{t}$
is the Perron vector of $K_{1,n-1}$. Obviously, $X\neq Z$. It follows that
$\rho(G^{\star})\geq\rho(K_{1,n-1}^{+})>X^{t}A(K_{1,n-1}^{+})X=\sqrt{n-1}+\frac{1}{n-1},$
which is equivalent to

$\rho^{2}(G^{\star})-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}-n+1>0.$
(1)

We first give the following claim which indicates that except $u^{\star}$
there is no cut vertex.

######  Claim 1.

For each vertex $u\in V(G^{\star})\backslash\\{u^{\star}\\}$, $u$ is not a cut
vertex.

###### Proof.

By the way of contradiction, assume that $u$ is a cut vertex. Then there exist
two components of $G^{\star}\backslash\\{u\\}$, say $G_{1}$ and $G_{2}$.
Without loss of generality, suppose that $u^{\star}\in V(G_{1})$. Let
$G^{\prime}$ be the graph obtained by deleting the edges between $u$ and
$N_{V(G_{2})}(u)$ and adding the edges between $u^{\star}$ and
$N_{V(G_{2})}(u)$. The resulting graph still does not have two edge-disjoint
cycles. It follows that,

$\rho(G^{\prime})-\rho(G^{\star})\geq
Z^{t}(A(G^{\prime})-A(G^{\star}))Z=(z_{u^{\star}}-z_{u})\sum_{v\in
N_{V(G_{2})}(u)}z_{v}\geq 0.$ (2)

If $\rho(G^{\prime})=\rho(G^{\star})$, then $z_{u^{\star}}=z_{u}$ and $Z$ is
also the Perron vector of $A(G^{\prime})$. But on the other hand,

$\rho(G^{\prime})z_{u^{\star}}=\sum_{v\in N(u^{\star})}z_{v}+\sum_{v\in
N_{V(G_{2})}(u)}z_{v}>\sum_{v\in
N(u^{\star})}z_{v}=\rho(G^{\star})z_{u^{\star}}.$

It follows that $\rho(G^{\prime})>\rho(G^{\star})$, which contradicts the fact
that $G^{\star}$ has maximum spectral radius. ∎

Then, we have the following claim.

######  Claim 2.

For each vertex $u\in V(G^{\star})$, $e(N(u))\leq 1$ and
$e(N(u),N^{2}(u))\leq|N^{2}(u)|+1$.

###### Proof.

By the way of contradiction, we assume that either $e(N(u))\geq 2$ or
$e(N(u),N^{2}(u))\geq|N^{2}(u)|+2$. Then $G^{\star}$ contains two triangles or
two $C_{4}$’s, a contradiction. Then the result follows. ∎

Set $|N(u^{\star})|=q$, $|N^{2}(u^{\star})|=t$ $(t>0)$ and
$N(u^{\star})=\\{v_{11},v_{12},\ldots,v_{1q}\\}$,
$N^{2}(u^{\star})=\\{v_{21},v_{22},\ldots,v_{2t}\\}$. For simplicity, we use
$d_{1i}$ $(1\leq i\leq q)$ and $d_{2j}$ $(1\leq j\leq t)$ to denote
$d_{N(u^{\star})}(v_{1i})$ and $d_{N(u^{\star})}(v_{2j})$, respectively. Now
let $(1)\times z_{u^{\star}}$. Then

$\displaystyle\begin{aligned}
&\rho^{2}(G^{\star})z_{u^{\star}}-\frac{2}{n-1}\rho(G^{\star})z_{u^{\star}}+(\frac{1}{(n-1)^{2}}-n+1)z_{u^{\star}}\\\
&=d(u^{\star})z_{u^{\star}}+\sum_{i=1}^{q}d_{1i}z_{1i}+\sum_{j=1}^{t}d_{2j}z_{2j}-\frac{2}{n-1}\rho(G^{\star})z_{u^{\star}}+(\frac{1}{(n-1)^{2}}-n+1)z_{u^{\star}},\end{aligned}$
(3)

it is easy to see that $(\ref{2})>0$ and

$\displaystyle\begin{aligned} (\ref{2})&\leq
z_{u^{\star}}(d(u^{\star})+\sum_{i=1}^{q}d_{1i}+\sum_{j=1}^{t}d_{2j}-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}-n+1)\\\
&=z_{u^{\star}}(d(u^{\star})+2e(N(u^{\star}))+e(N(u^{\star}),N^{2}(u^{\star}))-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}-n+1).\end{aligned}$

It follows that

$\displaystyle
d(u^{\star})+2e(N(u^{\star}))+e(N(u^{\star}),N^{2}(u^{\star}))-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}-n+1>0.$
(4)

Let $C(u^{\star})=V(G^{\star})\backslash\\{N[u^{\star}]\cup
N^{2}(u^{\star})\\}$. By Claim 2, we have

$e(N(u^{\star}),N^{2}(u^{\star}))\leq|N^{2}(u^{\star})|+1=n-d(u^{\star})-|C(u^{\star})|.$

Then $(\ref{3})$ becomes

$\displaystyle
2e(N(u^{\star}))-|C(u^{\star})|-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}+1>0.$
(5)

Since $\rho(G^{\star})>\sqrt{n-1}+\frac{1}{n-1}$, by inequality $(\ref{6})$,
we have $|C(u^{\star})|=0$ if $e(N(u^{\star}))=0$ and $|C(u^{\star})|\leq 2$
if $e(N(u^{\star}))=1$.

Note that $\rho(G^{\star})z_{v_{2j}}=\sum\limits_{u\sim v_{2j}}z_{u}\leq
d(v_{2j})z_{u^{\star}}$ and $\rho(G^{\star})>\sqrt{n-1}\geq 5$ as $n\geq 26$.
Then

$\displaystyle(\ref{2})\leq$ $\displaystyle
z_{u^{\star}}(d(u^{\star})+\sum_{i=1}^{q}d_{1i}+\sum_{j=1}^{t}d_{2j}\frac{d(v_{2j})}{\rho(G^{\star})}-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}-n+1)$
$\displaystyle=$ $\displaystyle
z_{u^{\star}}(d(u^{\star})+\sum_{i=1}^{q}d_{1i}+e(N(u^{\star}),N^{2}(u^{\star}))-\alpha-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}-n+1),$
(6)

where
$\alpha=e(N(u^{\star}),N^{2}(u^{\star}))-\sum\limits_{j=1}^{t}d_{2j}\frac{d(v_{2j})}{\rho(G^{\star})}$,
that is,
$\alpha=\sum\limits_{j=1}^{t}d_{2j}-\sum\limits_{j=1}^{t}d_{2j}\frac{d(v_{2j})}{\rho(G^{\star})}$.
Before proceeding, we need the following fact.

######  Fact 1.

$5t-5\alpha<\sum_{j=1}^{t}d(v_{2j})\leq
t+1+2e(N^{2}(u^{\star}))+e(N^{2}(u^{\star}),N^{3}(u^{\star})).$

###### Proof.

Recall that there is at most one vertex $v_{2j}\in N^{2}(u^{\star})$ such that
$d_{2j}=2$, that is, $t\leq\sum\limits_{j=1}^{t}d_{2j}\leq t+1$. It implies
that $\sum\limits_{j=1}^{t}d(v_{2j})\leq
t+1+2e(N^{2}(u^{\star}))+e(N^{2}(u^{\star}),N^{3}(u^{\star})).$ In the
following, we only need to show that
$\sum\limits_{j=1}^{t}d(v_{2j})>5t-5\alpha.$ If
$\sum\limits_{j=1}^{t}d_{2j}=t$, then
$\alpha=t-\sum\limits_{j=1}^{t}\frac{d(v_{2j})}{\rho(G^{\star})}$. If
$\sum_{j=1}^{t}d_{2j}=t+1$, without loss of generality, let $d_{2t}=2$, then
$d_{N^{2}(u^{\star})}(v_{2t})\leq 1$ (otherwise, one can find two $C_{5}$’s).
Combining this with $|C(u^{\star})|\leq 2$, we have $d(v_{2t})\leq 5$. Then

$\alpha=t-1-\sum\limits_{j=1}^{t-1}\frac{d(v_{2j})}{\rho(G^{\star})}+2-2\frac{d(v_{2t})}{\rho(G^{\star})}\geq
t-1-\sum\limits_{j=1}^{t-1}\frac{d(v_{2j})}{\rho(G^{\star})}+1-\frac{d(v_{2t})}{\rho(G^{\star})}=t-\sum\limits_{j=1}^{t}\frac{d(v_{2j})}{\rho(G^{\star})}.$

Thus $\alpha\geq
t-\sum\limits_{j=1}^{t}\frac{d(v_{2j})}{\rho(G^{\star})}>t-\frac{1}{5}\sum\limits_{j=1}^{t}d(v_{2j})$,
as required. ∎

######  Claim 3.

$e(N(u^{\star}))=1$.

###### Proof.

By the way of contradiction, we assume that $e(N(u^{\star}))=0$. Recall that
the only possible cut vertex is $u^{\star}$. Moreover, from $(\ref{6})$, it
follows that $|C(u^{\star})|=0$. Now we derive the proof by the following
three cases.

$\underline{\mbox{Case 1. }}$ $e(N^{2}(u^{\star}))\geq 3$. Without loss of
generality, suppose that $e_{1},e_{2},e_{3}\in
E(G^{\star}[N^{2}(u^{\star})])$. It is clear that each edge in
$\\{e_{1},e_{2},e_{3}\\}$ is contained in either a $C_{3}$ or a $C_{5}$, which
implies that $G^{\star}$ contains two $C_{3}$’s or two $C_{5}$’s, a
contradiction.

$\underline{\mbox{Case 2.}}$ $1\leq e(N^{2}(u^{\star}))\leq 2$. Recall that
$2e(N(u^{\star}))=\sum_{i=1}^{q}d_{1i}=0$ and $|C(u^{\star})|=0$. Then
$e(N^{2}(u^{\star}),N^{3}(u^{\star}))=0$ and

$(\ref{4})\leq
z_{u^{\star}}(-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}+1-\alpha).$

From $0<(\ref{2})\leq(\ref{4})$, we have
$-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}+1-\alpha>0$, which implies
that $\alpha<1$. Then by Fact 1, we have

$5t-5<\sum_{j=1}^{t}d(v_{2j})\leq t+1+2e(N^{2}(u^{\star})),$

which is equivalent to $2|N^{2}(u^{\star})|<e(N^{2}(u^{\star}))+3\leq 5$, that
is, $e(N^{2}(u^{\star}))=1$ and $|N^{2}(u^{\star})|=2$. Then
$2|N^{2}(u^{\star})|<e(N^{2}(u^{\star}))+3=4$, which contradicts the fact that
$|N^{2}(u^{\star})|=2$.

$\underline{\mbox{Case 3. }}$ $e(N^{2}(u^{\star}))=0$. Combining
$e(N(u^{\star}),N^{2}(u^{\star}))\leq t+1$ with the fact that no vertex in
$N(u^{\star})$ is a cut vertex, we have $t=|N^{2}(u^{\star})|=1$, and then
$G^{\star}\cong C_{4}\bullet K_{1,n-4}$. By Lemma 1, $\rho(C_{4}\bullet
K_{1,n-4})<\rho(K_{1,n-2}^{+})<\rho(K_{1,n-1}^{+})$, a contradiction. ∎

For each edge in $G^{\star}[V(G^{\star})\backslash N[u^{\star}]]$, the two
end-vertices of which have no common neighbor since $e(N(u^{\star}))=1$. It
follows that $e$ is contained in a $5$-cycle for each edge $e\in
G^{\star}[N^{2}(u^{\star})]$, which implies that $e(N^{2}(u^{\star}))\leq 1$.
The following claim gives the clear characterization of $G^{\star}$.

######  Claim 4.

$G^{\star}\cong K_{1,n-1}^{+}$.

###### Proof.

Recall that $|C(u^{\star})|\leq 2$ and there exists no cut vertex in
$V(G^{\star})\backslash\\{u^{\star}\\}$. It follows that
$|N^{4}(u^{\star})|=0$ and $|N^{3}(u^{\star})|\leq 2$. Note that $\rho(G)\cdot
z_{u}=\sum_{v\sim u}z_{v}\leq d(u)z_{u^{\star}}$ and $\rho(G)>\sqrt{n-1}\geq
5$ as $n\geq 26$. Then $z_{u}<\frac{d(u)}{5}z_{u^{\star}}$ for each $u\in
V(G^{\star})\backslash\\{u^{\star}\\}$. We derive the proof by the following
three cases.

$\underline{\mbox{Case 1. }}$ $|N^{3}(u^{\star})|=2.$ Let
$N^{3}(u^{\star})=\\{u_{1},u_{2}\\}$. Recall that
$e(N(u^{\star}),N^{2}(u^{\star}))\leq n-d(u^{\star})-|C(u^{\star})|=t+1$. We
assert $e(N(u^{\star}),N^{2}(u^{\star}))=t+1$. If not, then
$e(N(u^{\star}),N^{2}(u^{\star}))=t=n-d(u^{\star})-|C(u^{\star})|-1$ and
$(\ref{3})$ becomes $-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}<0$, a
contradiction. It implies that $u^{\star}$ is contained in a $4$-cycle.
Therefore, for each $u\in N^{3}(u^{\star})$, if $w,v\in N^{2}(u^{\star})$ are
two neighbors of $u$, then $N_{N(u^{\star})}(w)\neq N_{N(u^{\star})}(v)$. It
follows that $e(N^{2}(u^{\star}),N^{3}(u^{\star}))\leq 3$ (otherwise, there
are two $C_{6}$’s) and $u_{1}u_{2}\in E(G^{\star})$ since $N^{2}(u^{\star})$
does not have cut vertex. By the above discussion, we have
$\sum_{i=1}^{q}d_{1i}=2e(N(u^{\star}))=2$,
$e(N^{2}(u^{\star}),N(u^{\star}))=t+1$, $e(N^{2}(u^{\star}))\leq 1$ and
$e(N^{2}(u^{\star}),N^{3}(u^{\star})\leq 3$. Then

$(\ref{4})=z_{u^{\star}}(-\frac{2}{n-1}\rho(G^{\star})+\frac{1}{(n-1)^{2}}+1-\alpha).$

Combining the fact with $0<(\ref{2})\leq(\ref{4})$, we have $\alpha<1$. By
Fact 1, we have $5t-5<t+6$, that is, $t\leq 2$. Then $t=2$ since
$N^{2}(u^{\star})$ does not contain cut vertex and $e(N^{2}(u^{\star}))\neq 1$
since $u^{\star}$ belongs to a 4-cycles. Since $u_{1}$, $u_{2}$ have no common
neighbor in $N^{2}(u^{\star})$, so $e(N^{2}(u^{\star}),N^{3}(u^{\star}))=2$.
Again by Fact 1, we have $5t-5<t+3$, that is, $t\leq 1$, which contradicts
$t=2$.

$\underline{\mbox{Case 2. }}$ $|N^{3}(u^{\star})|=1$. Let
$N^{3}(u^{\star})=\\{u\\}$. If $d(u)\geq 3$, then $G^{\star}$ contains either
two $C_{4}$’s or two $C_{6}$’s, which is impossible. Note that $u^{\star}$ is
the unique possible cut vertex. Thus $d(u)=2.$ Without loss of generality, set
$N(u)=\\{v_{21},v_{22}\\}$. Then $v_{21}v_{22}\notin E(G^{\star})$ and
$d_{21}=d_{22}=1$ (otherwise, either $G^{\star}$ contains two $C_{4}$’s or two
$C_{6}$’s). So $d(v_{21})+d(v_{22})\leq 5$ since $e(N^{2}(u^{\star}))\leq 1$.
Let $G_{1}=G^{\star}-\\{uv_{21},uv_{22}\\}+\\{u^{\star}u\\}$. Recall that
$z_{v_{2i}}<\frac{d(u)}{5}z_{u^{\star}}$ for $i=1,2$. Then

$Z^{T}(\rho(G_{1})-\rho(G^{\star}))Z=z_{u^{\star}}z_{u}-z_{u}(z_{v_{21}}+z_{v_{22}})>z_{u^{\star}}z_{u}(1-\frac{d(v_{21})+d(v_{22})}{5})\geq
0,$

which implies that $\rho(G_{1})>\rho(G^{\star})$, a contradiction.

$\underline{\mbox{Case 3. }}$ $|N^{3}(u^{\star})|=0$. Note that
$e(N^{2}(u^{\star}))\leq 1$ and $e(N(u^{\star}),N^{2}(u^{\star}))\leq t+1$.
Then $t\leq 3$ since no vertex in $N(u^{\star})$ is a cut vertex. If $t=1$ or
$t=3$, then there exists a vertex $\\{v_{21}\\}\in N^{2}(u^{\star})$ such that
$d(v_{21})=2$ and let $N(v_{21})=\\{v_{11},v_{12}\\}\subseteq N(u^{\star})$.
Besides, $v_{11}v_{12}\notin E(G^{\star})$. It is clear that
$d(v_{11})+d(v_{12})\leq 5$ for $t=1$. Moreover, $d(v_{11})+d(v_{12})\leq 5$
also holds for $t=3$ since otherwise there are two $C_{5}$’s. Let
$G_{2}=G^{\star}-\\{v_{21}v_{11},v_{21}v_{12}\\}+\\{u^{\star}v_{21}\\}$. By a
similar proof to Case 2, we have $\rho(G_{2})>\rho(G^{\star})$, a
contradiction. If $t=2$, say $\\{v_{21},v_{22}\\}\in N^{2}(u^{\star})$,
according to the fact that no vertex in $N(u^{\star})$ is a cut vertex and
$v_{21},v_{22}$ have no common neighbor, then $v_{21}v_{22}\in E(G^{\star})$.
It follows that $d_{21}=d_{22}=1$ (otherwise, there are two $C_{5}$’s), that
is, $d(v_{21})=d(v_{22})=2$. Let $N_{N(u^{\star})}(v_{21})=v_{11}$. Then
$d(v_{11})\leq 3$ and $d(v_{11})+d(v_{22})\leq 5$. Let
$G_{3}=G^{\star}-\\{v_{21}v_{11},v_{21}v_{22}\\}+\\{u^{\star}v_{21}\\}$.
Similar to the proof of Case 2, we have $\rho(G_{3})>\rho(G^{\star})$, a
contradiction. Therefore, $t=0$, i.e., $G^{\star}\cong K_{1,n-1}^{+}$.

Therefore, the proof of Theorem 2 is complete. ∎

##  3 Spectral conditions for edge-disjoint cycles

We first need the following well-known result as our lemma.

######  Lemma 2.

(Brouwer and Haemers [4, p. 30]; Godsil and Royle [15, pp. 196–198].) Let $A$
be a real symmetric matrix, and let $B$ be an equitable quotient matrix of
$A$. Then the eigenvalues of $B$ are also eigenvalues of $A$. Furthermore, if
$A$ is nonnegative and irreducible, then

$\rho(A)=\rho(B).$

Now, we shall give the proof of Theorem 3.

###  3.1 Proof of Theorem 3

Suppose that $G^{\star}$ is a graph attaining the maximum spectral radius
among all graphs of order $n$ without two edge-disjoint cycles. Clearly,
$G^{\star}$ is connected. Since the graph $K_{4}\bullet K_{1,n-4}$ does not
contain two edge-disjoint cycles, we have
$\rho(G^{\star})\geq\rho(K_{4}\bullet K_{1,n-4})$.

Let
$X=(\frac{\sqrt{2}}{2},\frac{1}{\sqrt{2(n-1)}},\ldots,\frac{1}{\sqrt{2(n-1)}})^{t}$
be the Perron vector of $K_{1,n-1}$. Notice that $X$ cannot be the Perron
vector of $K_{4}\bullet K_{1,n-4}$. Then, by the Rayleigh quotient, we obtain

$\rho(G^{\star})\geq\rho(K_{4}\bullet K_{1,n-4})>X^{\prime}A(K_{4}\bullet
K_{1,n-4})X=\sqrt{n-1}+\frac{3}{n-1},$

which implies that

$\rho^{2}(G^{\star})>n-1+\frac{6}{\sqrt{n-1}}+\frac{9}{(n-1)^{2}}.$ (7)

Let $Y=(y_{v_{1}},y_{v_{2}},\ldots,y_{v_{n}})^{t}$ be the unique positive
eigenvector of $\rho(G^{\star})$ with $\max\\{y_{v_{i}}:1\leq i\leq n\\}=1$,
and let $u^{\star}\in V(G^{\star})$ be such that $y_{u^{\star}}=1$. Similar to
the proof of Theorem 2, $u^{\star}$ is the only possible cut vertex.

######  Claim 5.

Aside from some triangles, there are no internal paths in $G^{\star}$.

###### Proof.

By Lemma 1, contracting an edge in an internal path will increase the spectral
radius but not increase the number of edge-disjoint cycles. Then the claim
follows. ∎

######  Claim 6.

Each vertex of $V(G^{\star})\backslash\\{u^{\star}\\}$ has degree at most $3$.

###### Proof.

By contradiction, assume that there exists some $v\in
V(G^{\star})\backslash\\{u^{\star}\\}$ such that $d(v)\geq 4$. Let
$u_{1},u_{2},u_{3},u_{4}$ be four neighbors of $v$. By Claim 1, $v$ is not a
cut vertex. Thus, there is a path $P_{1}$ from $u_{1}$ to $u_{4}$ with
$v\notin V(P_{1})$. We call it a $(u_{1},u_{4})$-path. Similarly, we can find
a $(u_{2},u_{3})$-path $P_{2}$ with $v\notin V(P_{2})$. Let $|V(P_{1})\cap
V(P_{2})|=k$. Whether $k\geq 2$, $k=1$ or $k=0$ (_see Figure. 1_), we can
always find two edge-disjoint cycles, a contradiction. ∎

$v$$v$$v$$u_{1}$$v_{i}$$u_{1}$$u_{1}$$u_{2}$$u_{2}$$u_{2}$$v_{i}$$u_{3}$$u_{3}$$u_{3}$$v_{j}$$u_{4}$$u_{4}$$u_{4}$
Figure 1: All cases of $(u_{1},u_{4})$-path and $(u_{2},u_{3})$-path.

Suppose that $N(u^{\star})=\\{v_{11},v_{12},\ldots,v_{1q}\\}$ and
$N^{2}(u^{\star})=\\{v_{21},v_{22},\ldots,v_{2t}\\}$. For simplicity, let
$d_{1i}=d_{G^{\star}[N(u^{\star})]}(v_{1i})$ $(1\leq i\leq q)$ and
$d_{2j}=d_{G^{\star}[N(u^{\star})]}(v_{2j})$ $(1\leq j\leq t)$. Our goal of
the rest is to show that $e(N(u^{\star}))=3$. We first show the following
claim to insure that $N(u^{\star})$ is not an independent set.

######  Claim 7.

$e(N(u^{\star}))\geq 1$

###### Proof.

Suppose to the contrary that $e(G^{\star}[N(u^{\star})])=0$. Let
$B_{1},B_{2},\ldots,B_{l}$ be the components of $V(G^{\star})\backslash
N[u^{\star}]$. Clearly, $l\geq 1$ because $G^{\star}\not\cong K_{1,n-1}$ due
to $\rho(G^{\star})>\rho(K_{1,n-1})$. By Claim 1, each vertex of
$V(G^{\star})\backslash\\{u^{\star}\\}$ is not a cut vertex. Then
$|N_{N(u^{\star})}(B_{i})|\geq 2$ and then $G^{\star}[N[u^{\star}]\cup B_{i}]$
contains a cycle for $1\leq i\leq l$. We derive the proof by the following two
cases.

$\underline{\mbox{Case 1.}}$ $l\geq 2$. We claim that $G^{\star}[B_{i}]$ is a
tree for $1\leq i\leq l$. If not, assume that $G^{\star}[B_{j}]$ contains a
cycle, say $C_{1}$ for some $j\in[1,l]$. Then $C_{1}$ together with a cycle in
$G^{\star}[N[u^{\star}]\cup B_{i}]$ $(i\neq j)$ are two edge-disjoint cycles
in $G^{\star}$, a contradiction. Similarly, we have $e(v,B_{i})\leq 1$ for
each vertex $v\in N(u^{\star})$. Then we claim that $|B_{i}|=1$ for $1\leq
i\leq l$. Otherwise, suppose that $|B_{j}|\geq 2$ for some $j\in[1,l]$, then
there are at least two leaves in $B_{j}$, say $v_{21}$ and $v_{22}$. Then
$N_{N(u^{\star})}(v_{21})\cap N_{N(u^{\star})}(v_{22})=\varnothing$. Moreover,
by Claims 1 and 5, we have
$|N_{N(u^{\star})}(v_{21})|=|N_{N(u^{\star})}(v_{22})|=2$. Without loss of
generality, assume that $N_{N(u^{\star})}(v_{21})=\\{v_{11},v_{12}\\}$ and
$N_{N(u^{\star})}(v_{22})=\\{v_{13},v_{14}\\}$. Then
$u^{\star}v_{11}v_{21}v_{12}u^{\star}$ and
$u^{\star}v_{13}v_{22}v_{14}u^{\star}$ are two edge-disjoint cycles, a
contradiction. Then by Claim 2, $e(N(u^{\star}),B_{i})=3$ for $1\leq i\leq l$.
It follows that $l=2$ (otherwise, one may easily find two edge-disjoint
cycles). Then $G^{\star}\cong K_{3,3}\bullet K_{1,n-6}$. Notice that

$B=\begin{bmatrix}0&1&0&0\\\ n-6&0&0&3\\\ 0&0&0&3\\\ 0&1&2&0\end{bmatrix}.$

is an equitable quotient matrix of $A(K_{3,3}\bullet K_{1,n-6})$, and the
characteristic polynomial of $B$ is $f(x)=x^{4}-(n+3)x^{2}+6n-36.$ By Lemma 2,
it follows that

$\rho^{2}(G^{\star})=\rho^{2}(B)=\frac{n+3+\sqrt{(n+3)^{2}-4(6n-36)}}{2}<n-1$

as $n\geq 17$, a contradiction.

$\underline{\mbox{Case 2.}}$ $l=1$. We claim that $|B_{1}|\geq 2$. Otherwise,
suppose that $|B_{1}|=1$ and $B_{1}=\\{v\\}$, then the vertex $w\in N(v)$ lies
in an internal path, a contradiction. If $|B_{1}|=2$ then $G^{\star}\cong
G_{1}$ (as shown in Figure. 2). Let
$G_{2}=G_{1}-\\{v_{11}v_{21},v_{11}v_{22}\\}+\\{v_{21}u^{\star},v_{22}u^{\star}\\}$
(see Figure. 2). Note that $G_{2}$ does not contain two edge-disjoint cycles.
However,

$Y^{t}(\rho(G_{2})-\rho(G^{\star}))Y\geq
2(y_{v_{21}}+y_{v_{22}})(y_{u^{\star}}-y_{v_{11}})>0$

since $y_{v_{11}}\leq\frac{3y_{u^{\star}}}{\rho({G^{\star}})}<y_{u^{\star}}$
as $n\geq 17$. It follows that $\rho(G^{\star})<\rho(G_{2})$, a contradiction.

$u^{\star}$$u^{\star}$$v_{11}$$v_{12}$$v_{11}$$v_{12}$$v_{21}$$v_{21}$$v_{22}$$v_{22}$$G_{1}$$G_{2}$
Figure 2: The graphs $G_{1}$ and $G_{2}$.

So in the following, we may assume that $|B_{1}|\geq 3$. Note that

$\rho^{2}({G^{\star}})=\rho^{2}({G^{\star}})y_{u^{\star}}=d(u^{\star})+\sum_{i=1}^{q}d_{1i}y_{1i}+\sum_{j=1}^{t}d_{2j}y_{2j}.$

According to inequality $(\ref{7})$ and the assumption that
$e(N(u^{\star}))=0$, we have

$n-1+\frac{6}{\sqrt{n-1}}+\frac{9}{(n-1)^{2}}<d(u^{\star})+\sum_{j=1}^{t}d_{2j}y_{2j}\leq
d(u^{\star})+e(N(u^{\star}),B_{1}).$

It follows that $e(N(u^{\star}),B_{1})>n-1-d(u^{\star})=|B_{1}|$. Then there
exists some $v_{21}\in B_{1}$ such that $d_{21}\geq 2$. Thus
$G^{\star}[B_{1}]$ is a tree. Otherwise, a cycle in $G^{\star}[B_{1}]$
together with a cycle in $G^{\star}[v_{21}\cup N[u^{\star}]]$ are two edge-
disjoint cycles, a contradiction. By Claims 1 and 6, we have $2\leq d(v)\leq
3$ for each $v\in V(B_{1})$. Set $S=\\{v\in V(B_{1})|d(v)=2\\}$. By Claim 5,
each vertex of $S$ belongs to some triangle of $G^{\star}.$ We aim to show
that $|S|=0$. By contradiction, suppose that $v_{22}\in S$, then
$v_{21}v_{22}\notin E(G^{\star})$ since $|B_{1}|\geq 3$ and $d(v_{21})=3$.
Then the $4$-cycle from $G^{\star}[N[u^{\star}]\cup\\{v_{21}\\}]$ together
with the triangle containing $v_{22}$ are two edge-disjoint cycles, a
contradiction. Therefore,
$e(N(u^{\star}),B_{1})=3|B_{1}|-2(|B_{1}|-1)=|B_{1}|+2\geq 5$. Thus
$|N_{N(u^{\star})}(B_{1})|\geq 3$ by Claim 6. Suppose that
$\\{v_{11},v_{12},v_{13}\\}\subseteq N(B_{1})$ and
$N_{N(u^{\star})}(v_{21})=\\{v_{11},v_{12}\\}$. Since $e(v_{13},B_{1})=2$ by
Claims 5 and 6, the cycle $v_{21}v_{11}u^{\star}v_{12}v_{21}$ together with a
cycle in $G^{\star}[B_{1}\cup\\{v_{13}\\}]$ are two edge-disjoint cycles, a
contradiction. Therefore, the proof of Claim 7 is complete. ∎

According to Claim 7, we see that $e(G^{\star}[N(u^{\star})])\geq 1$. Now we
shall prove that $V(G^{\star})=N[u^{\star}]$. If not, suppose that
$B_{1},B_{2},\ldots,B_{l}$ are components of $G^{\star}-N[u^{\star}]$. Then
each $G^{\star}[B_{i}]$ is a tree and $e(v,B_{i})\leq 1$ for each $v\in
N(u^{\star})$. Furthermore, we claim that $|B_{i}|=1$ for $i=1,\ldots,l$,
since otherwise there are two leaves in $G^{\star}[B_{i}]$, and we can find
two edge-disjoint $C_{4}$’s in $G^{\star}$, a contradiction. If $l\geq 2$, we
set $B_{1}=\\{u\\}$ and $B_{2}=\\{v\\}$. If $|N(u)\cap N(v)|\geq 2$, then a
triangle in $G^{\star}[N[u^{\star}]]$ together with a $C_{4}$ in
$G^{\star}[N(u^{\star})\cup\\{u,v\\}]$ are two edge-disjoint cycles, a
contradiction. If $|N(u)\cap N(v)|\leq 1$, then again we will find two edge-
disjoint cycles since $d(u),d(v)\geq 3$, a contradiction. It follows that
$l=1$. Set $B_{1}=\\{u\\}$. Then $2\leq d(u)\leq 3$. If $d(u)=3$ and
$N(u)=\\{v_{11},v_{12},v_{13}\\}$, again by Claims 5 and 6, we have
$d(v_{1i})=3$ for $i=1,2,3$, then $G^{\star}$ contains two edge-disjoint
triangles, a contradiction. If $d(u)=2$ and $N(u)=\\{v_{11},v_{12}\\}$, by
Claim 5, we have $v_{11}v_{12}\in E(G^{\star})$, then $G^{\star}+u^{\star}u$
does not contain two edge-disjoint cycles but
$\rho(G^{\star}+u^{\star}u)>\rho(G^{\star})$, a contradiction. Note that
$e(N(u^{\star}))\leq 3$. Then by the maximality of the spectral radius, we
have $G^{\star}\cong K_{4}\bullet K_{1,n-4}$.

###  3.2 Proof of Theorem 5

First we list some lemmas, which are useful in the proof of Theorem 5.

######  Lemma 3.

([8]) Let $G$ be a graph, and let $t$ denote the number of triangles in $G$.
Then

$e(G)\geq\rho^{2}(G)-\frac{3t}{\rho(G)}.$

######  Lemma 4.

(Cioabă, Feng, Tait and Zhang, [8]) Let $G$ be an $F_{k}$-free graph of order
$n$. For sufficiently large $n$, if $G$ has the maximal spectral radius, then

$G\in\textrm{EX}(n,F_{k}).$

Denote by $\beta(G)$ and $\Delta(G)$ be the matching number and the maximum
degree of $G$, respectively. For any two positive integers $\beta$ and
$\Delta$, we define
$f(\beta,\Delta)=\max\\{|E(G)|:\beta(G)\leq\beta,\Delta(G)\leq\Delta\\}$.
Chvátal and Hanson [5] proved the following result.

######  Lemma 5 (Chvátal and Hanson [5]).

For positive integers $\beta$, $\Delta\geq 1$,

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

######  Lemma 6.

([32]) Let $G$ be a connected graph and let $X$ be the eigenvector
corresponding to $\rho(G)$. If $x_{u}\geq x_{v}$, and let
$G^{\prime}=G-\\{vw|w\in N(v)\backslash N(u)\\}+\\{uw|w\in N(v)\backslash
N(u)\\},$ then $\rho(G)<\rho(G^{\prime})$.

Denote by $K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}\diamond
K_{1,k-1}$ the graph obtained by embedding a copy of $K_{1,k-1}$ in the part
of order $\lfloor\frac{n}{2}\rfloor$ in
$K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}$. Next, we give the
proof of Theorem 5.

Proof of Theorem 5. Assume that $G^{\star}$ is a graph attaining the maximum
spectral radius among all graphs of order $n$ containing no _$\Gamma_{k}$_.
Clearly, $G^{\star}$ is connected. Let us first prove that
$G^{\star}\in\textrm{EX}(n,\Gamma_{k})$. Since the proof method is almost the
same as the one in Lemma 4 (cf. [8]), we omit the details.

######  Claim 8.

$G^{\star}\in\textrm{EX}(n,\Gamma_{k}).$

###### Proof.

Notice that $K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}\diamond
K_{1,k-1}$ is $\Gamma_{k}$-free. By the maximality of $\rho(G^{\star})$, we
have
$\rho(G^{\star})\geq\rho(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}\diamond
K_{1,k-1})\geq\frac{2}{n}e(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}\diamond
K_{1,k-1})=\frac{2}{n}(\lfloor\frac{n^{2}}{4}\rfloor+k-1)>\frac{n}{2}$. Also,
since $G^{\star}$ is $\Gamma_{k}$-free, $F_{k}$ cannot be a subgraph of
$G^{\star}$, i.e., for any $v\in V(G^{\star})$, $G^{\star}[N(v)]$ contains no
$kK_{2}$. Let $t$ be the number of triangles in $G^{\star}.$ By Lemma 5,

$3t=\sum_{v\in V(G^{\star})}e(G^{\star}[N(v)])\leq\sum_{v\in
V(G^{\star})}\mathrm{ex}(d(v),kK_{2})\leq\sum_{v\in
V(G^{\star})}\mathrm{ex}(n,kK_{2})\leq\sum_{v\in V(G^{\star})}kn=kn^{2},$

which gives that $t\leq\frac{kn^{2}}{3}.$ Therefore, by Lemma 3, we have
$e(G^{\star})\geq\rho^{2}(G^{\star})-\frac{6t}{n}\geq\rho^{2}(G^{\star})-2kn>\frac{n^{2}}{4}-2kn.$
Let $\varepsilon$ and $\delta$ be fixed positive constants with
$\delta<\frac{1}{10(k+1)^{2}}$, $\varepsilon<\frac{\delta^{2}}{16}$. Notice
that
$\textrm{ex}(n,\Gamma_{k})=\lfloor\frac{n^{2}}{4}\rfloor+k-1\leq\textrm{ex}(n,F_{k})\leq\lfloor\frac{n^{2}}{4}\rfloor+k^{2}-k$.
Then, according to the proof in [8, Lemma 10], we have

######  Fact 2.

The graph $G^{\star}$ has a partition $V(G^{\star})=S\cup T$ which gives a
maximum cut such that $e(S,T)\geq(\frac{1}{4}-\varepsilon)n^{2}.$ Furthermore,
$\left(\frac{1}{2}-\sqrt{\varepsilon}\right)n\leq|S|,|T|\leq\left(\frac{1}{2}+\sqrt{\varepsilon}\right)n.$

Let $L=\left\\{v\in
V(G^{\star}):d(v)\leq\left(\frac{1}{2}-\frac{1}{4(k+1)}\right)n\right\\}$ and
$W=\left\\{v\in S:d_{S}(v)\geq\delta n\right\\}\cup\left\\{v\in
T:d_{T}(v)\geq\delta n\right\\}.$ We assert that $|L|<16k^{2}$. If not, there
exists some $L^{\prime}\subseteq L$ with $|L^{\prime}|=16k^{2}$. Then

$\displaystyle e(G^{\star}-L^{\prime})\geq e(G^{\star})-\sum_{v\in
L^{\prime}}d(v)\geq\frac{n^{2}}{4}-2kn-16k^{2}\left(\frac{1}{2}-\frac{1}{4(k+1)}\right)n>\frac{(n-16k^{2})^{2}}{4}+k-1$

for sufficiently large $n$. By Theorem 4, $G^{\star}-L^{\prime}$ contains $k$
edge-disjoint triangles, and so is $G^{\star}$, a contradiction. Combing this
with Fact 2, as in [8, Lemmas 13–17], we can prove the following results
successively:

  * •

$|W|<\frac{2\varepsilon}{\delta}n+\frac{2k^{2}}{\delta n}$ and $W\subseteq L$;

  * •

$L=\emptyset$, and both $G^{\star}[S]$ and $G^{\star}[T]$ are $K_{1,k}$\- and
$kK_{2}$-free;

  * •

$e(G^{\star})\geq\frac{n^{2}}{4}-12k^{2}$,
$\frac{n}{2}-4k\leq|S|,|T|\leq\frac{n}{2}+4k,$ and
$\frac{n}{2}-14k^{2}\leq\delta(G^{\star})\leq\rho(G^{\star})\leq\Delta(G^{\star})\leq\frac{n}{2}+5k$;

  * •

For any $u\in V(G^{\star})$, $\mathbf{x}_{u}\geq 1-\frac{120k^{2}}{n}$;

  * •

$\big{|}|S|-|T|\big{|}\leq 1$.

Now we prove that $G^{\star}\in\textrm{EX}(n,\Gamma_{k})$. By contradiction,
assume that $e(G^{\star})\leq\textrm{ex}(n,\Gamma_{k})-1.$ By Theorem 4, every
graph in $\textrm{EX}(n,\Gamma_{k})$ has a maximum cut $(S,T)$ of size
$\lfloor n^{2}/4\rfloor$. Since $\big{|}|S|-|T|\big{|}\leq 1$, there exists
some $H\in\textrm{EX}(n,\Gamma_{k})$ with $V(H)=V(G^{\star})$ such that the
edges between $S$ and $T$ in $H$ form a complete bipartite graph. Let
$E_{+}=E(H)\setminus E(G^{\star})$ and $E_{-}=E(G^{\star})\setminus E(H)$.
Then $(E(G^{\star})\cup E_{+})\setminus E_{-}=E(H)$, and
$|E_{+}|\geq|E_{-}|+1$ because $|E(G^{\star})\cap
E(H)|+|E_{-}|=e(G^{\star})<e(H)=|E(G^{\star})\cap E(H)|+|E_{+}|$. Also note
that $|E_{-}|\leq e(S)+e(T)<2k^{2}$. Thus,

$\displaystyle\rho(H)$
$\displaystyle\geq\frac{\mathbf{x}^{T}A(H)\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}$
$\displaystyle=\rho(G^{\star})+\frac{2}{\mathbf{x}^{T}\mathbf{x}}\sum_{ij\in
E_{+}}\mathbf{x}_{i}\mathbf{x}_{j}-\frac{2}{\mathbf{x}^{T}\mathbf{x}}\sum_{ij\in
E_{-}}\mathbf{x}_{i}\mathbf{x}_{j}$
$\displaystyle\geq\rho(G^{\star})+\frac{2}{\mathbf{x}^{T}\mathbf{x}}\left(|E_{+}|\left(1-\frac{120k^{2}}{n}\right)^{2}-|E_{-}|\right)$
$\displaystyle\geq\rho(G^{\star})+\frac{2}{\mathbf{x}^{T}\mathbf{x}}\left(|E_{+}|-|E_{-}|-\frac{240k^{2}}{n}|E_{+}|+\frac{(120k^{2})^{2}}{n^{2}}|E_{+}|\right)$
$\displaystyle\geq\rho(G^{\star})+\frac{2}{\mathbf{x}^{T}\mathbf{x}}\left(1-\frac{240k^{2}}{n}|E_{+}|+\frac{(120k^{2})^{2}}{n^{2}}|E_{+}|\right)$
$\displaystyle>\rho(G^{\star})$

for sufficiently large $n$, contrary to the maximality of $\rho(G^{\star})$.
Therefore, we conclude that $e(G^{\star})=\textrm{ex}(n,\Gamma_{k})$, and the
result follows. ∎

By Claim 8 and Theorem 4, we see that $G^{\star}$ has a partition
$V(G^{\star})=S\cup T$ with $|S|=s=\lfloor\frac{n}{2}\rfloor$ and
$|T|=t=\lceil\frac{n}{2}\rceil$ such that the edges between $S$ and $T$ form a
complete bipartite graph and $e(S)+e(T)=k-1$. Now we focus on characterizing
the exact structure of $G^{\star}$.

Let $X=(x_{v}:v\in V(G^{\star}))^{t}$ be the Perron vector of $G^{\star}$. Set
$S=\\{u_{0},u_{1},\ldots,u_{s-1}\\}$ and $T=\\{v_{0},v_{1},\ldots,v_{t-1}\\}$.
Without loss of generality, suppose that $x_{u_{0}}\geq
x_{u_{1}}\geq\cdots\geq x_{u_{s-1}}$ and $x_{v_{0}}\geq
x_{v_{1}}\geq\cdots\geq x_{v_{t-1}}$. We first assert that

$N_{S}(u_{j})\subseteq N_{S}[u_{i}]~{}~{}\textrm{for}~{}~{}0\leq i<j\leq
s-1,~{}~{}N_{T}(v_{j})\subseteq N_{T}[v_{i}]~{}~{}\textrm{for}~{}~{}0\leq
i<j\leq t-1.$ (8)

Without loss of generality, we only prove the former by the way of
contradiction. Suppose that there exist $i,j$ with $i<j$ such that
$N_{S}(u_{j})\not\subseteq N_{S}[u_{i}]$. Let $u\in N_{S}(u_{j})\setminus
N_{S}[u_{i}]$ and $G^{\prime}=G^{\star}-uu_{j}+uu_{i}$. By Lemma 6,
$\rho(G^{\prime})>\rho(G^{\star})$. This is a contradiction, and so (8)
follows. According to (8), we have $N_{S}(u_{j})\subseteq N_{S}[u_{0}]$ for
all $j\in[1,s-1]$ (resp. $N_{T}(v_{j})\subseteq N_{T}[v_{0}]$ for all
$j\in[1,t-1]$), and it follows that $E(S)=E(N_{S}[u_{0}])$ (resp.
$E(T)=E(N_{T}[v_{0}])$). Similarly, we can deduce that
$E(N_{S}(u_{0}))=E(N_{S}[u_{1}])$ and $E(N_{T}(v_{0}))=E(N_{T}[v_{1}])$.

In the remaining part of the proof, we will frequently construct a
$\Gamma_{k}$-free graph $G^{\prime}$ from $G^{\star}$ by modifying some edges.
For convenience, we always use $Y=(y_{v}:v\in V(G^{\prime}))^{t}$ to denote
the Perron vector of $G^{\prime}$. Also, we write
$\rho^{\prime}=\rho(G^{\prime})$ and $\rho=\rho(G^{\star})$ for short.

Let $s_{0}=d_{S}(u_{0})$ and $t_{0}=d_{T}(v_{0})$. Clearly, $e(S)\geq s_{0}$
and $e(T)\geq t_{0}$. In the following, we shall analyze the structure of
$G^{\star}$ according to the structure of $G^{\star}[S]$ and $G^{\star}[T]$.
Before proceeding, we need the following two claims.

######  Claim 9.

$e(S)\in\\{s_{0},s_{0}+1\\}$ and $e(T)\in\\{t_{0},t_{0}+1\\}$.

###### Proof.

We first prove that $e(S)\in\\{s_{0},s_{0}+1\\}$. By contradiction, suppose
that $e(S)\geq s_{0}+2$. Let $E^{\star}=E(N_{S}(u_{0}))$. Since
$e(S)=e(N_{S}[u_{0}])\geq d_{S}(u_{0})+2$, we have $|E^{\star}|\geq 2$. Let
$E^{\prime}=\\{u_{0}u_{i}|s_{0}+1\leq i\leq e(S)\\}$ and
$G^{\prime}=G^{\star}-E^{\star}+E^{\prime}$. Then
$|E^{\prime}|=e(S)-s_{0}=|E^{\star}|$, $G^{\prime}[S]\cong
K_{1,e(S)}\cup(s-e(S)-1)K_{1}$, and $G^{\prime}$ is $\Gamma_{k}$-free. Recall
that $X$ and $Y$ are the Perron vectors of $G^{\star}$ and $G^{\prime}$,
respectively. Then

$Y^{t}(\rho^{\prime}-\rho)X=Y^{t}(A(G^{\prime})-A(G^{\star}))X=\sum_{i=s_{0}+1}^{e(S)}(x_{u_{0}}y_{u_{i}}+y_{u_{0}}x_{u_{i}})-\sum_{u_{i}u_{j}\in
E^{\star}}(x_{u_{i}}y_{u_{j}}+x_{u_{j}}y_{u_{i}}).$

Observe that $x_{u_{i}}=x_{u_{j}}$ for $i,j\in[s_{0}+1,e(S)]$ and
$y_{u_{i}}=y_{u_{j}}$ for $i,j\in[1,e(S)]$. Then

$\sum_{i=s_{0}+1}^{e(S)}(x_{u_{0}}y_{u_{i}}+y_{u_{0}}x_{u_{i}})=|E^{\star}|(x_{u_{0}}y_{u_{1}}+y_{u_{0}}x_{u_{s_{0}+1}})$

and

$\sum_{u_{i}u_{j}\in
E^{\star}}(x_{u_{i}}y_{u_{j}}+x_{u_{j}}y_{u_{i}})\leq|E^{\star}|y_{u_{1}}(x_{u_{1}}+x_{u_{2}})\leq
2|E^{\star}|x_{u_{0}}y_{u_{1}}.$

It follows that
$Y^{t}(\rho^{\prime}-\rho)X\geq|E^{\star}|(y_{u_{0}}x_{u_{s_{0}+1}}-x_{u_{0}}y_{u_{1}}).$
Note that $\rho x_{u_{0}}-\rho x_{u_{s_{0}+1}}=\sum_{i=1}^{s_{0}}x_{u_{i}}\leq
s_{0}x_{u_{0}}$. Then $x_{u_{s_{0}+1}}\geq\frac{\rho-s_{0}}{\rho}x_{u_{0}}.$
Also, recall that $G^{\prime}[S]\cong K_{1,e(S)}\cup(s-e(S)-1)K_{1}$. Then
$y_{u_{i}}=y_{u_{j}}$ for $i,j\in[1,e(S)]$, and by considering the eigenvalue-
eigenvector equation of $A(G^{\prime})$ with respect to $\rho^{\prime}$, we
obtain

$\rho^{\prime}y_{u_{0}}=\sum\limits_{i=1}^{e(S)}y_{u_{i}}+\sum_{i=0}^{t-1}y_{v_{i}}=e(S)\cdot
y_{u_{1}}+\sum_{i=0}^{t-1}y_{v_{i}}~{}~{}\mbox{and}~{}~{}\rho^{\prime}y_{u_{1}}=y_{u_{0}}+\sum_{i=0}^{t-1}y_{v_{i}}.$

This implies that
$y_{u_{1}}=\frac{\rho^{\prime}+1}{\rho^{\prime}+e(S)}y_{u_{0}}\leq\frac{\rho+1}{\rho+e(S)}y_{u_{0}}$
because $\rho^{\prime}\leq\rho$ and $e(S)>0$. Thus,

$y_{u_{0}}x_{u_{s_{0}+1}}-x_{u_{0}}y_{u_{1}}\geq
x_{u_{0}}y_{u_{0}}\left(\frac{\rho-
s_{0}}{\rho}-\frac{\rho+1}{\rho+e(S)}\right)=x_{u_{0}}y_{u_{0}}\left(\frac{\rho(e(S)-(s_{0}+1))-s_{0}e(S)}{\rho(\rho+e(S))}\right)>0$

for sufficiently large $n$. Then
$Y^{t}(\rho^{\prime}-\rho)X\geq|E^{\star}|(y_{u_{0}}x_{u_{s_{0}+1}}-x_{u_{0}}y_{u_{1}})>0$,
and so $\rho^{\prime}>\rho$, a contradiction. Similarly,
$e(T)\in\\{t_{0},t_{0}+1\\}$. This completes the proof of the claim. ∎

######  Claim 10.

If $e(S)\neq 3$ (resp. $e(T)\neq 3$), then $e(S)=s_{0}$ and $G^{\star}[S]\cong
K_{1,e(S)}\cup(s-e(S)-1)K_{1}$ (resp. $e(T)=t_{0}$ and $G^{\star}[T]\cong
K_{1,e(T)}\cup(t-e(T)-1)K_{1}$), and if $e(S)=3$ (resp. $e(T)=3$), then
$e(S)=s_{0}+1$ and $G^{\star}[S]\cong K_{3}\cup(s-3)K_{1}$ (resp.
$e(T)=t_{0}+1$ and $G^{\star}[T]\cong K_{3}\cup(t-3)K_{1}$).

###### Proof.

By symmetry, we only need to prove the claim for $S$. First assume that
$e(S)\neq 3$. By Claim 9, we have $e(S)\in\\{s_{0},s_{0}+1\\}$. If
$e(S)=e(N_{S}[u_{0}])=s_{0}$, then the result follows. Thus we may assume that
$e(S)=e(N_{S}[u_{0}])=s_{0}+1=d_{S}(u_{0})+1=|N_{s}[u_{0}]|$. Since $e(S)\neq
3$, we claim that $s_{0}\geq 3$ and $G^{\star}[N_{S}[u_{0}]]\cong
K_{1,s_{0}}+u_{1}u_{2}$. Let $G^{\prime}=G-u_{1}u_{2}+u_{0}u_{s_{0}+1}$. It is
easy to see that $G^{\prime}[S]\cong K_{1,s_{0}+1}\cup(s-s_{0}-2)K_{1}$, and
$G^{\prime}$ is $\Gamma_{k}$-free. Thus

$\displaystyle Y^{t}(\rho^{\prime}-\rho)X$
$\displaystyle=Y^{t}(A(G^{\prime})-A(G^{\star}))X=x_{u_{0}}y_{u_{s_{0}+1}}+y_{u_{0}}x_{u_{s_{0}+1}}-x_{u_{1}}y_{u_{2}}-x_{u_{2}}y_{u_{1}}$
$\displaystyle=x_{u_{0}}y_{u_{1}}+y_{u_{0}}x_{u_{s_{0}+1}}-2x_{u_{1}}y_{u_{1}},$

where the last equality follows from the fact that $x_{u_{1}}=x_{u_{2}}$ and
$y_{u_{i}}=y_{u_{j}}$ for $i,j\in[1,s_{0}+1]$. Notice that
$G^{\star}[S]\cong(K_{1,s_{0}}+u_{1}u_{2})\cup(s-s_{0}-1)K_{1}$,
$x_{u_{1}}=x_{u_{2}}$ and $x_{u_{i}}=x_{u_{j}}$ for $i,j\in[3,s_{0}].$ By
considering the eigenvalue-eigenvector equation of $A(G^{\star})$ with respect
to $\rho$, we obtain

$\displaystyle\rho$ $\displaystyle
x_{u_{0}}=x_{u_{1}}+x_{u_{2}}+\sum_{i=3}^{s_{0}}x_{u_{i}}+\sum_{i=0}^{t-1}x_{v_{i}}=2x_{u_{1}}+(s_{0}-2)x_{u_{3}}+\sum_{i=0}^{t-1}x_{v_{i}},$
$\displaystyle\rho$ $\displaystyle
x_{u_{1}}=x_{u_{0}}+x_{u_{2}}+\sum_{i=0}^{t-1}x_{v_{i}}=x_{u_{0}}+x_{u_{1}}+\sum_{i=0}^{t-1}x_{v_{i}},~{}~{}\rho
x_{u_{3}}=x_{u_{0}}+\sum_{i=0}^{t-1}x_{v_{i}},~{}~{}\rho
x_{u_{s_{0}+1}}=\sum_{i=0}^{t-1}x_{v_{i}},$

which leads to
$x_{u_{1}}=x_{u_{2}}=\frac{\rho(\rho+1)}{\rho^{2}+(s_{0}-1)\rho-(s_{0}-2)}x_{u_{0}}\leq\frac{\rho(\rho+1)}{\rho^{2}+2\rho-1}x_{u_{0}}$
and $x_{u_{s_{0}+1}}=\frac{\rho-1}{\rho}x_{u_{1}}-\frac{1}{\rho}x_{u_{0}}.$
Therefore, $x_{u_{0}}y_{u_{1}}+y_{u_{0}}x_{u_{s_{0}+1}}-2x_{u_{1}}y_{u_{1}}$
is equal to

$\displaystyle
x_{u_{0}}y_{u_{1}}+y_{u_{0}}\left(\frac{\rho-1}{\rho}x_{u_{1}}-\frac{1}{\rho}x_{u_{0}}\right)-2x_{u_{1}}y_{u_{1}}=x_{u_{0}}\left(y_{u_{1}}-\frac{y_{u_{0}}}{\rho}\right)-x_{u_{1}}\left(2y_{u_{1}}-\frac{\rho-1}{\rho}y_{u_{0}}\right).$

Recall that $G^{\prime}[S]\cong K_{1,s_{0}+1}\cup(s-s_{0}-2)K_{1}$. According
to $\rho^{\prime}y_{u_{0}}=(s_{0}+1)\cdot
y_{u_{1}}+\sum_{i=0}^{t-1}y_{v_{i}}$,
$\rho^{\prime}y_{u_{1}}=y_{u_{0}}+\sum_{i=0}^{t-1}y_{v_{i}}$ and the fact that
$s_{0}\geq 3$, we get

$y_{u_{1}}=\frac{\rho^{\prime}+1}{\rho^{\prime}+s_{0}+1}y_{u_{0}}\leq\frac{\rho+1}{\rho+4}y_{u_{0}},$

and therefore,

$2y_{u_{1}}-\frac{\rho-1}{\rho}y_{u_{0}}\geq\left(\frac{2(\rho^{\prime}+1)}{\rho^{\prime}+s_{0}+1}-1\right)y_{u_{0}}>0.$

Notice that $x_{u_{1}}\leq\frac{\rho(\rho+1)}{\rho^{2}+2\rho-1}x_{u_{0}}.$
Then

$\displaystyle
x_{u_{0}}\left(y_{u_{1}}-\frac{y_{u_{0}}}{\rho}\right)-x_{u_{1}}\left(2y_{u_{1}}-\frac{\rho-1}{\rho}y_{u_{0}}\right)\geq
x_{u_{0}}\left(y_{u_{1}}-\frac{y_{u_{0}}}{\rho}\right)-\frac{\rho(\rho+1)}{\rho^{2}+2\rho-1}x_{u_{0}}\left(2y_{u_{1}}-\frac{\rho-1}{\rho}y_{u_{0}}\right)$
$\displaystyle=\left(\frac{\rho^{2}-1}{\rho^{2}+2\rho-1}-\frac{1}{\rho}\right)x_{u_{0}}y_{u_{0}}-\frac{\rho^{2}+1}{\rho^{2}+2\rho-1}x_{u_{0}}y_{u_{1}}$
$\displaystyle\geq\left(\frac{\rho^{2}-1}{\rho^{2}+2\rho-1}-\frac{1}{\rho}-\frac{(\rho^{2}+1)(\rho+1)}{(\rho^{2}+2\rho-1)(\rho+4)}\right)x_{u_{0}}y_{u_{0}}>0.$

Thus
$Y^{t}(\rho^{\prime}-\rho)X=x_{u_{0}}y_{u_{1}}+y_{u_{0}}x_{u_{s_{0}+1}}-2x_{u_{1}}y_{u_{1}}=x_{u_{0}}\left(y_{u_{1}}-\frac{y_{u_{0}}}{\rho}\right)-x_{u_{1}}\left(2y_{u_{1}}-\frac{\rho-1}{\rho}y_{u_{0}}\right)>0,$
implying that $\rho^{\prime}>\rho$, a contradiction. Therefore, if $e(S)\neq
3$, then $e(S)=s_{0}$ and $G^{\star}[S]\cong K_{1,e(S)}\cup(s-e(S)-1)K_{1}$.

Now suppose that $e(S)=3$. If $e(S)=e(N_{S}[u_{0}])=s_{0}+1$, then $s_{0}=2$
and $G^{\star}[S]\cong K_{3}\cup(s-3)K_{1}$, as required. So the remaining
case is $e(S)=e(N_{S}[u_{0}])=s_{0}$. In this situation, we have $s_{0}=3$ and
$G^{\star}[S]\cong K_{1,3}\cup(s-4)K_{1}$. Let
$G^{\prime}=G^{\star}-u_{0}u_{3}+u_{1}u_{2}$. Then it is clear that
$G^{\prime}[S]\cong K_{3}\cup(s-3)K_{1}$, and

$\displaystyle Y^{t}(\rho^{\prime}-\rho)X$
$\displaystyle=Y^{t}(A(G^{\prime})-A(G^{\star}))X=x_{u_{1}}y_{u_{2}}+x_{u_{2}}y_{u_{1}}-x_{u_{0}}y_{u_{3}}-x_{u_{3}}y_{u_{0}}=x_{u_{1}}y_{u_{0}}-x_{u_{0}}y_{u_{3}},$

where the last equality follows from the fact that
$x_{u_{1}}=x_{u_{2}}=x_{u_{3}}$ and $y_{u_{0}}=y_{u_{1}}=y_{u_{2}}$. As above,
by $\rho x_{u_{0}}=3x_{u_{1}}+\sum\limits_{i=0}^{t-1}x_{v_{i}}$, $\rho
x_{u_{1}}=x_{u_{0}}+\sum\limits_{i=0}^{t-1}x_{v_{i}}$,
$\rho^{\prime}y_{u_{0}}=2y_{u_{0}}+\sum\limits_{i=0}^{t-1}y_{v_{i}}$ and
$\rho^{\prime}y_{u_{3}}=\sum\limits_{i=0}^{t-1}y_{v_{i}}$, we obtain

$x_{u_{1}}=\frac{\rho+1}{\rho+3}x_{u_{0}}~{}~{}\mbox{and}~{}~{}y_{u_{3}}=\frac{\rho^{\prime}-2}{\rho^{\prime}}y_{u_{0}}\leq\frac{\rho-2}{\rho}y_{u_{0}}.$

Hence,

$x_{u_{1}}y_{u_{0}}-x_{u_{0}}y_{u_{3}}\geq
x_{u_{0}}y_{u_{0}}\left(\frac{\rho+1}{\rho+3}-\frac{\rho-2}{\rho}\right)=\frac{6}{\rho(\rho+3)}x_{u_{0}}y_{u_{0}}>0.$

Then $Y^{t}(\rho^{\prime}-\rho)X=x_{u_{1}}y_{u_{0}}-x_{u_{0}}y_{u_{3}}>0,$ and
so $\rho^{\prime}>\rho$, contrary to the maximality of $\rho(G^{\star})$.
Hence, if $e(S)=3$, then $e(S)=s_{0}+1$ and $G^{\star}[S]\cong
K_{3}\cup(s-3)K_{1}$. ∎

According to Claim 10, we only need to consider the following four cases. For
simplicity, we denote by $s^{\star}=e(S)$ and $t^{\star}=e(T)$.

$\underline{\mbox{Case 1.}}$ $G^{\star}[S]\cong K_{3}\cup(s-3)K_{1}$ and
$G^{\star}[T]\cong K_{3}\cup(t-3)K_{1}$.

In this situation, we have $x_{u_{0}}=x_{u_{1}}=x_{u_{2}}$,
$x_{u_{i}}=x_{u_{j}}$ for $i,j\in[3,s-1]$ and $x_{v_{0}}=x_{v_{1}}=x_{v_{2}},$
$x_{v_{i}}=x_{v_{j}}$ for $i,j\in[3,t-1]$. Combining $\rho
x_{u_{0}}=x_{u_{1}}+x_{u_{2}}+\sum\limits_{i=0}^{t-1}x_{v_{i}}=2x_{u_{0}}+\rho
x_{u_{3}}$ and $\rho
x_{v_{0}}=x_{v_{1}}+x_{v_{2}}+\sum\limits_{i=0}^{s-1}x_{u_{i}}=2x_{v_{0}}+\rho
x_{v_{3}}$ yields that

$x_{v_{3}}=\frac{\rho-2}{\rho}x_{v_{0}},~{}x_{u_{3}}=\frac{\rho-2}{\rho}x_{u_{0}}~{}~{}\mbox{and}~{}~{}(\rho-2)(x_{v_{0}}-x_{u_{0}})=\sum\limits_{i=0}^{s-1}x_{u_{i}}-\sum\limits_{i=0}^{t-1}x_{v_{i}}.$
(9)

Furthermore, we assert that $x_{v_{0}}\leq x_{u_{0}}$. Suppose to the contrary
that $x_{v_{0}}>x_{u_{0}}$, then we obtain
$\sum\limits_{i=0}^{s-1}x_{u_{i}}>\sum\limits_{i=0}^{t-1}x_{v_{i}}$. On the
other hand,

$\displaystyle\sum_{i=0}^{t-1}x_{v_{i}}$
$\displaystyle=\sum_{i=0}^{2}x_{v_{i}}+\sum_{i=3}^{t-1}x_{v_{i}}=3x_{v_{0}}+(t-3)x_{v_{3}}=3x_{v_{0}}+(t-3)\frac{\rho-2}{\rho}x_{v_{0}}$
$\displaystyle>3x_{u_{0}}+(s-3)\frac{\rho-2}{\rho}x_{u_{0}}=\sum_{i=0}^{s-1}x_{u_{i}},$

which is a contradiction.

Let $E^{\star}=\\{v_{0}v_{1},v_{0}v_{2},v_{1}v_{2},\\}$,
$E^{\prime}=\\{u_{0}u_{3},u_{0}u_{4},u_{3}u_{4}\\}$ and
$G^{\prime}=G^{\star}-E^{\star}+E^{\prime}$. We see that
$G^{\prime}[S]\cong(K_{1}\nabla 2K_{2})\cup(s-5)K_{1}$ and $G^{\prime}$ is
$\Gamma_{k}$-free, where $K_{1}\nabla 2K_{2}$ is a graph obtained from the
disjoint union $K_{1}\cup 2K_{2}$ by adding all edges between $K_{1}$ and
$2K_{2}.$ Then $y_{u_{1}}=y_{u_{2}}=y_{u_{3}}=y_{u_{4}}$,
$y_{u_{i}}=y_{u_{j}}$ for $i,j\in[5,s-1]$ and $y_{v_{i}}=y_{v_{j}}$ for
$i,j\in[0,t-1]$. By considering the eigenvalue-eigenvector equation of
$A(G^{\prime})$ with respect to $\rho^{\prime}$, we obtain

$\displaystyle\rho^{\prime}y_{u_{0}}=4y_{u_{1}}+\sum\limits_{i=0}^{t-1}y_{v_{i}},~{}\rho^{\prime}y_{u_{1}}=y_{u_{0}}+y_{u_{1}}+\sum\limits_{i=0}^{t-1}y_{v_{i}},~{}\rho^{\prime}y_{u_{5}}=\sum\limits_{i=0}^{t-1}y_{v_{i}},~{}~{}\rho^{\prime}y_{v_{0}}=y_{u_{0}}+4y_{u_{1}}+(s-5)y_{u_{5}},$

which gives that

$y_{u_{5}}=\left(1-\frac{4(\rho^{\prime}+1)}{\rho^{\prime}(\rho^{\prime}+3)}\right)y_{u_{0}}~{}\mbox{and}~{}y_{u_{1}}=\frac{\rho^{\prime}+1}{\rho^{\prime}+3}y_{u_{0}}.$
(10)

Hence,
$y_{v_{0}}=\frac{y_{u_{0}}}{\rho^{\prime}}\left(s-4+\frac{4(\rho^{\prime}+1)(\rho^{\prime}-s+5)}{\rho^{\prime}(\rho^{\prime}+3)}\right)=\frac{y_{u_{0}}}{\rho^{\prime}}\left(s-4+\frac{4(\rho^{\prime}+3)^{2}-4s(\rho^{\prime}+3)+8(s-2)}{\rho^{\prime}(\rho^{\prime}+3)}\right)$.
Combining this with $\rho^{\prime}>s=\lfloor\frac{n}{2}\rfloor$ (since
$G^{\prime}$ contains $K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$
as a proper subgraph), we deduce that

$y_{v_{0}}\leq\frac{y_{u_{0}}}{\rho^{\prime}}\left(\rho^{\prime}-4+\frac{4(\rho^{\prime}+3)^{2}-4\rho^{\prime}(\rho^{\prime}+3)+8(\rho^{\prime}-2)}{\rho^{\prime}(\rho^{\prime}+3)}\right)=\frac{y_{u_{0}}}{\rho^{\prime}}(\rho^{\prime}-4)+\emph{O}\left(\frac{1}{\rho^{\prime
2}}\right).$ (11)

Recall that $x_{v_{0}}\leq x_{u_{0}}$, and $X$ and $Y$ are the Perron vector
of $G^{\star}$ and $G^{\prime}$, respectively. Combining (9), (10) and (11),
we have

$\displaystyle Y^{t}(\rho^{\prime}-\rho)X$
$\displaystyle=Y^{t}(A(G^{\prime})-A(G))X=\sum\limits_{ij\in
E^{\prime}}(x_{i}y_{j}+y_{i}x_{j})-\sum\limits_{ij\in
E^{\star}}(x_{i}y_{j}+y_{i}x_{j})$
$\displaystyle=2((y_{u_{1}}x_{u_{0}}+(y_{u_{0}}+y_{u_{1}})x_{u_{3}})-3x_{v_{0}}y_{v_{0}})\geq
2((y_{u_{1}}x_{u_{0}}+(y_{u_{0}}+y_{u_{1}})x_{u_{3}})-3x_{u_{0}}y_{v_{0}})$
$\displaystyle=2x_{u_{0}}y_{u_{0}}\left(\frac{\rho^{\prime}+1}{\rho^{\prime}+3}+(1+\frac{\rho^{\prime}+1}{\rho^{\prime}+3})\frac{\rho-2}{\rho}\right)-6x_{u_{0}}y_{v_{0}}$
$\displaystyle\geq
2x_{u_{0}}y_{u_{0}}\left(\frac{\rho^{\prime}+1}{\rho^{\prime}+3}+(1+\frac{\rho^{\prime}+1}{\rho^{\prime}+3})\frac{\rho^{\prime}-2}{\rho^{\prime}}\right)-6x_{u_{0}}y_{v_{0}}$
$\displaystyle\geq
2x_{u_{0}}y_{u_{0}}\left(3-\frac{4}{\rho^{\prime}}-\frac{4}{\rho^{\prime}+3}-\frac{3}{\rho^{\prime}}(\rho^{\prime}-4)+\emph{O}\left(\frac{1}{\rho^{\prime
2}}\right)\right)$
$\displaystyle=2x_{u_{0}}y_{u_{0}}\left(\frac{12}{\rho^{\prime}}-\frac{4}{\rho^{\prime}}-\frac{4}{\rho^{\prime}+3}+\emph{O}\left(\frac{1}{\rho^{\prime
2}}\right)\right)>0.$

It follows that $\rho^{\prime}>\rho$, a contradiction.

$\underline{\mbox{Case 2.}}$ $G^{\star}[S]\cong
K_{1,s^{\star}}\cup(s-s^{\star}-1)K_{1}$ and $G^{\star}[T]\cong
K_{1,t^{\star}}\cup(t-t^{\star}-1)K_{1}$, where $s^{\star}\neq 3$ and
$t^{\star}\neq 3$.

Note that $s_{0}=e(N_{S}[u_{0}])$, $t_{0}=e(N_{T}[v_{0}])$ and
$s_{0}+t_{0}=k-1$. If $s_{0}=k-1,$ then $G^{\star}\cong
K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}\diamond K_{1,k-1},$ as
desired. So we may assume that $s_{0}\leq k-2.$ Observe that
$x_{u_{i}}=x_{u_{j}}$ for $i,j\in[1,s_{0}]$ and $x_{v_{i}}=x_{v_{j}}$ for
$i,j\in[1,t_{0}]$. Let $E^{\star}=\\{v_{0}v_{i}:1\leq i\leq t_{0}\\}$,
$E^{\prime}=\\{u_{0}u_{i}:s_{0}+1\leq i\leq k-1\\}$, and
$G^{\prime}=G^{\star}-E^{\star}+E^{\prime}.$ It is easy to see that
$G^{\prime}[S]\cong K_{1,k-1}\cup(s-k)K_{1}$ and $G^{\prime}$ is
$\Gamma_{k}$-free. By symmetry, $y_{u_{i}}=y_{u_{j}}$ for $i,j\in[1,k-1]$.
Then

$\displaystyle\rho
y_{u_{0}}=\sum_{i=1}^{k-1}y_{u_{i}}+\sum_{i=0}^{t-1}y_{v_{i}}=(k-1)y_{u_{1}}+\sum_{i=0}^{t-1}y_{v_{i}},~{}\rho
y_{u_{1}}=y_{u_{0}}+\sum_{i=0}^{t-1}y_{v_{i}},~{}\rho
y_{u_{k}}=\sum_{i=0}^{t-1}y_{v_{i}},$

which leads to

$y_{u_{1}}=\frac{\rho^{\prime}+1}{\rho^{\prime}+k-1}y_{u_{0}},~{}y_{u_{k}}=\frac{\rho^{\prime}y_{u_{1}}-y_{u_{0}}}{\rho^{\prime}},$

and

$\sum\limits_{i=0}^{s-1}y_{u_{i}}=\frac{\rho^{\prime
2}s+2\rho^{\prime}(k-1)-(k-1)s+k(k-1)}{\rho^{\prime}(\rho^{\prime}+k-1)}y_{u_{0}}\leq\frac{\rho^{\prime
3}+\rho^{\prime}(k-1)+k(k-1)}{\rho^{\prime}(\rho^{\prime}+k-1)}y_{u_{0}}.$

Notice that $\rho^{\prime}y_{v_{0}}=\sum\limits_{i=0}^{s-1}y_{u_{i}}.$ Then

$y_{v_{0}}\leq\frac{\rho^{\prime 3}+\rho^{\prime}(k-1)+k(k-1)}{\rho^{\prime
2}(\rho^{\prime}+k-1)}y_{u_{0}}.$ (12)

Similarly, we have $x_{u_{1}}=\frac{\rho+1}{\rho+s_{0}}x_{u_{0}}$,
$x_{u_{s_{0}+1}}=\frac{\rho^{2}-s_{0}}{\rho(\rho+s_{0})}x_{u_{0}}$. Since
$s=\lfloor\frac{n}{2}\rfloor<\rho$, it follows that

$\sum\limits_{i=0}^{s-1}x_{u_{i}}=\frac{\rho^{2}s+2\rho
s_{0}-s_{0}s+s_{0}^{2}+s_{0}}{\rho(\rho+s_{0})}x_{u_{0}}\leq\frac{\rho^{3}+\rho
s_{0}+s_{0}^{2}+s_{0}}{\rho(\rho+s_{0})}x_{u_{0}}.$

Hence, $x_{v_{1}}=\frac{\rho+1}{\rho+t_{0}}x_{v_{0}}$. According to $\rho
x_{v_{0}}=\sum\limits_{i=1}^{t_{0}}x_{v_{i}}+\sum\limits_{i=0}^{s-1}x_{u_{i}}=t_{0}x_{v_{1}}+\sum\limits_{i=0}^{s-1}x_{u_{i}},$
we obtain

$x_{v_{0}}\leq\frac{(\rho+k-1-s_{0})(\rho^{3}+\rho
s_{0}+s_{0}^{2}+s_{0})}{\rho(\rho+s_{0})(\rho^{2}-(k-1-s_{0}))}x_{u_{0}}.$

It follows that

$\displaystyle\frac{2\rho+k-s_{0}}{\rho+k-1-s_{0}}x_{v_{0}}y_{v_{0}}$ (13)
$\displaystyle\leq\frac{2\rho+k-s_{0}}{\rho+k-1-s_{0}}\cdot\frac{(\rho+k-1-s_{0})(\rho^{3}+\rho
s_{0}+s_{0}^{2}+s_{0})}{\rho(\rho+s_{0})(\rho^{2}-(k-1-s_{0}))}\cdot\frac{\rho^{\prime
3}+\rho^{\prime}(k-1)+k(k-1)}{\rho^{\prime
2}(\rho^{\prime}+k-1)}x_{u_{0}}y_{u_{0}}$
$\displaystyle=\frac{(2\rho+k-s_{0})(\rho^{3}+\rho
s_{0}+s_{0}(s_{0}+1))(\rho^{\prime
3}+\rho^{\prime}(k-1)+k(k-1))}{\rho\rho^{\prime
2}(\rho+s_{0})(\rho^{2}-(k-1-s_{0}))(\rho^{\prime}+k-1)}x_{u_{0}}y_{u_{0}}$
$\displaystyle=\left(\frac{2\rho^{4}\rho^{\prime 3}+\rho^{3}\rho^{\prime
3}(k-s_{0})}{\rho\rho^{\prime
2}(\rho+s_{0})(\rho^{2}-(k-1-s_{0}))(\rho^{\prime}+k-1)}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}y_{u_{0}}.$

Note that $X$ and $Y$ are the Perron vectors of $G^{\star}$ and $G^{\prime}$,
respectively. Then

$\displaystyle Y^{t}(\rho^{\prime}-\rho)X$
$\displaystyle=Y^{t}(A(G^{\prime})-A(G^{\star}))X=\sum\limits_{u_{0}u_{i}\in
E^{\prime}}(x_{u_{0}}y_{u_{i}}+y_{u_{0}}x_{u_{i}})-\sum\limits_{v_{0}v_{i}\in
E^{\star}}(x_{v_{0}}y_{v_{i}}+y_{v_{0}}x_{v_{i}})$ (14)
$\displaystyle=(k-1-s_{0})(x_{u_{0}}y_{u_{1}}+y_{u_{0}}x_{u_{s_{0}+1}}-x_{v_{0}}y_{v_{0}}-x_{v_{1}}y_{v_{0}})$
$\displaystyle=(k-1-s_{0})\left(\left(\frac{\rho^{\prime}+1}{\rho^{\prime}+k-1}+\frac{\rho^{2}-s_{0}}{\rho(\rho+s_{0})}\right)x_{u_{0}}y_{u_{0}}-\frac{2\rho+k-s_{0}}{\rho+k-1-s_{0}}x_{v_{0}}y_{v_{0}}\right).$

Recall that $s_{0}\leq k-2$. We shall prove $(\ref{case2-3})>0$ by showing

$\left(\frac{\rho^{\prime}+1}{\rho^{\prime}+k-1}+\frac{\rho^{2}-s_{0}}{\rho(\rho+s_{0})}\right)x_{u_{0}}y_{u_{0}}>\frac{2\rho+k-s_{0}}{\rho+k-1-s_{0}}x_{v_{0}}y_{v_{0}},$

which leads to $\rho^{\prime}>\rho$, and we derive a contradiction. According
to (13), it suffices to show

$\frac{\rho^{\prime}+1}{\rho^{\prime}+k-1}+\frac{\rho^{2}-s_{0}}{\rho(\rho+s_{0})}>\frac{2\rho^{4}\rho^{\prime
3}+\rho^{3}\rho^{\prime 3}(k-s_{0})}{\rho\rho^{\prime
2}(\rho+s_{0})(\rho^{2}-(k-1-s_{0}))(\rho^{\prime}+k-1)}+\emph{O}(\frac{1}{\rho^{2}}).$

The last inequality holds by
$\frac{\rho^{\prime}+1}{\rho^{\prime}+k-1}+\frac{\rho^{2}-s_{0}}{\rho(\rho+s_{0})}=\frac{2\rho^{4}(\rho^{\prime
3}+k\rho^{4}\rho^{\prime 2}+s_{0}\rho^{3}\rho^{\prime 3}}{\rho\rho^{\prime
2}(\rho+s_{0})(\rho^{2}-(k-1-s_{0}))(\rho^{\prime}+k-1)}+\emph{O}\left(\frac{1}{\rho^{2}}\right),$
as required.

$\underline{\mbox{Case 3.}}$ $G^{\star}[S]\cong
K_{1,s^{\star}}\cup(s-s^{\star}-1)K_{1}$ and $G^{\star}[T]\cong
K_{3}\cup(t-3)K_{1}$, where $s^{\star}\neq 3$.

Clearly, $k\geq 4$ and $s_{0}=k-4$. First we may assume that $k\geq 5$. Then
$x_{u_{i}}=x_{u_{j}}$ for $i,j\in[1,k-4]$ and $x_{v_{0}}=x_{v_{1}}=x_{v_{2}}$.
It follows that

$x_{u_{1}}=\frac{\rho+1}{\rho+k-4}x_{u_{0}},$ (15)

and

$x_{u_{k-3}}=\frac{\rho^{2}-k+4}{\rho(\rho+k-4)}x_{u_{0}}=\left(\frac{\rho}{\rho+k-4}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}=\left(1-\frac{k-4}{\rho+k-4}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}.$
(16)

Combining with $s=\lfloor\frac{n}{2}\rfloor<\rho$, we have

$\displaystyle\sum\limits_{i=0}^{s-1}x_{u_{i}}$
$\displaystyle=x_{u_{0}}+(k-4)x_{u_{1}}+(s-k+3)x_{u_{k-3}}=\frac{\rho^{2}s+2\rho(k-4)-s(k-4)+(k-4)(k-3)}{\rho(\rho+k-4)}x_{u_{0}}$
$\displaystyle\leq\frac{\rho^{3}+2\rho(k-4)-\rho(k-4)+(k-4)(k-3)}{\rho(\rho+k-4)}x_{u_{0}}=\left(\frac{\rho^{2}+k-4}{\rho+k-4}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}.$

Notice that $\rho
x_{v_{0}}=x_{v_{1}}+x_{v_{2}}+\sum\limits_{i=0}^{s-1}x_{u_{i}}=2x_{v_{0}}+\sum\limits_{i=0}^{s-1}x_{u_{i}}.$
Then we obtain

$x_{v_{0}}\leq\frac{1}{\rho-2}\left(\frac{\rho^{2}+k-4}{\rho+k-4}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}=\left(\frac{\rho^{2}+k-4}{(\rho-2)(\rho+k-4)}+\emph{O}\left(\frac{1}{\rho^{3}}\right)\right)x_{u_{0}}.$
(17)

Let $E^{\star}=\\{v_{0}v_{1},v_{0}v_{2},v_{1}v_{2}\\}$,
$E^{\prime}=\\{u_{0}u_{k-3},u_{0}u_{k-2},u_{0}u_{k-1}\\},$ and
$G^{\prime}=G^{\star}-E^{\star}+E^{\prime}$. Then $G^{\prime}\cong
K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}\diamond K_{1,k-1}$ and
$G^{\prime}$ is $\Gamma_{k}$-free. Note that

$y_{u_{1}}=\frac{\rho^{\prime}+1}{\rho^{\prime}+k-1}y_{u_{0}}=(1-\frac{k-2}{\rho^{\prime}+k-1})y_{u_{0}},~{}y_{u_{k}}=\frac{\rho^{\prime}y_{u_{1}}-y_{u_{0}}}{\rho^{\prime}},$
(18)

and

$\displaystyle\sum\limits_{i=0}^{s-1}y_{u_{i}}$
$\displaystyle=\frac{\rho^{\prime
2}s+2\rho^{\prime}(k-1)-s(k-1)+k(k-1)}{\rho^{\prime}(\rho^{\prime}+k-1)}y_{u_{0}}$
$\displaystyle\leq\frac{\rho^{\prime
3}+2\rho^{\prime}(k-1)-\rho^{\prime}(k-1)+k(k-1)}{\rho^{\prime}(\rho^{\prime}+k-1)}y_{u_{0}}=\left(\frac{\rho^{\prime
2}+k-1}{\rho^{\prime}+k-1}+\emph{O}\left(\frac{1}{\rho^{\prime
2}}\right)\right)y_{u_{0}},$

where the inequality by $s=\lfloor\frac{n}{2}\rfloor<\rho^{\prime}$. Then by
using $\rho^{\prime}y_{v_{0}}=\sum\limits_{i=0}^{s-1}y_{u_{i}}$, we have

$\displaystyle y_{v_{0}}\leq\frac{1}{\rho^{\prime}}\left(\frac{\rho^{\prime
2}+k-1}{\rho^{\prime}+k-1}+\emph{O}\left(\frac{1}{\rho^{\prime
2}}\right)\right)y_{u_{0}}=\left(\frac{\rho^{\prime
2}+k-1}{\rho^{\prime}(\rho^{\prime}+k-1)}+\emph{O}\left(\frac{1}{\rho^{\prime
3}}\right)\right)y_{u_{0}}.$ (19)

Thus, combining this with (17), we deduce

$\displaystyle\vspace{3mm}x_{v_{0}}y_{v_{0}}$
$\displaystyle\leq\left(\frac{\rho^{2}+k-4}{(\rho-2)(\rho+k-4)}+\emph{O}\left(\frac{1}{\rho^{3}}\right)\right)\left(\frac{\rho^{\prime
2}+k-1}{\rho^{\prime}(\rho^{\prime}+k-1)}+\emph{O}\left(\frac{1}{\rho^{\prime
3}}\right)\right)x_{u_{0}}y_{u_{0}}$ (20)
$\displaystyle=\left(\frac{(\rho^{2}+k-4)(\rho^{\prime
2}+k-1)}{\rho^{\prime}(\rho^{\prime}+k-1)(\rho-2)(\rho+k-4)}+\emph{O}\left(\frac{1}{\rho^{3}}\right)\right)x_{u_{0}}y_{u_{0}}.$

By symmetry, we have

$\displaystyle Y^{t}(\rho^{\prime}-\rho)X$
$\displaystyle=Y^{t}(A^{\prime}-A)X=\sum\limits_{ij\in
E^{\prime}}(x_{i}y_{j}+x_{j}y_{i})-\sum\limits_{ij\in
E^{\star}}(x_{i}y_{j}+x_{j}y_{i})$ (21)
$\displaystyle=3x_{u_{0}}y_{u_{1}}+3y_{u_{0}}x_{u_{k-3}}-6x_{v_{0}}y_{v_{0}}.$

Now, we shall show $(\ref{iii-5})>0$. According to (16) and (18), we change
(21) to
$3x_{u_{0}}y_{u_{0}}(\frac{\rho^{\prime}+1}{\rho^{\prime}+k-1}+\frac{\rho^{2}-k+4}{\rho(\rho+k-4)})-6x_{v_{0}}y_{v_{0}}.$
Thus, combining with (20), it suffices to prove

$\frac{\rho^{\prime}+1}{\rho^{\prime}+k-1}+\frac{\rho^{2}-k+4}{\rho(\rho+k-4)}>2\left(\frac{(\rho^{2}+k-4)(\rho^{\prime
2}+k-1)}{\rho^{\prime}(\rho^{\prime}+k-1)(\rho-2)(\rho+k-4)}+\emph{O}\left(\frac{1}{\rho^{3}}\right)\right).$

Let us multiply both sides of this inequality by
$\rho^{\prime}\rho(\rho^{\prime}+k-1)(\rho-2)(\rho+k-4).$ Then it suffices to
show

$\rho\rho^{\prime}(\rho^{\prime}+1)(\rho-2)(\rho+k-4)+\rho^{\prime}(\rho^{\prime}+k-1)(\rho-2)(\rho^{2}-k+4)>2\rho(\rho^{2}+k-4)(\rho^{\prime
2}+k-1)+\emph{O}(\rho^{2}).$

By calculation, we only need to prove that $\rho^{2}\rho^{\prime
2}(k-8)+\rho^{3}\rho^{\prime}k>0$ since
$\rho=\emph{O}(n),\rho^{\prime}=\emph{O}(n).$ Note that $\rho>\rho^{\prime}$.
Then

$\rho^{2}\rho^{\prime 2}(k-8)+\rho^{3}\rho^{\prime}k>\rho^{2}\rho^{\prime
2}(k-8)+\rho^{2}\rho^{\prime 2}k=\rho^{2}\rho^{\prime 2}(2k-8).$

Thus, for $k\geq 5$, we have $\rho^{\prime}>\rho$ by (21), a contradiction.

For $k=4,$ we see that $G^{\star}[N_{T}[v_{0}]]\cong K_{3}$, and
$G^{\star}[N_{S}[u_{0}]]$ is an empty graph. If $s=t=\frac{n}{2}$, then
$G^{\star}\cong K_{\frac{n}{2},\frac{n}{2}}\diamond K_{3}$, as desired. If
$s=t-1=\frac{n-1}{2}$, then let
$E^{\star}=\\{v_{0}v_{1},v_{0}v_{2},v_{1}v_{2}\\}$,
$E^{\prime}=\\{u_{0}u_{1},u_{0}u_{2},u_{1}u_{2}\\}$ and
$G^{\prime}=G^{\star}-E^{\star}+E^{\prime}.$ Then $G^{\prime}\cong
K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}\diamond K_{3}$ and
$G^{\prime}$ is $\Gamma_{4}$-free. Notice that the quotient matrix of
$A(G^{\star})$ with respect to the partition
$\Pi^{\star}:V(G^{\star})=\\{u_{0},\cdots,u_{s-1}\\}\cup\\{v_{0},v_{1},v_{2}\\}\cup\\{v_{3},\cdots,v_{t-1}\\}$
is given by

$B_{1}=\left(\begin{array}[]{ccc}0&3&t-3\\\ s&2&0\\\ s&0&0\\\
\end{array}\right).$

Furthermore, the characteristic polynomial of $B_{1}$ is
$\varphi(B_{1},x)=x^{3}-2x^{2}-stx+2s(t-3),$ and its largest root coincides
with $\rho$ by Lemma 2 since the partition is equitable. By symmetry, the
characteristic polynomial $\varphi(B_{2},x)$ of the quotient matrix $B_{2}$ of
$A(G^{\prime})$ with respect to the partition
$\Pi^{\prime}:V(G^{\prime})=\\{v_{0},\cdots,v_{t-1}\\}\cup\\{u_{0},u_{1},u_{2}\\}\cup\\{u_{3},\cdots,u_{s-1}\\}$
can be obtained from $\varphi(B_{1},x)$ by switching $s$ and $t$. The
partition is also equitable, then by Lemma 2, $\rho^{\prime}=\rho(B_{2})$.
Notice that $\rho>s=\frac{n-1}{2}$ and $s+t=n.$ By a simple calculation, we
have

$\varphi(B_{2},\rho)=\varphi(B_{2},\rho)-\varphi(B_{1},\rho)=-4\rho^{2}-\left(\frac{n^{2}}{2}-\frac{1}{2}\right)\rho+n^{2}-6n-1.$

Thus
$\varphi(B_{2},\rho)<\varphi(B_{2},\frac{n-1}{2})=-\frac{n^{3}}{4}+\frac{n^{2}}{4}-\frac{15n}{4}-\frac{9}{4}<0$,
as required. Therefore, $\rho<\rho^{\prime}$, which leads to a contradiction.

$\underline{\mbox{Case 4.}}$ $G^{\star}[S]\cong K_{3}\cup(s-3)K_{1}$ and
$G^{\star}[T]\cong K_{1,t^{\star}}\cup(t-t^{\star}-1)K_{1}$, where
$t^{\star}\neq 3$.

Then $x_{u_{0}}=x_{u_{1}}=x_{u_{2}}$ and $x_{v_{i}}=x_{v_{j}}$ for
$i,j\in[1,k-4]$. It follows that

$\displaystyle
x_{v_{1}}=\frac{\rho+1}{\rho+k-4}x_{v_{0}},~{}x_{u_{3}}=\frac{\rho-2}{\rho}x_{u_{0}},$
(22)

and

$\displaystyle\sum\limits_{i=0}^{s-1}x_{u_{i}}=3x_{u_{0}}+(s-3)x_{u_{3}}=\frac{\rho
s-2s+6}{\rho}x_{u_{0}}\leq\frac{\rho^{2}+2\rho+6}{\rho}x_{u_{0}}=(\rho-2+\frac{6}{\rho})x_{u_{0}},$

where the inequality above holds as $s=\lfloor\frac{n}{2}\rfloor<\rho$. Notice
that

$\rho
x_{v_{0}}=\sum\limits_{i=1}^{k-4}x_{v_{i}}+\sum\limits_{i=0}^{s-1}x_{u_{i}}=(k-4)x_{v_{1}}+\sum\limits_{i=0}^{s-1}x_{u_{i}}.$

Then

$\displaystyle
x_{v_{0}}=\left(\frac{(k-4)(\rho+1)}{\rho(\rho+k-4)}+\frac{\rho-2}{\rho}+\frac{6}{\rho^{2}}\right)x_{u_{0}}\leq\left(1+\frac{k-4}{\rho+k-4}-\frac{2}{\rho}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}.$
(23)

Let $E^{\star}=\\{v_{0}v_{1},v_{0}v_{2},...,v_{0}v_{k-4},u_{1}u_{2}\\}$,
$E^{\prime}=\\{u_{0}u_{3},u_{0}u_{4},...,u_{0}u_{k-1}\\}$ and
$G^{\prime}=G^{\star}-E^{\star}+E^{\prime}.$ Then $G^{\prime}\cong
K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}\diamond K_{1,k-1}$ and
$G^{\prime}$ is $\Gamma_{k}$-free. By (19) and (23), we have

$\displaystyle\vspace{3mm}x_{v_{0}}y_{v_{0}}$
$\displaystyle\leq\left(1-\frac{2}{\rho}+\frac{k-4}{\rho+k-4}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)\left(\frac{\rho^{\prime}}{\rho^{\prime}+k-1}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}y_{u_{0}}$
$\displaystyle=\left(1+\frac{k-4}{\rho+k-4}-\frac{2}{\rho}-\frac{k-1}{\rho^{\prime}+k-1}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}y_{u_{0}}.$

Combining with (18) and (22), we have

$\displaystyle
Y^{t}(\rho^{\prime}-\rho)X=Y^{t}(A^{\prime}-A)X=\sum\limits_{ij\in
E^{\prime}}(x_{i}y_{j}+x_{j}y_{i})-\sum\limits_{ij\in
E^{\star}}(x_{i}y_{j}+x_{j}y_{i})$
$\displaystyle=(k-3)(x_{u_{0}}y_{u_{1}}+x_{u_{1}}y_{u_{3}})-(k-4)(x_{v_{0}}y_{v_{1}}+y_{v_{0}}x_{v_{1}})-2x_{u_{0}}y_{u_{1}}$
$\displaystyle=((k-5)(1-\frac{k-2}{\rho^{\prime}+k-1})+(k-3)(1-\frac{2}{\rho}))x_{u_{0}}y_{u_{0}}-(k-4)(2-\frac{k-5}{\rho+k-4})x_{v_{0}}y_{v_{0}}$
$\displaystyle\geq\left(2k-8-\frac{(k-5)(k-2)}{\rho^{\prime}+k-1}-\frac{2(k-3)}{\rho}\right)x_{u_{0}}y_{u_{0}}$
$\displaystyle~{}~{}~{}~{}~{}-\left(2k-8-\frac{(k-5)(k-4)}{\rho+k-4}\right)\left(1+\frac{k-4}{\rho+k-4}-\frac{2}{\rho}-\frac{k-1}{\rho^{\prime}+k-1}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}y_{u_{0}}$
$\displaystyle=\left(\frac{k^{2}-k-2}{\rho^{\prime}+k-1}+\frac{2(k-5)}{\rho}-\frac{(k-4)(k-3)}{\rho+k-4}+\emph{O}\left(\frac{1}{\rho^{2}}\right)\right)x_{u_{0}}y_{u_{0}}>0.$

It follows that $\rho^{\prime}>\rho$, which is impossible. This completes the
proof of Case 4.

Considering Case 1-4, we complete the proof of Theorem 5. $\hfill\blacksquare$

##  4 Conclusion remark

Bollobás [2] asked: what is the maximum size of a graph
$G\in\overline{\Omega^{\prime}_{k}}$ with order $n$? In this paper, we pose a
spectral analogue problem as follows.

######  Problem 4.1.

What is the maximum spectral radius of a graph
$G\in\overline{\Omega^{\prime}_{k}}$ with $k\geq 3$ and order $n$?

Ma and Yang [24] proved that $f(n)<n+\sqrt{n}+o(n)$ for any $n$-vertex
2-connected graph. Theorem 2 shows that the graph with the maximum spectral
radius among all graphs with no two cycles of the same length has a cut
vertex. So it is natural to ask the following problem.

######  Problem 4.2.

What is the maximum spectral radius among all 2-connected $n$-vertex graphs
with no two cycles of the same length?

## References

  * [1] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications (Macmillan, New York, 1976).
  * [2] B. Bollbás, Extremal graph theory, London Mathematical Society Monographs, 11. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-NewYork, 1978. xx+488 pp. ISBN: 0-12-111750-2.
  * [3] E. Boros, Y. Caro, Z. Füredi, R. Yuster, Covering non-uniform hypergraphs, _J. Combin. Theory Ser. B_ 82 (2001) 270–284.
  * [4] A.E. Brouwer, W.H. Haemers, Spectra of Graphs, Springer, Berlin, 2011.
  * [5] V. Chvátal, D. Hanson, Degrees and matchings, J. Combin. Theory Ser. B, 20 (1976) 128–138.
  * [6] M. Chen, X. Zhang, Some new results and problems in spectral extremal graph theory (in Chinese), _J. Anhui Univ. Nat. Sci._ 42 (2018) 12–25.
  * [7] S.M. Cioabă, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, arXiv: 2104.07729v1.
  * [8] S.M. Cioabă, L. Feng, M. Tait, X. Zhang, The spectral radius of graphs with no intersecting triangles, _Electron. J. Combin._ 27 (2020), no. 4, Paper No. 4.22, 19 pp.
  * [9] G. Chen, J. Lehel, M.S. Jacobson, W.E. Shreve, Note on graphs without repeated cycle lengths, _J. Graph Theory_ 29 (1998) 11–15.
  * [10] P. Erdős, L. Posa, On independent circuits contained in a graph, _Canadian J. Math._ 17 (1965) 347–352.
  * [11] O. Favaron, M. Mahéo, J.-F. Saclé, Some eigenvalue properties in graphs (conjectures of Graffiti. II), _Discrete Math._ 111 (1993) 197–220.
  * [12] J. Gao, X. Hou, The spectral radius of graphs without long cycles, _Linear Algebra Appl._ 566  (2019) 17–33.
  * [13] J. Ge, B. Ning, Spectral radius and Hamiltonian properties of graphs, II, _Linear Multilinear Algebra_ 68 (2020) 2298–2315.
  * [14] D. Gerbner, E. Győri, A. Methuku, M. Vizer, Generalized Turán problems for even cycles, _J. Combin. Theory Ser. B_ 145 (2020) 169–213.
  * [15] C. Godsil, G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001.
  * [16] E. Győri, On the number of edge disjoint cliques in graphs of given size, _Combinatorica_ 11 (1991) 231–243.
  * [17] A.J. Hoffman, J.H. Smith, in: Fiedler (Ed.), Recent Advances in Graph Theory, Academia Praha, New York, 1975, pp. 273–281.
  * [18] B. Li, B. Ning, The stability method, eigenvalues and cycles of consecutive lengths, arXiv:2102.03855
  * [19] H. Lin, B. Ning, B. Wu, Eigenvalues and triangles in graphs, _Combin. Probab. Comput._ 30 (2021) 258–270.
  * [20] C. Lai, Graphs without repeated cycle lengths, _Australas. J. Combin._ 27 (2003) 101–105.
  * [21] C. Lai, On the size of graphs without repeated cycle lengths, _Discrete Appl. Math._ 232 (2017) 226–229.
  * [22] C. Lai, On the number of edges in some graphs, _Discrete Appl. Math._ 283 (2020) 751–755.
  * [23] Y. Li, Y. Peng, The spectral radius of graphs with no intersecting odd cycles, arXiv:2106.00587.
  * [24] J. Ma, T. Yang, Non-repeated cycle lengths and Sidon sequences, _Israel J. Math._ , to appear, arXiv:2007.12513.
  * [25] V. Nikiforov, A spectral condition for odd cycles in graphs, _Linear Algebra Appl._ 428 (2008) 1492–1498.
  * [26] V. Nikiforov, Degree powers in graphs with a forbidden even cycle, _Electron. J. Combin._ 16 (2009), no. 1, Research Paper 107, 9 pp.
  * [27] V. Nikiforov, The maximum spectral radius of $C_{4}$-free graphs of given order and size, _Linear Algebra Appl._ 430 (2009) 2898–2905.
  * [28] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, _Linear Algebra Appl._ 432 (2010) 2243–2256.
  * [29] V. Nikiforov, Some new results in extremal graph theory. Surveys in combinatorics 2011, 141–181, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011
  * [30] B. Ning, X. Peng, Extensions of the Erdős-Gallai theorem and Luo’s theorem, _Combin. Probab. Comput._ 29 (2020) 128–136.
  * [31] Y. Shi, On maximum cycle-distributed graphs, _Discrete Math._ 71 (1988) 57–71.
  * [32] B. Wu, E. Xiao, Y. Hong, The spectral radius of trees on $k$ pendant vertices, _Linear Algebra Appl._ 395 (2005) 343–349.
  * [33] W. Yuan, B. Wang, M. Zhai, On the spectral radii of graphs without given cycles, _Electron. J. Linear Algebra_ 23 (2012) 599–606.
  * [34] M. Zhai, H. Lin, Spectral extrema of graphs: forbidden hexagon, _Discrete Math._ 343 (2020), no. 10, 112028, 6 pp.
  * [35] M. Zhai, H. Lin, A strengthening of the spectral color critical edge theorem: books and theta graphs, arXiv:2102.04041.
  * [36] M. Zhai, B. Wang, Proof of a conjecture on the spectral radius of $C_{4}$-free graphs, _Linear Algebra Appl._ 437 (2012) 1641–1647.
  * [37] X. Zhang, R. Luo, The spectral radius of triangle-free graphs, _Australas. J. Combin._ 26 (2002) 33–39.