# Spectral conditions implying the existence of doubly chorded cycles without
or with constraints

Leyou Xu111Email<EMAIL_ADDRESS>Bo Zhou222Email<EMAIL_ADDRESS>
School of Mathematical Sciences, South China Normal University
Guangzhou 510631, P.R. China

###### Abstract

What spectral conditions imply a graph contains a chorded cycle? This question
was asked by R.J. Gould in 2022. We answer three modified versions of Gould’s
question by giving tight spectral conditions that imply the existence of
doubly chorded cycle, a doubly chorded cycle with two chords incident to a
vertex, and a doubly chorded cycle on five vertices with two chords incident
to one vertex, in a graph, respectively.

Keywords: doubly chorded cycle, spectral condition, spectral radius

Mathematics Subject Classification: 05C50, 05C38

##  1 Introduction

One of the classical questions in combinatorics is as follows: What bounds for
the size imply an $n$-vertex graph contains a subgraph with a certain
prescribed structure? Its spectral version is: What spectral conditions imply
an $n$-vertex graph contains a subgraph with a certain prescribed structure?

We consider only simple graphs. Let $G$ be a graph with vertex set $V(G)$ and
edge set $E(G)$. Let $\delta(G)$ denote the minimum degree of $G$. The
adjacency matrix $A(G)$ of $G$ is the matrix $(a_{uv})_{u,v\in V(G)}$, where
$a_{uv}=1$ if $u$ and $v$ are adjacent and $0$ otherwise. The largest
eigenvalue of $A(G)$ is called the spectral radius of $G$, denoted by
$\rho(G)$. The above question may be rephrased via the spectral radius as:
Among $n$-vertex graphs that do not contain a subgraph with a certain
prescribed structure, what is the maximum spectral radius and which graphs
achieve this value? Such questions, originated from [5] and called
Brualdi–Solheid–Turán type problems in [20], received much attention in recent
years, see, e.g. [8, 18, 20, 23, 27, 28].

Let $K_{s}$ denote the complete graph on $s$ vertices. For positive integers
$n_{1},\dots,n_{k}$ with $k\geqslant 2$, let $K_{n_{1},\dots,n_{k}}$ denote
the complete $k$-partite graph with part sizes $n_{1},\dots,n_{k}$.

Let $C$ be a cycle of a graph. We say an edge that joins two vertices of a
cycle $C$ is a chord of $C$ if the edge is not itself an edge of $C$. If $C$
has at least one chord, then it is called a chorded cycle, and if $C$ has at
least two chords, then it is called a doubly chorded cycle (DCC for short).
The study of cycles in graphs is well established. The existence of cycles
with additional properties such as containing at least $s$ chords for some
number $s\geqslant 1$ received much attention, see [10, 7, 12, 15] and
references therein. For $s=1,2$, the cycles are just chorded cycles and doubly
chorded cycles.

Given a graph $G$, Pósa [21] suggested the problem of finding degree
conditions that imply the existence of a chorded cycle in $G$. Czipser proved
(see problem 10.2, p. 65 in [19]) that $\delta(G)\geqslant 3$ suffices. Gould
asked in [15] the following question: What spectral conditions imply a graph
contains a chorded cycle? Zheng et al. [29] answered Gould’s question by
showing that any graph $G$ of order $n\geqslant 6$ with
$\rho(G)\geqslant\rho(K_{2,n-2})$ contains a chorded cycle unless $G\cong
K_{2,n-2}$. Different answers are provided via the signless Laplacian spectral
radius [24]. Gould et al. [16] observed that it is only slightly more
difficult to show that $\delta(G)\geqslant 3$ implies $G$ contains a DCC. So
it is more natural to consider conditions implying the existence of DCCs [16,
22]. We try to answer the following three questions, which may be viewed as
modified versions of Gould’s original question.

######  Question 1.1.

What spectral conditions imply a graph on $n$ vertices contains a DCC?

The problem to determine the maximum size of an $n$-vertex graph that does not
contain a cycle with many chords incident to a vertex received much attention.
Through the work of Erdős, Lewin (see [1, p. 398, no. 12]) and Bollobás [1, p.
398, no. 12], Jiang [17] showed that for any $n$-vertex graph with $n\geqslant
9$ that does not contain a DCC with two chords incident to a vertex,
$|E(G)|\leqslant 3n-9$, and it is attained if $G\cong K_{3,n-3}$.

We call a DCC with two chords incident to a vertex a DCC1.

######  Question 1.2.

What spectral conditions imply a graph on $n$ vertices contains a DCC1?

Let $G\cup H$ be the disjoint union of graphs $G$ and $H$. The disjoint union
of $k$ copies of a graph $G$ is denoted by $kG$. The join of disjoint graphs
$G$ and $H$, denoted by $G\vee H$, is the graph obtained from $G\cup H$ by
adding all possible edges between vertices in $G$ and vertices in $H$. Note
that $K_{1}\vee P_{4}$ is the unique $5$-vertex DCC1. There are spectral
conditions for a graph with fixed size which imply the existence of a copy of
$K_{1}\vee P_{4}$ [25]. There is also a paper considering the spectral
extremal graphs of graphs containing no copies of $K_{1}\vee P_{2k}$ with
$k\geqslant 3$ for sufficiently large order [26]. Zhao et al. [28] determined
the $n$-vertex graphs that maximize the spectral radius among graphs that do
not contain any wheels $W_{r}:=P_{1}\vee C_{r}$ for $r\geqslant 3$. A graph
that does not contain copies of $K_{1}\vee P_{4}$ does not contain any wheels
$W_{r}$ for $r\geqslant 4$ but it may contain $W_{3}$ (i.e., $K_{4}$). A graph
that does not contains any wheels may contain $K_{1}\vee P_{4}$.

######  Question 1.3.

What spectral conditions imply a graph on $n$ vertices contains a copy of
$K_{1}\vee P_{4}$?

Questions 1.1, 1.2 and 1.3 are answered by the following Theorems 1.1, 1.2 and
1.3, respectively.

######  Theorem 1.1.

Suppose that $G$ is an $n$-vertex graph containing no DCCs, where $n\geqslant
3$. Then $\rho(G)\leqslant\tfrac{1}{2}+\sqrt{2n-\tfrac{15}{4}}$ with equality
if and only if $G\cong K_{1,1,n-2}$.

Let $F_{1}$ be the graph obtained from $K_{2}$ and $K_{4}$ by identifying a
vertex.

######  Theorem 1.2.

Suppose that $G$ is an $n$-vertex graph containing no DCC1s. Then

$\rho(G)\leqslant\begin{cases}n-1&\mbox{ if }n\leqslant 4\\\ 3.0861&\mbox{ if
}n=5\\\ \frac{1}{2}+\sqrt{2n-\frac{15}{4}}&\mbox{ if }6\leqslant n\leqslant
9\\\ \sqrt{3(n-3)}&\mbox{ if }n\geqslant 10\end{cases}$

with equality if and only if

$G\cong\begin{cases}K_{n}&\mbox{ if }n\leqslant 4,\\\ F_{1}&\mbox{ if }n=5,\\\
K_{1,1,n-2}&\mbox{ if }6\leqslant n\leqslant 9,\\\ K_{3,n-3}&\mbox{ if
}n\geqslant 10.\end{cases}$ (1.1)

By Theorem 1.2, if $G$ is a $5$-vertex graph containing no copies of
$K_{1}\vee P_{4}$, then $\rho(G)\leqslant\rho(F_{1})$ with equality if and
only if $G\cong F_{1}$.

######  Theorem 1.3.

Suppose that $G$ is an $n$-vertex graph containing no copies of $K_{1}\vee
P_{4}$ with $n\geqslant 6$. Then

$\rho(G)\leqslant\begin{cases}\frac{n+1}{2}&\mbox{ if }n\equiv 1\pmod{2}\\\
\frac{1+\sqrt{n^{2}+1}}{2}&\mbox{ if }n\equiv 0\pmod{4}\\\ \eta(n)&\mbox{ if
}n\equiv 2\pmod{4}\end{cases}$

with equality if and only if $G\cong H_{n}$, where

$H_{n}=\begin{cases}\frac{n+1}{2}K_{1}\vee\frac{n-1}{4}K_{2}&\mbox{ if
}n\equiv 1\pmod{4},\\\ \frac{n-1}{2}K_{1}\vee\frac{n+1}{4}K_{2}&\mbox{ if
}n\equiv 3\pmod{4},\\\ \frac{n}{2}K_{1}\vee\frac{n}{4}K_{2}&\mbox{ if }n\equiv
0\pmod{4},\\\ \frac{n}{2}K_{1}\vee(\frac{n-2}{4}K_{2}\cup K_{1})&\mbox{ if
}n\equiv 2\pmod{4},\end{cases}$

and $\eta(n)$ is the largest root of
$x^{3}-x^{2}-\tfrac{n^{2}}{4}x+\tfrac{n}{2}=0$.

##  2 Preliminaries

Let $G$ be a graph. For $v\in V(G)$, we denote by $N_{G}(v)$ the neighborhood
of $v$ in $G$, and $d_{G}(v)$ the degree of $v$ in $G$. Let
$N_{G}[v]:=\\{v\\}\cup N_{G}(v)$ be the closed neighborhood of $v$. For
simplicity, we use $d_{u}$ for $d_{G}(u)$ if there is no ambiguity. For
$S\subseteq V(G)$, let $N_{S}(v)=N_{G}(v)\cap S$ and $d_{S}(v)=|N_{S}(v)|$
whether $v\in S$ or not. For $S,T\subset V(G)$, let $e(S,T)$ be the number of
edges between $S$ and $T$. Particularly, if $S=T$, then $e(S)$ denotes the
number of edges in $G[S]$ (the subgraph of $G$ induced by $S$). The set $S$ is
independent if $G[S]$ has no edges.

For a nontrivial graph $G$ with $v\in V(G)$, $G-v$ denotes the graph obtained
from $G$ by removing $v$ and its incident edges.

A vertex $v$ in a connected graph $G$ is a cut vertex if $G-v$ is
disconnected, equivalently, there exist vertices $u$ and $w$ distinct from $v$
such that there is at least one path from $u$ to $w$ in $G$ and $v$ lies on
every such path in $G$.

For a graph $G$ with two nonadjacent vertices $u$ and $v$, denote by $G+uv$
the graph obtained from $G$ by adding the edge $uv$. If $wz$ is an edge of
$G$, then $G-wz$ is the graph obtained from $G$ be removing the edge $wz$.

The following lemma is an immediate consequence of the Perron-Frobenius
theorem.

######  Lemma 2.1.

Let $G$ be a graph and $u$ and $v$ two nonadjacent vertices of $G$. If $G+uv$
is connected, then $\rho(G+uv)>\rho(G)$.

If $G$ is a connected graph, then $A(G)$ is irreducible, so by Perron-
Frobenius theorem, there exists a unique unit positive eigenvector of $A(G)$
corresponding to $\rho(G)$, which we call the Perron vector of $G$.

######  Lemma 2.2.

[4] Let $G$ be a connected graph with $\\{u,v,w\\}\subseteq V(G)$ such that
$uw\notin E(G)$ and $vw\in E(G)$. If $\mathbf{x}$ is the Perron vector of $G$
with $x_{u}\geqslant x_{v}$, then $\rho(G-vw+uw)>\rho(G)$.

If $\mathbf{x}^{\prime}$ is the Perron vector of $G-vw+uw$ in Lemma 2.2, then
$x^{\prime}_{u}>x^{\prime}_{v}$ by Lemma 2.2. So Lemma 2.2 has the equivalent
form: Let $G$ be a connected graph with $\\{u,v\\}\subset V(G)$ and
$N_{G}(v)\setminus N_{G}[u]\neq\emptyset$. If $\mathbf{x}$ is the Perron
vector of $G$ with $x_{u}\geqslant x_{v}$, then for any nonempty $N\subseteq
N_{G}(v)\setminus N_{G}[u]$, $\rho(G-\\{vw:w\in N\\}+\\{uw:w\in
N\\})>\rho(G)$.

For a graph $G$ with $u,v\in V(G)$, the $(u,v)$-entry of $A(G)^{2}$ is equal
to the number of walks of length two from $u$ to $v$. If $\mathbf{x}$ is the
Perron vector of $G$, then $\mathbf{x}$ is an eigenvector of $A(G)^{2}$
corresponding to the eigenvalue $\rho(G)^{2}$, so

$\rho(G)^{2}x_{u}=d_{G}(u)x_{u}+\sum_{v\in
N_{G}(u)}d_{N_{G}(u)}(v)x_{v}+\sum_{v\in V(G)\setminus
N_{G}[u]}d_{N_{G}(u)}(v)x_{v}.$ (2.1)

Suppose that $V(G)$ is partitioned as $V_{1}\cup\dots\cup V_{m}$. For
$1\leqslant i<j\leqslant m$, set $A_{ij}$ to be the submatrix of $A(G)$ with
rows corresponding to vertices in $V_{i}$ and columns corresponding to
vertices in $V_{j}$. The quotient matrix of $A(G)$ with respect to the
partition $V_{1}\cup\dots\cup V_{m}$ is denoted by $B=(b_{ij})$, where
$b_{ij}=\tfrac{1}{|V_{i}|}\sum_{u\in V_{i}}\sum_{v\in V_{j}}a_{uv}$. If
$A_{ij}$ has constant row sum, then we say $B$ is an equitable quotient
matrix. The following lemma is an immediate consequence of [3, Lemma 2.3.1].

######  Lemma 2.3.

For a connected graph $G$, if $B$ is an equitable quotient matrix of $A(G)$,
then the eigenvalues of $B$ are also eigenvalues of $A(G)$ and $\rho(G)$ is
equal to the largest eigenvalue of $B$.

Let $G_{1}$ and $G_{2}$ be two graphs with $u\in V(G_{1})$ and $v\in
V(G_{2})$. Denote by $G_{1}uvG_{2}$ the graph obtained by identifying the
vertices $u$ and $v$, which we call this graph the coalescence of $G_{1}$ and
$G_{2}$ at $u$ and $v$. If $u=v$, then we denote by $G_{1}uG_{2}$ for
simplicity.

######  Lemma 2.4.

[9] Let $G_{1}$ be a graph with $u\in V(G_{1})$ and $G_{2}$ a connected graph
with $v,w\in V(G_{2})$. If $\rho(G_{2}-v)<\rho(G_{2}-w)$, then
$\rho(G_{1}uvG_{2})>\rho(G_{1}uwG_{2})$.

######  Lemma 2.5.

[9] Let $G$ be a connected graph with $u\in V(G)$, $H_{1}$ and $H_{2}$ be two
graphs of the same order with $v_{i}\in V(H_{i})$ for $i=1,2$. If
$\rho(H_{1})>\rho(H_{2})$ and $\rho(H_{1}-v_{1})\leqslant\rho(H_{2}-v_{2})$,
then $\rho(Guv_{1}H_{1})>\rho(Guv_{2}H_{2})$.

######  Lemma 2.6.

[13] We have

$\rho(K_{1,1,n-2})=\frac{1}{2}+\sqrt{2n-\frac{15}{4}}\mbox{ and
}\rho(K_{3,n-3})=\sqrt{3(n-3)}.$

Moreover, $\rho(K_{3,n-3})>\rho(K_{1,1,n-2})$ if and only if $n\geqslant 10$.

Denote by $d_{G}(u,v)$ the distance between vertices $u$ and $v$ in a graph
$G$. Let $u$ and $v$ be two vertices of $G$ and $P$ be a path from $u$ to $v$
in $G$. Moreover, if $w$ and $z$ are two vertices on $P$ with
$d_{P}(u,w)<d_{P}(u,z)$, then $P[w,z]$ denotes the segment of $P$ from $w$ to
$z$.

If a component of a graph is $K_{1}$, $K_{2}$, or $K_{1,s}$ with $s\geqslant
2$, then we call it an isolated vertex, an isolated edge, or a star (in which
the vertex of degree $s$ is its center). As usual, a copy of $K_{3}$ is called
a triangle. A vertex of degree one is also called a pendant vertex.

We use $I_{n}$ to denote the identity matrix of order $n$.

##  3 Proof of Theorem 1.1

######  Lemma 3.1.

[6] If $G$ is an $n$-vertex graph containing no DCCs, then $e(G)\leqslant
2n-3$.

###### Proof of Theorem 1.1.

The case for $n=3,4$ can be checked easily. Suppose that $n\geqslant 5$.
Suppose that $G$ is a graph that maximizes the spectral radius among all
graphs on $n$ vertices containing no DCCs. It suffices to show that $G\cong
K_{1,1,n}$.

If $G$ is not connected with components $G_{1},\dots,G_{r}$, then we obtain a
graph $G^{\prime}$ by choosing $v_{i}\in V(G_{i})$ for $i=1,\dots,r$ and
adding edges $v_{1}v_{j}$ for all $j=2,\dots,j$, which obviously does not
contain a DCC, and we have by Lemma 2.1 that $\rho(G^{\prime})>\rho(G)$, which
is a contradiction. Thus, $G$ is connected.

Let $\rho=\rho(G)$. Denote by $\mathbf{x}$ the Perron vector of $G$. Let $u$
be a vertex with maximum entry in $\mathbf{x}$. Let $X=N_{G}(u)$ and
$Y=V(G)\setminus N_{G}[u]$. As $G$ does not contain a DCC, a component of
$G[X]$ is an isolated vertex $K_{1}$, an isolated edge $K_{2}$, or a star
$K_{1,r}$ for some $r\geqslant 2$. Let $X_{0}$ be the set of isolated vertices
in $G[X]$ and $X_{1}$ be the set of vertices of isolated edges in $G[X]$. Let
$X_{2}=X\setminus(X_{0}\cup X_{1})$. Let $X_{2}^{\prime}$ be the set of
vertices of degree at least two in $G[X]$ (i.e., the centers of the stars in
$G[X]$). Note that $\rho x_{u}=\sum_{v\in X}x_{v}$. From (2.1), we have

$\displaystyle(\rho^{2}-\rho)x_{u}$ $\displaystyle=d_{u}x_{u}+\sum_{v\in
X}(d_{X}(v)-1)x_{v}+\sum_{v\in Y}d_{X}(v)x_{v}$
$\displaystyle\leqslant\left(d_{u}+\sum_{v\in
X_{2}^{\prime}}(d_{X}(v)-1)+\sum_{v\in Y}d_{X}(v)-\sum_{v\in
X_{0}}\frac{x_{v}}{x_{u}}\right)x_{u}$
$\displaystyle=\left(|X|+|X_{2}|-2|X_{2}^{\prime}|+e(X,Y)-\sum_{v\in
X_{0}}\frac{x_{v}}{x_{u}}\right)x_{u},$

so

$\rho^{2}-\rho\leqslant|X|+|X_{2}|-2|X_{2}^{\prime}|+e(X,Y)-\sum_{v\in
X_{0}}\frac{x_{v}}{x_{u}}.$

As $K_{1,1,n-2}$ does not contain a DCC, we have by Lemma 2.6 that
$\rho\geqslant\rho(K_{1,1,n-2})=\tfrac{1}{2}+\sqrt{2n-\tfrac{15}{4}}$, so
$\rho^{2}-\rho\geqslant 2n-4$. Therefore, we have

$2n-4\leqslant|X|+|X_{2}|-2|X_{2}^{\prime}|+e(X,Y)-\sum_{v\in
X_{0}}\frac{x_{v}}{x_{u}}.$ (3.1)

######  Claim 3.1.

There is no cut vertex in $V(G)\setminus\\{u\\}$.

###### Proof.

Suppose to the contrary that there is a cut vertex $v\in
V(G)\setminus\\{u\\}$. Then $G-v$ has at least two components, one of which
does not contain $u$, which we denote by $H$. Let

$G^{\prime}=G-\\{vz:z\in N_{H}(v)\\}+\\{uz:z\in N_{H}(v)\\}.$

Then $u$ is a cut vertex of $G^{\prime}$ and $G^{\prime}[\\{u\\}\cup
V(H)]\cong G[\\{v\\}\cup V(H)]$, so $G^{\prime}$ does not contain a DCC.
However, we have by Lemma 2.2 that $\rho(G^{\prime})>\rho$, a contradiction. ∎

######  Claim 3.2.

For each $vv^{\prime}\in E(G[X_{1}])$, if $vw\in Y$ for some $w\in Y$, then
either $N_{X}(w)\setminus\\{v\\}\subseteq X_{0}$ or
$N_{X}(w)=\\{v,v^{\prime}\\}$.

###### Proof.

We first claim that $N_{X}(w)\setminus\\{v,v^{\prime}\\}\subseteq X_{0}$.
Otherwise, there is a vertex $v_{1}\in
X\setminus(X_{0}\cup\\{v,v^{\prime}\\})$ with $v_{1}w\in E(G)$. Then
$v_{1}\in(X_{1}\cup X_{2})\setminus\\{v,v^{\prime}\\}$. Denote by
$v_{1}^{\prime}$ one neighbor of $v_{1}$ in $X$. Then
$uv^{\prime}vwv_{1}v_{1}^{\prime}u$ is a cycle with chords $uv$ and $uv_{1}$,
a contradiction.

If $v_{0}w\in E(G)$ for some $v_{0}\in X_{0}$ and $v^{\prime}w\in E(G)$, then
$uvv^{\prime}wv_{0}u$ is a cycle with chords $uv^{\prime}$ and $vw$, a
contradiction. So $v^{\prime}w\notin E(G)$ or $v_{0}w\notin E(G)$. ∎

Let $Y_{1}$ be the set of those vertices in $Y$ with at least one neighbor in
$X_{1}$. By Claim 3.2, $d_{X_{1}}(w)=1,2$ for any $w\in Y_{1}$. Let
$Y_{1}^{i}=\\{w\in Y_{1}:d_{X_{1}}(w)=i\\}$ for $i=1,2$. Then
$Y_{1}=Y_{1}^{1}\cup Y_{1}^{2}$ and

$e(X_{1},Y)=|Y_{1}^{1}|+2|Y_{1}^{2}|\mbox{ and }e(X_{0},Y_{1}^{2})=0.$ (3.2)

######  Claim 3.3.

For each $v\in X_{2}\setminus X_{2}^{\prime}$, $N_{Y}(v)=\emptyset$.

###### Proof.

Suppose that $N_{Y}(v)=\emptyset$, say $w\in N_{Y}(v)$ for some $v\in
X_{2}\setminus X_{2}^{\prime}$. By Claim 3.1, there is a path $P$ between $w$
and $u$ which does not contain $v$. Let $v_{0}$ be the unique neighbor of $v$
in $X$ and $v^{\prime}$ be a neighbor of $v_{0}$ different from $v^{\prime}$
in $X$.

If $P$ does not contain $v_{0}$ or $v^{\prime}$, then $uv^{\prime}v_{0}vwPu$
is a cycle with chords $uv_{0}$ and $uv$, a contradiction. If $P$ contains
$v_{0}$ but not $v^{\prime}$ or $P$ contains both $v_{0}$ and $v^{\prime}$
with $d_{P}(w,v_{0})<d_{P}(w,v^{\prime})$, then
$uvwP[w,v_{0}]v_{0}v^{\prime}u$ is a cycle with chords $uv_{0}$ and $vv_{0}$,
a contradiction. Similarly, if $P$ contains $v^{\prime}$ but not $v_{0}$ or
$P$ contains both $v^{\prime}$ and $v_{0}$ with
$d_{P}(w,v^{\prime})<d_{P}(w,v_{0})$, then
$uvwP[w,v^{\prime}]v^{\prime}v_{0}u$ is a cycle with chords $uv^{\prime}$ and
$vv_{0}$, also a contradiction. ∎

######  Claim 3.4.

For each $v\in X_{2}^{\prime}$, if $vw\in E(G)$ for some $w\in Y$, then
$N_{X}(w)\setminus\\{v\\}\subseteq X_{0}$.

###### Proof.

Suppose that there exists a vertex $v_{0}\in X_{1}\cup X_{2}\setminus\\{v\\}$
such that $v_{0}w\in E(G)$. Let $v^{\prime}\in N_{X}(v)\setminus\\{v_{0}\\}$.
By Claim 3.3, $vv_{0}\notin E(G)$. Let $v_{0}^{\prime}$ be a neighbor of
$v_{0}$ in $X$. Then $uv^{\prime}vwv_{0}v_{0}^{\prime}u$ is a cycle with
chords $uv$ and $uv_{0}$, a contradiction. ∎

Let $Y_{2}$ be the set of those vertices in $Y$ with at least one neighbor in
$X_{2}$. Then by Claims 3.3 and 3.4,

$e(X_{2},Y)=e(X_{2}^{\prime},Y_{2})=|Y_{2}|.$ (3.3)

By Claims 3.2 and 3.4, we have $Y_{1}\cap Y_{2}=\emptyset$.

For $v\in X_{1}\cup X_{2}^{\prime}$, let

$X_{v}=\\{z\in X_{0}:N_{Y}(z)\cap N_{Y}(v)\neq\emptyset\\}.$

######  Claim 3.5.

For each $v_{0}\in X_{v}$ with $v\in X_{1}\cup X_{2}^{\prime}$ and $w\in
N_{Y}(v)\cap N_{Y}(v_{0})$, if $|N_{Y}(v_{0})|\geqslant 2$, then
$N_{X}(z)\subseteq\\{v,v_{0}\\}$ for each $z\in N_{Y}(v_{0})\setminus\\{w\\}$.
Moreover, if $|N_{Y}(v)|\geqslant 2$, then $|N_{Y}(v)\cap N_{Y}(v_{0})|=1$ or
$N_{X}(z)\subseteq\\{v,v_{0}\\}$ for each $z\in N_{Y}(v_{0})$.

###### Proof.

Suppose that $v_{1}\in N_{X}(z)\setminus\\{v,v_{0}\\}$. Denote by $v^{\prime}$
one neighbor of $v$ in $X$. Then $uv^{\prime}vwv_{0}zv_{1}u$ is a cycle with
chords $uv$ and $uv_{0}$, a contradiction. So
$N_{X}(z)\setminus\\{v,v_{0}\\}=\emptyset$. The second result follows
immediately. ∎

By Claim 3.5, we have $X_{v}\cap X_{v^{\prime}}=\emptyset$ for any pair
$\\{v,v^{\prime}\\}\subseteq X_{1}\cup X_{2}^{\prime}$. By Claims 3.2 and 3.4
again, $e(X_{v},Y_{1}\cup Y_{2})=e(X_{v},N_{Y}(v))$.

Let $v\in X_{1}\cup X_{2}^{\prime}$. Note that

$e(X_{v},Y_{1}\cup Y_{2})\leqslant|X_{v}|+|N_{Y}(v)|.$

If $|N_{Y}(v)|=1$, this is obvious as $e(X_{v},Y_{1}\cup Y_{2})=|X_{v}|$.
Suppose that $|N_{Y}(v)|\geqslant 2$. Let $X_{v}^{1}=\\{v_{0}\in
X_{v}:|N_{Y}(v)\cap N_{Y}(v_{0})|=1\\}$ and $X_{v}^{2}=X_{v}\setminus
X_{v}^{1}$. Then by Claim 3.5, $e(X_{v}^{1},Y_{1}\cup Y_{2})=|X_{v}^{1}|$ and
$N_{Y}(v_{0})\cap N_{Y}(v_{0}^{\prime})=\emptyset$ for any pair
$\\{v_{0},v_{0}^{\prime}\\}\subseteq X_{v}^{2}$. So $e(X_{v}^{2},Y_{1}\cup
Y_{2})=|\\{w\in N_{Y}(v):v_{0}w\in E(G),v_{0}\in
X_{v}^{2}\\}|\leqslant|N_{Y}(v)|$. Thus

$e(X_{v},Y_{1}\cup Y_{2})=e(X_{v}^{1},Y_{1}\cup Y_{2})+e(X_{v}^{2},Y_{1}\cup
Y_{2})\leqslant|X_{v}^{1}|+|N_{Y}(v)|\leqslant|X_{v}|+|N_{Y}(v)|,$

as desired.

Let $X_{0}^{\prime}=\cup_{v\in X_{1}\cup X_{2}^{\prime}}X_{v}$. Then

$e(X_{0}^{\prime},Y_{1}\cup Y_{2})=\sum_{v\in X_{1}\cup
X_{2}}e(X_{v},Y_{1}\cup Y_{2})\leqslant\sum_{v\in X_{1}\cup
X_{2}}\left(|X_{v}|+|N_{Y}(v)|\right)=|X_{0}^{\prime}|+|Y_{1}^{1}|+|Y_{2}|.$

Let

$Y_{v}=\\{z\in Y\setminus(Y_{1}\cup Y_{2}):N_{X_{v}}(z)\neq\emptyset\\}.$

By Claim 3.5, we have $e(X,Y_{v})=e(X_{v},Y_{v})=|Y_{v}|$ and $Y_{v}\cap
Y_{v^{\prime}}=\emptyset$ for any $v^{\prime}\in X_{1}\cup
X_{2}^{\prime}\setminus\\{v\\}$. Let $Y_{0}^{\prime}=\cup_{v\in X_{1}\cup
X_{2}^{\prime}}Y_{v}$. Then $e(X_{v},Y_{0}^{\prime})=e(X_{v},Y_{v})=|Y_{v}|$
and

$e(X_{0}^{\prime},Y_{0}^{\prime})=\sum_{v\in X_{1}\cup
X_{2}^{\prime}}e(X_{v},Y_{0}^{\prime})=\sum_{v\in X_{1}\cup
X_{2}^{\prime}}|Y_{v}|=|Y_{0}^{\prime}|.$

Note that
$e(X_{0}^{\prime},Y)=e(X_{0}^{\prime},Y_{0}^{\prime})+e(X_{0}^{\prime},Y_{1}\cup
Y_{2})$. So

$e(X_{0}^{\prime},Y)\leqslant|X_{0}^{\prime}|+|Y_{0}^{\prime}|+|Y_{1}^{1}|+|Y_{2}|.$
(3.4)

Let $X_{0}^{*}=X_{0}\setminus X_{0}^{\prime}$ and $Y_{0}=Y\setminus(Y_{1}\cup
Y_{2}\cup Y_{0}^{\prime})$. Then $e(X_{0}^{*},Y)=e(X_{0}^{*},Y_{0})$ and
$e(X_{0}^{\prime},Y_{0})=0$. It then follows from (3.2)–(3.4) that

$\displaystyle e(X,Y)$
$\displaystyle=e(X_{0}^{*},Y)+e(X_{0}^{\prime},Y)+e(X_{1},Y)+e(X_{2}^{\prime},Y)$
$\displaystyle\leqslant
e(X_{0}^{*},Y)+|X_{0}^{\prime}|+|Y_{0}^{\prime}|+|Y_{1}^{1}|+|Y_{2}|+|Y_{1}^{1}|+2|Y_{1}^{2}|+|Y_{2}|$
$\displaystyle=e(X_{0}^{*},Y_{0})+|X_{0}^{\prime}|+|Y_{0}^{\prime}|+2|Y_{1}|+2|Y_{2}|.$

Note that $n=1+|X|+|Y|$, $X=|X_{0}^{*}|+|X_{0}^{\prime}|+|X_{1}|+|X_{2}|$ and
$|Y|=|Y_{0}|+|Y_{0}^{\prime}|+|Y_{1}|+|Y_{2}|$. So, from (3.1), we have

$|X_{0}^{*}|+|X_{1}|+2|X_{2}^{\prime}|+2|Y_{0}|+|Y_{0}^{\prime}|-2\leqslant
e(X_{0}^{*},Y_{0})-\sum_{v\in X_{0}}\frac{x_{v}}{x_{u}}.$ (3.5)

Suppose that $X_{0}^{*}\neq\emptyset$. Then $\sum_{v\in
X_{0}}\frac{x_{v}}{x_{u}}>0$. From (3.5), we have

$e(X_{0}^{*},Y_{0})\geqslant|X_{0}^{*}|+2|Y_{0}|-1.$ (3.6)

Let $G_{1}=G[\\{u\\}\cup X_{0}^{*}\cup Y_{0}]$. As $G_{1}$ does not contain a
DCC, we have $e(G_{1})\leqslant 2|X_{0}^{*}|+2|Y_{0}|-1$ by Lemma 3.1. So,
from (3.6), we have

$2|X_{0}^{*}|+2|Y_{0}|-1\leqslant
e(G_{1})=|X_{0}^{*}|+e(X_{0}^{*},Y_{0})+e(Y_{0})\geqslant
2|X_{0}^{*}|+2|Y_{0}|-1+e(Y_{0}),$

implying that $e(Y_{0})=0$. Thus (3.6) is an equality, so from (3.5) again, we
have $X_{1}=X_{2}^{\prime}=\emptyset$, so $G=G_{1}$. As $G$ is bipartite, we
have $\rho(G)\leqslant\sqrt{e(G)}=\sqrt{2n-3}$, so
$\tfrac{1}{2}+\sqrt{2n-\tfrac{15}{4}}\leqslant\sqrt{2n-3}$, a contradiction.
This shows that $X_{0}^{*}=\emptyset$. So (3.5) becomes

$|X_{1}|+2|X_{2}^{\prime}|+2|Y_{0}|+|Y_{0}^{\prime}|\leqslant 2-\sum_{v\in
X_{0}}\frac{x_{v}}{x_{u}}.$ (3.7)

If $X_{1}\cup X_{2}^{\prime}=\emptyset$, then $X_{0}^{\prime}=\emptyset$, so
$X_{0}=\emptyset$, which shows that $G$ is trivial or disconnected, a
contradiction. So $X_{1}\cup X_{2}^{\prime}\neq\emptyset$. From (3.7) we have
$(|X_{1}|,|X_{2}^{\prime}|,|Y_{0}|,|Y_{0}^{\prime}|)=(2,0,0,0)$, $(0,1,0,0)$
and $X_{0}=\emptyset$.

If $(|X_{1}|,|X_{2}^{\prime}|,|Y_{0}|,|Y_{0}^{\prime}|)=(0,1,0,0)$, then by
Claims 3.1 and 3.3, $Y_{2}=\emptyset$. So $G\cong K_{1,1,n-2}$, as desired.

If $(|X_{1}|,|X_{2}^{\prime}|,|Y_{0}|,|Y_{0}^{\prime}|)=(2,0,0,0)$, then we
have from (3.1) and (3.2) that $Y_{1}^{1}=\emptyset$ and $V(G)=\\{u\\}\cup
X_{1}\cup Y_{1}^{2}$. We claim that $Y_{1}^{2}$ is independent, as otherwise,
there is an edge $w_{1}w_{2}$ with $w_{1},w_{2}\in Y$, which leads to a cycle
$uv_{1}w_{1}w_{2}v_{2}u$ with chords $v_{1}v_{2}$ and $v_{1}w_{2}$, where
$v_{1},v_{2}\in X_{1}$, a contradiction. Therefore, $G\cong K_{1,1,n-2}$.

Combining the above cases, we conclude that $G\cong K_{1,1,n-2}$. This
completes the proof. ∎

##  4 Proof of Theorem 1.2

Let $G$ be an $n$-vertex graph that does not contain a DCC1. From a result in
[17], we have $e(G)\leqslant 3n-9$ for $n\geqslant 9$. Note that $F_{1}$ is a
graph on five vertices with no DCC1s, and $e(F_{1})=7>6=3n-9$. In the
following lemma, we show that $e(G)\leqslant 3n-9$ for $n\geqslant 6$. As in
[17], we need a result due to Bondy [2] (see also [1, Theorem 4.11]): Let $C$
be a longest cycle (with length $c$) in an $n$-vertex graph $G$, then there
are at most $\lfloor\tfrac{1}{2}c(n-c)\rfloor$ edges with at most one end
vertex on $C$. We also need a result of Czipszer [11] (see also [1, p. 386])
stating that if $\delta(G)\geqslant 4$ then $G$ contains a DCC1.

######  Lemma 4.1.

Let $n\geqslant 6$. If $G$ is an $n$-vertex graph that does not contain a
DCC1, then $e(G)\leqslant 3n-9$ with equality when $G$ is bipartite if and
only if $G\cong K_{3,n-3}$.

###### Proof.

We prove the result by induction on $n$.

Suppose that $n=6$. Let $C$ be a longest cycle of $G$ and $c$ the length of
$C$. By Bondy’s result,
$e(G-E(G[V(C)]))\leqslant\lfloor\tfrac{1}{2}c(6-c)\rfloor$. As $G$ does not
contain a DCC1, each vertex in $G[V(C)]$ has degree at most three. Then
$e(G[V(C)])\leqslant\lfloor\frac{3}{2}c\rfloor$. Then
$e(G)=e(G-E(G[V(C)])))+e(G[V(C)])\leqslant\lfloor\tfrac{1}{2}c(6-c)\rfloor+\lfloor\tfrac{3}{2}c\rfloor$.
So, if $c=3,5,6$, then $e(G)\leqslant 9$. Suppose that $c=4$. If $G[V(C)]\cong
K_{4}$, then each vertex outside $C$ is adjacent to at most one vertex on $C$,
and it is possible that the two vertices outside $C$ are adjacent to a vertex
on $C$, so they may be adjacent, implying that $e(G)\leqslant 6+3=9$. If
$G[V(C)]\ncong K_{4}$, then $e(G[V(C)])\leqslant 5$, so
$e(G)\leqslant\lfloor\tfrac{1}{2}c(6-c)\rfloor+5=9$. This shows that
$e(G)\leqslant 3n-9$ for $n=6$.

Moreover, suppose that $G$ is a bipartite graph with $e(G)=3n-9=9$. Then
$c=4,6$. If $c=4$, then $e(G)\leqslant\lfloor\tfrac{1}{2}c(6-c)\rfloor+4=8<9$.
If $c=6$, then $e(G)=\lfloor\frac{3}{2}c\rfloor=9$ if and only if $G$ is
regular of degree three, equivalently, $G\cong K_{3,3}$.

Suppose that $n\geqslant 7$. Let $v$ be a vertex of minimum degree in $G$. By
induction assumption, $e(G-v)\leqslant 3(n-1)-9$. By Czipser’s result,
$\delta(G)\leqslant 3$. So $e(G)=e(G-v)+\delta(G)\leqslant 3(n-1)-9+3=3n-9$.

Next, suppose that $G$ is a bipartite graph with $e(G)=3n-9$. By the above
argument, $d_{G}(v)=3$ and $e(G-v)=3(n-1)-9$. By induction assumption,
$G-v\cong K_{3,n-4}$. If $n=7$, then as $G$ is bipartite, we have $G\cong
K_{3,4}$. Suppose that $n\geqslant 8$. Let $(V_{1},V_{2})$ be the bipartition
of $G-v$ with $|V_{1}|=3$ and $|V_{2}|=n-4$. Suppose that $G\not\cong
K_{3,n}$. As $G$ is bipartite, $G$ does not contain a triangle, so
$N_{G}(v)\subset V_{2}$. Let $V_{1}=\\{u_{1},u_{2},u_{3}\\}$ and
$N_{G}(v)=\\{v_{1},v_{2},v_{3}\\}\subset\\{v_{1},\dots,v_{4}\\}\subseteq
V_{2}$. Then $vv_{1}u_{1}v_{4}u_{3}v_{3}u_{2}v_{1}v$ is a cycle with chords
$v_{1}u_{2}$ and $v_{1}u_{3}$, a contradiction. ∎

For positive integers $n$ and $r$ with $n\geqslant 3r+4$ and $r\geqslant 1$,
let $u$ be the vertex of degree $3r$ in $K_{1}\vee rK_{3}$ (any vertex if
$r=1$), and $vw$ an edge of $K_{3,n-3r-3}$, where the degree of $v$ is
$n-3r-3$ and the degree of $w$ is three, and let $H_{n,r}=(K_{1}\vee
rK_{3})uvK_{3,n-3r-3}$ and $H_{n,r}^{\prime}=(K_{1}\vee
rK_{3})uwK_{3,n-3r-3}$.

######  Lemma 4.2.

For $n\geqslant 3r+6$ and $r\geqslant 1$,
$\rho(H_{n,r})\geqslant\rho(H_{n,r}^{\prime})$ with equality if and only if
$n=3r+6$.

###### Proof.

If $n=3r+6$, then $H_{n,r}\cong H_{n,r}^{\prime}$. Suppose that $n\geqslant
3r+7$. Then $n-3r-3>3$, so
$\rho(K_{3,n-3r-3}-v)=\rho(K_{2,n-3r-3})=\sqrt{2(n-3r-3)}<\sqrt{3(n-3r-4)}=\rho(K_{3,n-3r-4})=\rho(K_{3,n-3r-3}-w)$.
Thus the result follows by Lemma 2.4. ∎

######  Lemma 4.3.

For positive integers $n\geqslant 3r+4$, $\rho(K_{3,n-3})>\rho(H_{n,r})$.

###### Proof.

Let $U_{1}=V(rK_{3})$, $V_{1}$ be the set of vertices of degree three in
$K_{3,n-3r-3}$ and $V_{2}=V(G)\setminus(U_{1}\cup V_{1}\cup\\{u\\})$. With
respect to the vertex partition $V(H_{n,r})=\\{u\\}\cup U_{1}\cup V_{1}\cup
V_{2}$, $A(H_{n,r})$ has an equitable quotient matrix

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

By Lemma 2.3, $\rho(H_{n,r})$ is the largest root of $f(x)=0$, where

$f(x)=\det(xI_{4}-B)=x^{4}-2x^{3}+(6r-3n+9)x^{2}+(6n-18r-18)x+6nr-18r-18r^{2}.$

It is evident that $f^{\prime\prime}(x)\geqslant
f^{\prime\prime}(\sqrt{3n-9})>0$ if $x\geqslant\sqrt{3n-9}$, so it may be
checked that $f^{\prime}(x)\geqslant f^{\prime}(\sqrt{3n-9})>0$ if
$x\geqslant\sqrt{3n-9}$. As $n\geqslant 3r+4$, we have
$4n-12-3r>3\sqrt{3n-9}$, so

$f(\sqrt{3(n-3)})=24rn-72r-18r^{2}-18r\sqrt{3n-9}=6r(4n-12-3r-3\sqrt{3n-9})>0,$

which shows that $\rho(H_{n,r})<\rho(K_{3,n-3})$. ∎

The following result follows from Lemmas 4.2 and 4.3.

######  Corollary 4.1.

For $n\geqslant 3r+6$ and $r\geqslant 1$,
$\rho(K_{3,n-3})>\rho(H_{n,r}^{\prime})$.

######  Lemma 4.4.

The following results hold.
(i) For integer $n\geqslant 7$ with $n\equiv 1\pmod{3}$,
$\rho(K_{1}\vee\tfrac{n-1}{3}K_{3})<\sqrt{3(n-3)}$;
(ii) For integer $n\geqslant 6$ with $n\equiv 0\pmod{3}$,

$\rho(K_{1}\vee(K_{2}\cup\tfrac{n-3}{3}K_{3}))<\begin{cases}\sqrt{3(n-3)}&\mbox{if
$n\geqslant 9$},\\\ \frac{1}{2}+\sqrt{2n-\frac{15}{4}}&\mbox{if
$n=6$};\end{cases}$

(iii) For integers $n\geqslant 8$ with $n\equiv 2\pmod{3}$,
$\rho(K_{1}\vee(K_{1}\cup\tfrac{n-2}{3}K_{3}))<\sqrt{3(n-3)}$ .

###### Proof.

From [3, p. 19, Ex. 1.12], we know that
$\rho(K_{1}\vee\tfrac{n-1}{3}K_{3})=1+\sqrt{n}$, so (i) follows.

Let $H=K_{1}\vee(K_{2}\cup\tfrac{n-3}{3}K_{3})$. Let $u$ be the vertex of
degree $n-1$ in $H$, $V_{1}$ be the set of vertices of degree two and
$V_{2}=V(H)\setminus(V_{1}\cup\\{u\\})$. With respect to the vertex partition
$V(H)=\\{u\\}\cup V_{1}\cup V_{2}$, $A(H)$ has an equitable quotient matrix

$B^{\prime}=\begin{pmatrix}0&2&n-3\\\ 1&1&0\\\ 1&0&2\end{pmatrix}.$

By Lemma 2.3, $\rho(H)$ is equal to the largest root of $g(x)=0$, where

$g(x)=\det(xI_{3}-B^{\prime})=x^{3}-3x^{2}-(n-3)x+n+1.$

As $g(x)$ is increasing in $[\sqrt{3n-9},\infty)$ and
$g(\sqrt{3(n-3)})=2(n-3)\sqrt{3n-9}-2(4n-13)>0$ if $n\geqslant 9$, we have
$\rho(H)<\sqrt{3(n-3)}$ if $n\geqslant 9$. The result for $n=6$ follows by an
easy calculation. This proves (ii).

Let $G=K_{1}\vee(K_{1}\cup\tfrac{n-2}{3}K_{3})$. Let $u$ be the vertex of
degree $n-1$ and $v$ be the pendant vertex in $G$. Let
$U_{1}=V(G)\setminus\\{u,v\\}$. With vertex partition
$V(G)=\\{u\\}\cup\\{v\\}\cup V_{1}$, $A(G)$ has an equitable quotient matrix

$B=\begin{pmatrix}0&1&n-2\\\ 1&0&0\\\ 1&0&2\end{pmatrix}.$

By Lemma 2.3, $\rho(G)$ is equal to the largest root of $f(x)=0$, where

$f(x)=\det(xI_{3}-B)=x^{3}-2x^{2}-(n-1)x+2.$

As $f(x)$ is increasing in $[\sqrt{3n-9},\infty]$ and
$f(\sqrt{3n-9})=(2n-8)\sqrt{3n-9}-2(3n-10)>0$. This proves (iii). ∎

######  Lemma 4.5.

For $n\geqslant 5+t$ and $t\geqslant 2$ with $n-t\equiv 2\pmod{3}$,
$\rho(K_{1}\vee(K_{1,t}\cup\tfrac{n-t-2}{3}K_{3}))<\rho(K_{1,1,n-2})$.

###### Proof.

Let $G=K_{1}\vee(K_{1,t}\cup\tfrac{n-t-2}{3}K_{3})$, $\rho=\rho(G)$ and
$\mathbf{x}$ be the Perron vector of $G$. Let $u$ and $v$ be the vertices of
degree $n-1$ and $t+1$ in $G$, respectively. Let $V_{1}$ be the set of
vertices of degree four in $G$ and $V_{2}$ be the set of remaining vertices.
By $A(G)\mathbf{x}=\rho\mathbf{x}$, for $i=1,2$, each vertex in $V_{i}$ has
the same entry, denoted by $x_{i}$. By $A(G)\mathbf{x}=\rho\mathbf{x}$ at $v$,
$w\in V_{1}$ and $z\in V_{2}$, we have

$x_{1}=\frac{1}{\rho-2}x_{u}\mbox{ and }x_{v}=\frac{\rho+t}{\rho^{2}-t}x_{u}.$

As $\tfrac{1}{\rho-2}<\tfrac{\rho+t}{\rho^{2}-t}$, $x_{1}<x_{v}$. Let

$G^{\prime}=G-\\{wz\in E(G):w,z\in V_{1}\\}+\\{vw:w\in V_{1}\\}.$

Then $G^{\prime}\cong K_{1,1,n-2}$. By Rayleigh’s principle,

$\rho(G^{\prime})\geqslant\mathbf{x}^{\top}A(G^{\prime})\mathbf{x}=\mathbf{x}^{\top}A(G)\mathbf{x}-2\sum_{wz\in
E(G[V_{1}])}x_{w}x_{z}+2\sum_{w\in V_{1}}x_{v}x_{w}>\rho,$

as desired. ∎

###### Proof of Theorem 1.2.

It is trivial for $n=3,4$. Suppose in the following that $n\geqslant 5$.
Suppose that $G$ is a graph that maximizes the spectral radius among all
graphs of order $n$ containing no DCC1s. Similarly as in the proof of Theorem
1.1, $G$ is connected. Let $\rho=\rho(G)$ and let $\mathbf{x}$ be the Perron
vector of $G$ and $u$ a vertex with maximum entry in $\mathbf{x}$. Let
$X=N_{G}(u)$ and $Y=V(G)\setminus N_{G}[u]$. From (2.1), we have

$\rho^{2}x_{u}=d_{u}x_{u}+\sum_{v\in X}d_{X}(v)x_{v}+\sum_{v\in
Y}d_{X}(v)x_{v}\leqslant\left(|X|+2e(X)+e(X,Y)\right)x_{u},$

so

$\rho^{2}\leqslant|X|+2e(X)+e(X,Y).$

As $K_{3,n-3}$ has no DCC1s, we have
$\rho\geqslant\rho(K_{3,n-3})=\sqrt{3(n-3)}$, so we have

$3(n-3)\leqslant|X|+2e(X)+e(X,Y).$ (4.1)

By the same argument as in the proof of Claim 3.1, we have

######  Claim 4.1.

There is no cut vertex in $V(G)\setminus\\{u\\}$.

As $G$ does not contain a DCC1, $G[X]$ is $P_{4}$-free, any component $G[X]$
is an isolated vertex $K_{1}$, an isolated edge $K_{2}$, a star $K_{1,r}$ for
some $r\geqslant 2$, or a triangle $K_{3}$. Let $X_{0}$ be the set of isolated
vertices in $G[X]$, $X_{1}$ the set of vertices of isolated edges in $G[X]$,
$X_{2}$ the set of vertices of stars in $G[X]$, and $X_{3}$ the set of
vertices of triangles in $G[X]$. Then $X=X_{0}\cup X_{1}\cup X_{2}\cup X_{3}$.

######  Claim 4.2.

For each $v\in X_{3}$, $N_{Y}(v)=\emptyset$.

###### Proof.

Suppose that $N_{Y}(v)\neq\emptyset$ for some $v\in X_{3}$. Assume that $w\in
N_{Y}(v)$. By Claim 4.1, $v$ is not a cut vertex of $G$, so there is a path
$P$ connecting $w$ and $u$ which does not contain $v$. Denote by $v^{\prime}$
the vertex on $P$ adjacent to $u$. Let $v_{1}$ and $v_{2}$ be two other
vertices of the triangle of $G[X]$ containing $v$. If both $v_{1}$ and $v_{2}$
lie outside $P$, then $uv_{1}v_{2}vwPu$ is a cycle with chords $uv$ and
$uv_{2}$, a contradiction. If one of $v_{1}$ or $v_{2}$, say $v_{1}$, lies on
$P$, where we assume that $d_{P}(v_{1},w)<d_{P}(v_{2},w)$ if both $v_{1}$ and
$v_{2}$ lie one $P$, then $uv_{2}vwP[w,v_{1}]v_{1}u$ is a cycle with chords
$vu$ and $vv_{1}$, also a contradiction. ∎

Let $X_{2}^{\prime}$ be the set of the centers of the stars in $G[X_{2}]$. Let
$X_{2}^{*}$ be the set of pendant vertices of the components $K_{1,2}$ of
$G[X_{2}]$

######  Claim 4.3.

For each $v\in X_{2}^{*}$, if $vw\in Y$ for some $w\in Y$, then
$N_{X}(w)\subseteq\\{v,v^{\prime}\\}$, where $v^{\prime}$ is the other vertex
in the component $K_{1,2}$ of $G[X_{2}]$ containing $v$.

###### Proof.

Suppose that $wv_{1}\in E(G)$ for some $v_{1}\in
X\setminus\\{v,v^{\prime}\\}$. If $vv_{1}\in E(G)$, then $v^{\prime}v_{1}\in
E(G)$, so $uv^{\prime}v_{1}wvu$ is a cycle with chords $uv_{1}$ and $vv_{1}$,
a contradiction. So $vv_{1}\notin E(G)$. Let $v_{0}$ be the unique neighbor of
$v$ in $G[X]$. Then $uv^{\prime}v_{0}vwv_{1}u$ is a cycle with chords $uv_{0}$
and $uv$, also a contradiction. ∎

######  Claim 4.4.

For each $v\in X_{2}\setminus(X_{2}^{\prime}\cup X_{2}^{*})$,
$N_{Y}(v)=\emptyset$.

###### Proof.

Suppose that $N_{Y}(v)\neq\emptyset$ for some $v\in
X_{2}\setminus(X_{2}^{\prime}\cup X_{2}^{*})$. Assume that $w\in N_{Y}(v)$. By
Claim 4.1, $v$ is not a cut vertex of $G$, so there is a path $P$ from $w$ to
$u$ which does not contain $v$. Let $v_{0}$ be the neighbor of $v$ in $X$ and
$v_{1},\dots,v_{t}$ all the neighbors of $v_{0}$ in $X$ with $v=v_{t}$. If all
$v_{0},v_{1},\dots,v_{t-1}$ lie outside $P$, then $uv_{1}v_{0}vwPu$ is a cycle
with chords $uv_{0}$ and $uv_{2}$, a contradiction. In the following, if one
of $v_{1},\dots,v_{t-1}$ lies one $P$, then we assume that $v_{1}$ lies on
$P$. If $v_{0}$ lies on $P$ and $v_{1}$ lies outside $P$, or both $v_{0}$ and
$v_{1}$ lie on $P$ with $d_{P}(w,v_{0})<d_{P}(w,v_{1})$, then
$uvwP[w,v_{0}]v_{0}v_{1}u$ is a cycle with chords $uv_{0}$ and $vv_{0}$, a
contradiction. If both $v_{0}$ and one of If $v_{1}$ lies on $P$ and $v_{0}$
lies outside $P$, or both $v_{1}$ and $v_{0}$ lie on $P$ with
$d_{P}(w,v_{1})<d_{P}(w,v_{0})$, then $uv_{2}v_{0}vwP[w,v_{1}]v_{1}u$ is a
cycle with chords is a cycle with chords $v_{0}u$ and $v_{0}v_{1}$, also a
contradiction. ∎

By Claim 4.3, for any $v\in X_{2}^{*}$ and any $w\in Y$, if $vw\in E(G)$, then
$d_{X}(w)\leqslant 2$. Let $Y_{2}$ be the set of those vertices in $Y$ with at
least one neighbor in $X_{2}^{*}$. Then $e(X_{2}^{*},Y_{2})\leqslant
2|Y_{2}|$. By Claim 4.4, $e(X_{2}\setminus(X_{2}^{\prime}\cup
X_{2}^{*}),Y)=0$, so

$e(X_{2}\setminus X_{2}^{\prime},Y)=e(X_{2}^{*},Y_{2})\leqslant 2|Y_{2}|.$
(4.2)

By a similar argument as in the proof of Claim 3.4, we have

######  Claim 4.5.

For each $v\in X_{2}^{\prime}$, if $vw\in Y$ for some $w\in Y$, then
$N_{X}(w)\setminus\\{v\\}\subseteq X_{0}$.

Denote by $Y_{2}^{\prime}\subseteq Y$ the set of vertices with at least one
neighbor in $X_{2}^{\prime}$. Then by Claim 4.5,

$e(X_{2}^{\prime},Y)=e(X_{2}^{\prime},Y_{2}^{\prime})=|Y_{2}^{\prime}|.$ (4.3)

######  Claim 4.6.

For each $vv^{\prime}\in E(G[X_{1}])$, if $vw\in Y$ for some $w\in Y$, then
$N_{X}(w)\setminus\\{v,v^{\prime}\\}\subseteq X_{0}$.

###### Proof.

Suppose that $wv_{1}\in E(G)$ for some $v_{1}\in
X\setminus(X_{0}\cup\\{v,v^{\prime}\\})$. Denote by $v_{1}^{\prime}$ a
neighbor of $v_{1}$ in $X$. Then $uv^{\prime}vwv_{1}v_{1}^{\prime}u$ is a
cycle with chords $uv$ and $uv_{1}$, a contradiction. ∎

Let $Y_{1}\subseteq Y$ be the set of those vertices with at least one
neighbors in $X_{1}$. By Claims 4.3, 4.5 and 4.6, $S\cap T=\emptyset$ for each
pair of $\\{S,T\\}\subset\\{Y_{1},Y_{2},Y_{2}^{\prime}\\}$.

For $v\in X_{1}\cup X_{2}^{\prime}$, let $X_{v}=\\{z\in X_{0}:N_{Y}(z)\cap
N_{Y}(v)\neq\emptyset\\}$.

By the same argument as in the proof of Claim 3.5, we have

######  Claim 4.7.

For each $v_{0}\in X_{v}$, if $|N_{Y}(v_{0})|\geqslant 2$, then
$N_{X}(z)\subseteq\\{v,v_{0}\\}$ for each $z\in N_{Y}(v_{0})\setminus\\{w\\}$,
where $w$ is a common neighbor of $v$ and $v_{0}$. Moreover, if
$|N_{Y}(v)|\geqslant 2$, then $|N_{Y}(v)\cap N_{Y}(v_{0})|=1$ or
$N_{X}(z)\subseteq\\{v,v_{0}\\}$ for each $z\in N_{Y}(v_{0})$.

By Claim 4.7, $X_{v}\cap X_{v^{\prime}}=\emptyset$ for any pair
$\\{v,v^{\prime}\\}\subseteq X_{1}\cup X_{2}^{\prime}$ with
$vv^{\prime}\not\in E(G)$ if $v,v^{\prime}\in X_{1}$. Then for each $v\in
X_{2}^{\prime}$, by Claim 4.5, $e(X_{v},Y_{1}\cup
Y_{2}^{\prime})=e(X_{v},N_{Y}(v))$ and so by the same argument as in the
previous section,

$e(X_{v},Y_{1}\cup Y_{2}^{\prime})\leqslant|X_{v}|+|N_{Y}(v)|.$ (4.4)

######  Claim 4.8.

If $vv^{\prime}\in E(X_{1})$, then $X_{v}\subseteq X_{v^{\prime}}$ or
$X_{v^{\prime}}\subseteq X_{v}$.

###### Proof.

Suppose to the contrary that $v_{0}\in X_{v}\setminus X_{v}^{\prime}$ and
$v_{1}\in X_{v}^{\prime}\setminus X_{v}$. By the definition of $X_{v}$, there
exist vertices $w$ and $w^{\prime}$ such that
$vw,v_{0}w,v^{\prime}w^{\prime},v_{1}w^{\prime}\in E(G)$. Then
$uv_{0}wvv^{\prime}w^{\prime}v_{1}u$ is a cycle with chords $uv$ and
$uv^{\prime}$, a contradiction. So $X_{v}\setminus X_{v}^{\prime}=\emptyset$
or $X_{v}^{\prime}\setminus X_{v}=\emptyset$. ∎

For an edge $vv^{\prime}\in G[X_{1}]$, assume that $X_{v^{\prime}}\subseteq
X_{v}$ by Claim 4.8. For $vv^{\prime}\in E(X_{1})$, let
$Y_{vv^{\prime}}=\\{w\in Y_{1}:vw,v^{\prime}w\in E(G)\\}$.

######  Claim 4.9.

For $vv^{\prime}\in G[X_{1}]$, $e(\\{v,v^{\prime}\\}\cup X_{v}\cup
X_{v^{\prime}},Y_{1})\leqslant 2|N_{Y}(v)\cup N_{Y}(v^{\prime})|+|X_{v}|$.

###### Proof.

If $X_{v}=\emptyset$, then the result follows by Claim 4.6. Suppose next that
$X_{v}\neq\emptyset$, say $v_{0}\in X_{v}$. Let $w\in N_{Y}(v_{0})$. Assume
that $vw\in E(G)$.

We first claim that $Y_{vv^{\prime}}\setminus\\{w\\}=\emptyset$. Otherwise,
there is some vertex $z\in Y_{vv^{\prime}}$ with $z\neq w$. Then
$uv_{0}wvzv^{\prime}u$ is a cycle with chords $uv$ and $vv^{\prime}$, a
contradiction. So either $Y_{vv^{\prime}}^{\prime}=\\{w\\}$ or
$Y_{vv^{\prime}}=\emptyset$.

If $Y_{vv^{\prime}}=\\{w\\}$, then $e(\\{v,v^{\prime}\\},Y_{1})=|N_{Y}(v)\cup
N_{Y}(v^{\prime})|+1\leqslant 2|N_{Y}(v)\cup N_{Y}(v^{\prime})|$ and for each
$z\in X_{v}$, $z$ is adjacent to exactly one vertex $w$ in $Y$, so
$e(X_{v},Y_{1})=|X_{v}|$. Therefore, $e(\\{v,v^{\prime}\\}\cup X_{v}\cup
X_{v^{\prime}},Y_{1})\leqslant 2|N_{Y}(v)\cup N_{Y}(v^{\prime})|+|X_{v}\cup
X_{v}^{\prime}|$.

If $Y_{vv^{\prime}}=\emptyset$, then
$e(\\{v,v^{\prime}\\},Y_{1})=|N_{Y}(v)\cup N_{Y}(v^{\prime})|$. By Eq. (4.4),
$e(X_{v},Y_{1})\leqslant|X_{v}|+|N_{Y}\cup N_{Y}(v^{\prime})|$. Therefore,
$e(\\{v,v^{\prime}\\}\cup X_{v}\cup X_{v^{\prime}},Y_{1})\leqslant
2|N_{Y}(v)\cup N_{Y}(v^{\prime})|+|X_{v}\cup X_{v}^{\prime}|$. ∎

Let $X_{0}^{\prime}\subseteq X_{0}$ be the set of those vertices with at least
one neighbor in $Y_{1}\cup Y_{2}^{\prime}$. Then $X_{0}^{\prime}=\cup_{v\in
X_{1}\cup X_{2}^{\prime}}X_{v}$. For $v\in X_{1}\cup X_{2}^{\prime}$, let
$Y_{v}\subseteq Y\setminus(Y_{1}\cup Y_{2}\cup Y_{2}^{\prime})$ be the set of
those vertices with at least one neighbor in $X_{v}$. Let
$Y_{0}^{\prime}=\cup_{v\in X_{1}\cup X_{2}^{\prime}}Y_{v}$. By Claim 4.7,
$e(X_{v},Y_{v})=|Y_{v}|$ and $e(X_{v},Y_{0}^{\prime})=e(X_{v},Y_{v})=|Y_{v}|$.
By (4.3) and (4.4) and Claim 4.9,

$\displaystyle\quad e(X_{0}^{\prime}\cup X_{1}\cup X_{2}^{\prime},Y)$
$\displaystyle=\sum_{vv^{\prime}\in E(X_{1})}\left(e(\\{v,v^{\prime}\\}\cup
X_{v}\cup X_{v^{\prime}},Y_{1})+e(X_{v}\cup
X_{v^{\prime}},Y_{0}^{\prime})\right)+\sum_{v\in
X_{2}^{\prime}}\left(e(v,Y)+e(X_{v},Y)\right)$
$\displaystyle\leqslant\sum_{vv^{\prime}\in E(X_{1})}(2|N_{Y}(v)\cup
N_{Y}(v^{\prime})|+|X_{v}|+|Y_{v}|)+|Y_{2}^{\prime}|+\sum_{v\in
X_{2}^{\prime}}(|X_{v}|+|N_{Y}(v)|+|Y_{v}|)$
$\displaystyle=2|Y_{1}|+\sum_{vv^{\prime}\in
E(X_{1})}(|X_{v}|+|Y_{v}|)+2|Y_{2}^{\prime}|+\sum_{v\in
X_{2}^{\prime}}(|X_{v}|+|Y_{v}|),$

i.e.,

$e(X_{0}^{\prime}\cup X_{1}\cup
X_{2}^{\prime},Y)\leqslant|X_{0}^{\prime}|+|Y_{0}^{\prime}|+2|Y_{1}|+2|Y_{2}^{\prime}|.$
(4.5)

Let $X_{0}^{*}=X_{0}\setminus X_{0}^{\prime}$ and $Y_{0}=Y\setminus(Y_{1}\cup
Y_{2}^{\prime}\cup Y_{2}\cup Y_{0}^{\prime})$. Then
$e(X_{0}^{*},Y)=e(X_{0}^{*},Y_{0})$. By (4.2) and (4.5),

$\displaystyle e(X,Y)$ $\displaystyle=e(X_{0}^{*},Y)+e(X_{0}^{\prime}\cup
X_{1}\cup X_{2}^{\prime},Y)+e(X_{2}\setminus X_{2}^{\prime},Y)$
$\displaystyle\leqslant
e(X_{0}^{*},Y_{0})+|X_{0}^{\prime}|+|Y_{0}^{\prime}|+2|Y_{1}|+2|Y_{2}^{\prime}|+2|Y_{2}|.$

Note that

$e(X)=\frac{1}{2}|X_{1}|+|X_{2}|-|X_{2}^{\prime}|+|X_{3}|$

and

$n=1+|X_{0}^{*}|+|X_{0}^{\prime}|+|X_{1}|+|X_{2}|+|X_{3}|+|Y_{0}|+|Y_{0}^{\prime}|+|Y_{1}|+|Y_{2}^{\prime}|+|Y_{2}|.$

From (4.1), we have

$e(X_{0}^{*},Y_{0})\geqslant
2|X_{0}^{*}|+|X_{0}^{\prime}|+|X_{1}|+2|X_{2}^{\prime}|+3|Y_{0}|+2|Y_{0}^{\prime}|+|Y_{1}|+|Y_{2}^{\prime}|+|Y_{2}|-6,$
(4.6)

so

$e(X_{0}^{*},Y_{0})\geqslant 2|X_{0}^{*}|+3|Y_{0}|-6.$ (4.7)

Case 1. $|X_{0}^{*}|+|Y_{0}|\geqslant 5$.

Let $G_{1}=G[\\{u\\}\cup X_{0}^{*}\cup Y_{0}]$. From (4.7), we have

$e(G_{1})\geqslant|X_{0}^{*}|+e(X_{0}^{*})+e(X_{0}^{*},Y_{0})+e(Y_{0})\geqslant
3|X_{0}^{*}|+3|Y_{0}|-6+e(Y_{0}).$

As $G_{1}$ does not contain a DCC1, we have $e(G_{1})\leqslant
3|X_{0}^{*}|+3|Y_{0}|-6$, so

$3|X_{0}^{*}|+3|Y_{0}|-6+e(Y_{0})\leqslant e(G_{1})\leqslant
3|X_{0}^{*}|+3|Y_{0}|-6,$

implying that $e(Y_{0})=0$ and $e(G_{1})=3|X_{0}^{*}|+3|Y_{0}|-6$.

As $e(Y_{0})=0$, $G_{1}$ is a bipartite graph with bipartition
$(X_{0}^{*},\\{u\\}\cup Y_{0})$. As $e(G_{1})=3|X_{0}^{*}|+3|Y_{0}|-6$, we
have by Lemma 4.1 that $G_{1}\cong K_{3,|X_{0}^{*}|+|Y_{0}|-2}$. So
$|X_{0}|=3$ or $|Y_{0}|=2$.

As $e(G_{1})=3|X_{0}^{*}|+3|Y_{0}|-6$, we know from the above argument that
(4.7) is an inequality. Then, from (4.6), we have
$X_{0}^{\prime}=X_{1}=X_{2}^{\prime}=Y_{0}^{\prime}=Y_{2}^{\prime}=Y_{2}=\emptyset$,
so $X=X_{0}^{*}\cup X_{3}$ and $Y=Y_{0}$.

Suppose $X_{3}\neq\emptyset$. Let $r$ be the number of triangles in $G[X]$.
Then $|X_{3}|=3r$. If $|Y_{0}|=2$, then $G\cong H_{n,r}$, and if $|X_{0}|=3$,
then $G\cong H_{n,r}^{\prime}$. By Lemma 4.3 and Corollary 4.1, we have
$\rho<\rho(K_{3,n-3})$, a contradiction. It follows that $X_{3}=\emptyset$, so
$n\geqslant 6$ and $G\cong K_{3,n-3}$.

Case 2. $|X_{0}^{*}|+|Y_{0}|\leqslant 4$ and $X_{0}^{*}\neq\emptyset$.

As $e(X_{0}^{*},Y_{0})\leqslant|X_{0}^{*}||Y_{0}|$, we have from (4.7) that
$(|X_{0}^{*}|-3)(|Y_{0}|-2)\geqslant 0$, so $|X_{0}^{*}|\leqslant 3$ and
$|Y_{0}|\leqslant 2$. If $|X_{0}^{*}|=1$ and $|Y_{0}|\geqslant 1$, then we
have from (4.6) that
$|X_{0}^{\prime}|+|X_{1}|+2|X_{2}|+2|Y_{0}^{\prime}|+|Y_{1}|+|Y_{2}|+|Y_{2}^{\prime}|\leqslant
4-2|Y_{0}|\leqslant 2$, so
$Y_{0}^{\prime}=Y_{1}=Y_{2}=Y_{2}^{\prime}=\emptyset$, implying $u$ and any
vertex in $Y_{0}$ belong to different components of $G-X_{0}^{*}$, that is,
the vertex of $X_{0}^{*}$ is a cut vertex, which contradicts Claim 4.1. So if
$|X_{0}^{*}|=1$, then $Y_{0}=\emptyset$ and there are three possibilities as
below:

  1. (a)

$|X_{0}^{*}|=2$ and $|Y_{0}|=2$;

  2. (b)

$|X_{0}^{*}|=2,3$ and $|Y_{0}|=1$;

  3. (c)

$|X_{0}^{*}|=1,2,3$ and $Y_{0}=\emptyset$.

Suppose first that (a) holds. From (4.7), we have $e(X_{0}^{*},Y_{0})=4$. Now,
from (4.6), we have
$X_{0}^{\prime}=X_{1}=X_{2}^{\prime}=Y_{0}^{\prime}=Y_{1}=Y_{2}=\emptyset$, so
$X=X_{0}^{*}$ and $Y=Y_{0}$. If $X_{3}\neq\emptyset$, then $G\cong
H_{n,\frac{|X_{3}|}{3}}$, so we have by Lemma 4.3 that $\rho<\rho(K_{3,n-3})$,
a contradiction. Therefore $X_{3}=\emptyset$, so $n=5$ and $G\cong K_{3,n-3}$.

Suppose next that (b) holds. From (4.6), we have
$|X_{0}^{\prime}|+|X_{1}|+2|X_{2}^{\prime}|+|Y_{1}|+|Y_{2}^{\prime}|+|Y_{2}|\leqslant
3-|X_{0}^{*}|\leqslant 1$, so $X_{1}=X_{2}^{\prime}=\emptyset$. It follows
that $Y=Y_{0}$, say $Y_{0}=\\{w\\}$, so $G^{\prime}:=G+uw$ does not contain a
DCC1. By Lemma 2.1, $\rho(G^{\prime})>\rho$, a contradiction.

Suppose finally that (c) holds. If $|X_{0}^{*}|\geqslant 2$, then as
$Y_{0}=\emptyset$, each vertex in $X_{0}^{*}$ is a pendant vertex of $G$, so
adding an edge between two vertices in $X_{0}^{*}$ leads to a graph that does
not contain a DCC1, which, by Lemma 2.1, is a contradiction. So
$|X_{0}^{*}|=1$.

######  Claim 4.10.

$X_{1}\cup X_{2}=\emptyset$.

###### Proof.

Suppose to the contrary that $X_{1}\cup X_{2}\neq\emptyset$.

If $Y=\emptyset$, then adding an edge between the vertex of $X_{0}^{*}$ and a
vertex in $X_{1}\cup X_{2}^{\prime}$ produces a graph that does not contain a
DCC1, which, by Lemma 2.1, is a contradiction. So $Y\neq\emptyset$. Moreover,
we have $Y_{2}^{\prime}=\emptyset$; otherwise we have by Claim 4.1 and (4.6)
that $|X_{0}^{\prime}|=|X_{2}^{\prime}|=|Y_{2}^{\prime}|=1$, $X=X_{0}^{*}\cup
X_{0}^{\prime}\cup X_{2}\cup X_{3}$ and $Y=Y_{2}^{\prime}$, so $e(X,Y)=2$,
which contradicts (4.1). This shows that $Y_{1}\cup Y_{2}\neq\emptyset$.

Suppose that $Y_{1}\neq\emptyset$. If $X_{0}^{\prime}=\emptyset$, then the
graph obtained from $G$ by adding an edge between the vertex of $X_{0}^{*}$
and a vertex in $Y_{1}$ does not contain a DCC1, which, by Lemma 2.1, is a
contradiction. So $X_{0}^{\prime}\neq\emptyset$. From (4.6), $|Y_{1}|=1$, so
the graph obtained from $G$ adding an edge between the vertex of $X_{0}^{*}$
and the vertex of $Y_{1}$ does not contain a DCC1, which, by Lemma 2.1, is a
contradiction.

Suppose that $Y_{2}\neq\emptyset$. Then $X_{2}^{\prime}\neq\emptyset$. We have
by Eq. (4.6) that $|X_{2}^{\prime}|=1$, $|Y_{2}|=1,2$ and
$e(X_{2},Y_{2})=2|Y_{2}|$. Let $F_{0}=G[\\{u\\}\cup X_{0}^{*}\cup X_{2}\cup
Y_{2}]$. Then $F_{0}$ is obtained from $K_{2,2+|Y_{2}|}$ with bipartition
$(X_{2}^{*},\\{u\\}\cup X_{2}^{\prime}\cup Y_{2})$ by adding an edge between
$u$ and the vertex of $X_{2}^{\prime}$ and a pendant vertex to $u$. If
$n=5+|Y_{2}|$, then $G=F_{0}$ and if $n>5+|Y_{2}|$, then $G$ consists of
$F_{0}$ and $G[V(G)\setminus V(F_{0})\cup\\{u\\}]$ with a common vertex $u$.
Let $F_{0}^{\prime}\cong K_{1,1,|Y_{2}|+3}$. By direct calculation, we have

$\rho(F_{0})=\begin{cases}2.9439&\mbox{ if }|Y_{2}|=1,\\\ 3.2054&\mbox{ if
}|Y_{2}|=2,\end{cases}\mbox{ and }\rho(F_{0}-u)=\begin{cases}2&\mbox{ if
}|Y_{2}|=1,\\\ 2.4495&\mbox{ if }|Y_{2}|=2,\end{cases}$

From Lemma 2.4,

$\rho(F_{0}^{\prime})=\begin{cases}3.3723&\mbox{ if }|Y_{2}|=1,\\\
3.7016&\mbox{ if }|Y_{2}|=2.\end{cases}$

As $F_{0}^{\prime}-u\cong K_{1,|Y_{2}|+3}$,

$\rho(F_{0}^{\prime}-u)=\begin{cases}2&\mbox{ if }|Y_{2}|=1,\\\
\sqrt{5}&\mbox{ if }|Y_{2}|=2.\end{cases}$

Thus,

$\rho(F_{0})<\rho(F_{0}^{\prime})\mbox{ and
}\rho(F_{0}-u)\geqslant\rho(F_{0}^{\prime}-u).$

If $n=5+|Y_{2}|$, then $\rho(F_{0})<\rho(F_{0}^{\prime})$, a contradiction,
and if $n>5+|Y_{2}|$, then we have by Lemma 2.5 that
$\rho(F_{0}^{\prime}uG[V(G)\setminus V(F_{0})\cup\\{u\\}])>\rho$, also a
contradiction.

This shows that $X_{1}\cup X_{2}=\emptyset$, as desired. ∎

By Claim 4.10, we have $X=X_{0}^{*}\cup X_{3}$ and $Y=\emptyset$, so $G\cong
K_{1}\vee(K_{1}\cup\tfrac{n-2}{3}K_{3})$, which, by Lemma 4.4, is a
contradiction if $n\geqslant 8$. Thus $n=5$ and $G\cong F_{1}$.

Case 3. $X_{0}^{*}=\emptyset$.

Case 3.1. $X_{0}^{\prime}=\emptyset$.

In this case, $X_{0}=\emptyset$. If $X_{1}\cup X_{2}=\emptyset$, then $G\cong
K_{1}\vee\tfrac{n-3}{3}K_{3}$, which, by Lemma 4.4, is a contradiction. So
$X_{1}\cup X_{2}\neq\emptyset$.

Next, we show that $Y_{1}\cup Y_{2}\cup Y_{2}^{\prime}=\emptyset$. Suppose to
the contrary that $Y_{1}\cup Y_{2}\cup Y_{2}^{\prime}\neq\emptyset$.

######  Claim 4.11.

For each $w\in Y_{1}\cup Y_{2}\cup Y_{2}^{\prime}$ and one neighbor $v$ of $w$
in $X_{1}\cup X_{2}$, any path from $w$ to $u$ passes through some vertex of
the component $H$ of $G[X]$ containing $v$.

###### Proof.

Suppose that this is not true. let $P$ be a path from $w$ to $u$ that does not
pass through any vertex of $H$. Let $v_{1}$ be a neighbor of $u$ on $P$. As
$X_{0}=\emptyset$, $N_{X}(v_{1})\neq\emptyset$. Let $v_{1}^{\prime}\in
N_{X}(v_{1})$. Assume that $v_{1}^{\prime}\notin V(P)$. Then with
$v^{\prime}\in N_{X}(v)$, $uv^{\prime}vwP[w,v_{1}]v_{1}v_{1}^{\prime}u$ is a
cycle with chords $uv$ and $uv_{1}$, a contradiction. ∎

######  Claim 4.12.

$Y_{2}^{\prime}=\emptyset$.

###### Proof.

Otherwise, assume that $w\in Y_{2}^{\prime}$. Let $v$ be the neighbor of $w$
in $X_{2}^{\prime}$. By Claims 4.1 and 4.11, there is a path from $w$ to $u$
containing some vertex $v^{*}\in N_{X}(v)$. Then, with $v^{\prime}\in
N_{X}(v)\setminus\\{v^{*}\\}$, $uv^{\prime}vwP[w,v^{*}]v^{*}u$ is a cycle with
chords $uv$ and $vv^{*}$, a contradiction. ∎

By Claim 4.12, we assume that $w\in Y_{1}\cup Y_{2}$. Let $v_{1}$ be one
neighbor of $w$ in $X_{1}\cup X_{2}$ and $H$ be the component of $G[X]$
containing $v_{1}$, which is a copy of $K_{2}$ or $K_{1,2}$. Denote by $v_{2}$
the pendant vertex in $H$ different from $v_{1}$.

Let $Y_{H}=N_{Y}(v_{1})\cup N_{Y}(v_{2})$.

######  Claim 4.13.

For any $z\in Y_{H}$, $d_{G}(z)=2$.

###### Proof.

By Claims 4.5 and 4.6, $z$ has one or two neighbors in $H$.

Suppose first that $z$ has two neighbors in $H$, that is, the two neighbors
are $v_{1}$ and $v_{2}$. If $N_{Y}(z)\neq\emptyset$, say $z^{\prime}\in
N_{Y}(z)$, then by Claim 4.1, there is a path from $z^{\prime}$ to $u$ which
does not pass through $z$. By Claims 4.11 and 4.12, a shortest such path $P$
passes through one of $v_{1}$ and $v_{2}$, say $v_{1}$. Then $v_{2}$ does not
lie on $P$. So $uv_{2}zz^{\prime}P[z^{\prime},v_{1}]v_{1}u$ is a cycle with
chords $v_{1}v_{2}$ and $v_{1}z$ if $H\cong K_{2}$ and
$uv_{0}v_{2}zz^{\prime}P[z,v_{1}]v_{1}u$ is a cycle with chords $v_{0}v_{1}$
and $v_{1}z$ if $H\cong K_{1,2}$ with center $v_{0}$, a contradiction. It
follows that $N_{Y}(z)=\emptyset$, so $d_{G}(z)=2$.

Suppose next that $z$ has exactly one neighbor, say $v_{1}$, in $H$. Suppose
that $d_{Y}(z)\geqslant 2$. Next, we show that $N_{Y}(z)\subseteq Y_{H}$.
Suppose that this is not true. Then $z$ has a neighbor in $Y_{0}$, so
$|Y_{0}|\geqslant 1$. Note that $X_{0}=\emptyset$. By Claim 4.3,
$e(X^{*},Y_{2})\leqslant 2|Y_{2}|$. By Claim 4.6, $e(X_{1},Y_{1})\leqslant
2|Y_{1}|$. Now (4.1) becomes

$3(|X_{1}|+|X_{2}|+|Y_{1}|+|Y_{2}|+|Y_{0}|)-6\leqslant|X_{1}|+|X_{2}|+2|X_{2}|-2|X_{2}^{\prime}|+2|Y_{1}|+2|Y_{2}|$

i.e., $|X_{1}|+2|X_{2}^{\prime}|+3|Y_{0}|+|Y_{1}|+|Y_{2}|\leqslant 6$, so
$|Y_{0}|=1$. If $X_{1}\neq\emptyset$, then $z\in Y_{H}\subseteq Y_{1}$, so
$Y_{H}=\\{z\\}$. If $X_{2}^{\prime}\neq\emptyset$, then $z\in Y_{H}\subset
Y_{2}$, so $Y_{H}=\\{z\\}$. In either case, $z$ is a cut vertex of $G$, a
contradicting Claim 4.1. So $N_{Y}(z)\subseteq Y_{H}$. By Claims 4.1 and 4.11,
there is a path $P$ from $z$ to $u$ containing $v_{2}$ but not $v_{1}$. Let
$z^{\prime}\in N_{Y}(z)$ outside $P$. Assume that $z^{\prime}v_{1}\in E(G)$.
Then $uv_{1}z^{\prime}zP[z,v_{2}]v_{2}u$ is a cycle with chords $v_{1}v_{2}$
and $v_{1}z$ if $H\cong K_{2}$ and $uv_{1}z^{\prime}zP[z,v_{2}]v_{2}v_{0}u$ is
a cycle with chords $v_{0}v_{1}$ and $v_{1}z$ if $H\cong K_{1,2}$ with center
$v_{0}$, a contradiction. So $d_{Y}(z)\leqslant 1$. By Claim 4.1,
$d_{Y}(z)=1$, so $d_{G}(z)=2$. ∎

By Claims 4.5, 4.6 and 4.13, $e(Y_{H})\leqslant\tfrac{|Y_{H}|}{2}$, so
$\sum_{z\in Y_{H}}x_{u}x_{z}>\sum_{zz^{\prime}\in
E(G[Y_{H}])}x_{z}x_{z^{\prime}}$. Assume that $x_{v_{1}}\geqslant x_{v_{2}}$.

Suppose that $H\cong K_{2}$. Let

$\displaystyle G^{\prime}$ $\displaystyle=G-\\{v_{2}z:z\in
N_{Y}(v_{2})\setminus N_{Y}(v_{1})\\}-\\{zz^{\prime}\in E(G):z,z^{\prime}\in
Y_{H}\\}$ $\displaystyle\quad+\\{v_{1}z:z\in N_{Y}(v_{2})\setminus
N_{Y}(v_{1})\\}+\\{uz:z\in Y_{H}\\}.$

It is easy to see that $G^{\prime}$ does not contain a DCC1. But we have by
Rayleigh’s principle that

$\rho(G^{\prime})\geqslant\rho+2\sum_{z\in N_{Y}(v_{2})\setminus
N_{Y}(v_{1})}(x_{v_{1}}-x_{v_{2}})x_{z}+2\left(\sum_{z\in
Y_{H}}x_{u}x_{z}-\sum_{zz^{\prime}\in
E(G[Y_{H}])}x_{z}x_{z^{\prime}}\right)>\rho,$

a contradiction.

Suppose that $H\cong K_{1,2}$. Let $v_{0}$ be the center of $H$. Let

$G^{\prime}=\begin{cases}\begin{aligned} &G-\\{v_{i}z_{i}:z_{i}\in
N_{Y}(v_{i}),i=1,2\\}-\\{zz^{\prime}\in E(G):z,z^{\prime}\in Y_{H}\\}\\\
&\quad+\\{uz,v_{0}z:z\in Y_{H}\\}\end{aligned}&\mbox{if $x_{v_{0}}\geqslant
x_{v_{1}}$},\\\ \begin{aligned} &G-v_{0}v_{2}-\\{v_{2}z:z\in
N_{Y}(v_{2})\\}-\\{zz^{\prime}\in E(G):z,z^{\prime}\in Y_{H}\\}\\\
&\quad+v_{1}v_{2}+\\{uz:z\in Y_{H}\\}+\\{v_{1}z:z\in N_{Y}(v_{2})\setminus
N_{Y}(v_{1})\\}\end{aligned}&\mbox{otherwise}.\end{cases}$

Note that $G^{\prime}$ does not contain a DCC1. Let $U_{0}=N_{Y}(v_{1})\cap
N_{Y}(v_{2})$, $U_{1}=N_{Y}(v_{1})\setminus U_{0}$ and
$U_{2}=N_{Y}(v_{2})\setminus U_{0}$. If $x_{v_{0}}\geqslant x_{v_{1}}$, as one
of $U_{0},U_{1},U_{2}$ is not empty, so

$\displaystyle\rho(G^{\prime})$ $\displaystyle\geqslant\rho(G)+2\sum_{z\in
U_{0}}(x_{u}+x_{v_{0}}-x_{v_{1}}-x_{v_{2}})x_{z}$
$\displaystyle\quad+2\sum_{z\in U_{1}}(x_{v_{0}}-x_{v_{1}})x_{z}+2\sum_{z\in
U_{2}}(x_{v_{0}}-x_{v_{2}})x_{z}$ $\displaystyle\quad+2\left(\sum_{z\in
U_{1}\cup U_{2}}x_{u}x_{z}-\sum_{zz^{\prime}\in E(G[U_{1}\cup
U_{2}])}x_{z}x_{z^{\prime}}\right)$ $\displaystyle>\rho,$

and otherwise, we have $x_{v_{1}}>x_{v_{0}}$, so

$\displaystyle\rho(G^{\prime})$
$\displaystyle\geqslant\rho+2(x_{v_{1}}-x_{v_{0}})x_{v_{2}}+2\sum_{z\in
U_{2}}(x_{v_{1}}-x_{v_{2}})x_{z}$ $\displaystyle\quad+2\sum_{z\in
U_{0}}(x_{u}-x_{v_{2}})x_{z}+2\left(\sum_{z\in U_{1}\cup
U_{2}}x_{u}x_{z}-\sum_{zz^{\prime}\in E(G[U_{1}\cup
U_{2}])}x_{z}x_{z^{\prime}}\right)$ $\displaystyle>\rho.$

Thus we reach a contradiction in either case. This shows that $Y_{1}\cup
Y_{2}\cup Y_{2}^{\prime}=\emptyset$. Thus, $Y=\emptyset$.

Suppose that there are two components in $G[X_{1}\cup X_{2}]$, say $H_{1}$ and
$H_{2}$. Let $v_{i}$ be the center of $H_{i}$ for $i=1,2$ (if $H_{i}\cong
K_{2}$, then $v_{i}$ is arbitrary). Assume that $x_{v_{1}}\geqslant
x_{v_{2}}$. Let

$G^{\prime}=G-\\{v_{2}z:z\in N_{X}(v_{2})\\}\cup\\{v_{1}z:z\in
N_{X}(v_{1})\\}.$

Obviously, $G^{\prime}$ does not contain a DCC1. By Lemma 2.2,
$\rho(G^{\prime})>\rho$, a contradiction. So $G[X_{1}\cup X_{2}]$ is
connected, i.e., either $X_{1}\neq\emptyset$ or $X_{2}\neq\emptyset$.

If $X_{1}\neq\emptyset$, then $|X_{1}|=2$, so $G\cong
K_{1}\vee(K_{2}\cup\tfrac{n-3}{3}K_{3})$, which, by Lemma 4.4, is a
contradiction.

If $X_{2}\neq\emptyset$, then $|X_{2}^{\prime}|=1$, $G\cong
K_{1}\vee(K_{1,t}\cup\tfrac{n-t-2}{3}K_{3})$ for some $2\leqslant t\leqslant
n-2$, so we have by Lemma 4.5 that $t=n-2$, i.e., $G\cong K_{1,1,n-2}$.

Case 3.2. $X_{0}^{\prime}\neq\emptyset$.

In this case, $X_{1}\cup X_{2}^{\prime}\neq\emptyset$. As
$X_{0}^{\prime}\neq\emptyset$, we have $v_{0}w\in E(G)$ for some $v_{0}\in
X_{0}^{\prime}$ and some $w\in Y_{1}\cup Y_{2}^{\prime}$.

Case 3.2.1. $w\in Y_{1}$.

From (4.6), $Y_{2}=Y_{2}^{\prime}=\emptyset$.

Let $v_{1}$ be a neighbor of $w$ in $X_{1}$ and $v_{2}$ the neighbor of
$v_{1}$ in $X$. Let $X_{1}^{\prime}=\\{v_{1},v_{2}\\}$,
$X_{0}^{\prime\prime}=\cup_{v\in X_{1}^{\prime}}X_{v}$,
$Y^{*}=N_{Y}(v_{1})\cup N_{Y}(v_{2})$ and $Y^{\prime}=N_{Y}(v_{1})\cap
N_{Y}(v_{2})$.

By similar argument as in the proof of Claim 4.9, $Y^{\prime}=\\{w\\}$ or
$Y^{\prime}=\emptyset$.

Suppose that $Y^{\prime}=\\{w\\}$. Then
$e(X_{0}^{\prime\prime},Y_{1})=|X_{0}^{\prime\prime}|$. As
$e(X_{1}^{\prime},Y_{1})=|Y^{*}|+1$, we have by (4.1) that $|Y^{*}|=1$,
$e(X_{1}^{\prime},Y^{*})=2$ and $1\leqslant|X_{0}^{\prime\prime}|\leqslant 3$.
So $N_{G}(w)=X_{1}^{\prime}\cup X_{0}^{\prime\prime}$. Let
$F_{2}=G[\\{u\\}\cup N_{G}[w]]$. Then $F_{2}$ is the graph obtained from
$K_{2,|X_{0}^{\prime\prime}|+2}$ with bipartition $(\\{u,w\\},N_{G}(w))$ by
adding an edge $v_{1}v_{2}$. Thus, if $n=4+|X_{0}^{\prime\prime}|$, then
$G=F_{2}$, and if $n>4+|X_{0}^{\prime\prime}|$, then $G$ consists of $F_{2}$
and $G[V(G)\setminus N_{G}[w]]$ with a common vertex $u$. Let $F_{2}^{\prime}$
be a copy of $K_{1,1,|X_{0}^{\prime\prime}|+2}$ obtained from
$K_{2,|X_{0}^{\prime\prime}|+2}$ as above by adding an edge $uw$. By a direct
calculation, we have

$\rho(F_{2})=\begin{cases}2.8858&\mbox{ if }|X_{0}^{\prime\prime}|=1,\\\
3.1413&\mbox{ if }|X_{0}^{\prime\prime}|=2,\\\ 3.4142&\mbox{ if
}|X_{0}^{\prime\prime}|=3,\end{cases}\mbox{ and
}\rho(F_{2}-u)=\begin{cases}2.1701&\mbox{ if }|X_{0}^{\prime\prime}|=1,\\\
2.3429&\mbox{ if }|X_{0}^{\prime\prime}|=2,\\\ 2.5141&\mbox{ if
}|X_{0}^{\prime\prime}|=3.\end{cases}$

From Lemma 2.6,

$\rho(F_{2}^{\prime})=\begin{cases}3&\mbox{ if }|X_{0}^{\prime\prime}|=1,\\\
3.3723&\mbox{ if }|X_{0}^{\prime\prime}|=2,\\\ 3.7016&\mbox{ if
}|X_{0}^{\prime\prime}|=3.\end{cases}$

Evidently, $F_{2}^{\prime}-u\cong K_{1,|X_{0}^{\prime}|+2}$, so

$\rho(F_{2}^{\prime}-u)=\begin{cases}\sqrt{3}&\mbox{ if
}|X_{0}^{\prime\prime}|=1,\\\ 2&\mbox{ if }|X_{0}^{\prime\prime}|=2,\\\
\sqrt{5}&\mbox{ if }|X_{0}^{\prime\prime}|=3.\end{cases}$

Thus

$\rho(F_{2})<\rho(F_{2}^{\prime})\mbox{ and
}\rho(F_{2}-u)>\rho(F_{2}^{\prime}-u).$

If $n=4+|X_{0}^{\prime\prime}|$, then $\rho(F_{2})<\rho(F_{2}^{\prime})$, a
contradiction, and if $n>4+|X_{0}^{\prime\prime}|$, then we have by Lemma 2.5
that $\rho(F_{2}^{\prime}uG[V(G)\setminus N_{G}[w]])>\rho$, also a
contradiction.

Suppose that $Y^{\prime}=\emptyset$. Then $e(X_{1},Y_{1})=|Y^{*}|$ and
$e(X_{0}^{\prime\prime},Y_{1})\leqslant|X_{0}^{\prime\prime}|+|Y^{*}|-1$, so
we have by (4.1) that $|Y^{*}|=1$ and $|X_{0}^{\prime\prime}|\leqslant 2$. As
$G+v_{2}w$ also does not contain a DCC1, we have by Lemma 2.1 that
$\rho(G+v_{2}w)>\rho$, a contradiction.

Case 3.2.2. $w\in Y_{2}^{\prime}$.

Let $v\in N_{X}(w)$. As $G$ does not contain a DCC1, $N_{Y}(w)=\emptyset$. So
$G^{\prime}=G-\\{vz:z\in N_{Y}(v)\\}+\\{uz:z\in N_{Y}(v)\\}$ also does not
contain a DDC1. By Lemma 2.2, $\rho(G^{\prime})>\rho$, a contradiction.

Combining the above cases, we have $G\cong F_{1},K_{1,1,n-2},K_{3,n-3}$. Note
that $\rho(F_{1})>\rho(K_{1,1,3})>\rho(K_{3,2})$. By Lemma 2.6, we have (1.1).
∎

##  5 Proof of Theorem 1.3

######  Lemma 5.1.

[28] Let $H_{n}$ be defined as in Theorem 1.3. Then

$\rho(H_{n})=\begin{cases}\frac{n+1}{2}&\mbox{ if }n\equiv 1\pmod{2},\\\
\frac{1+\sqrt{n^{2}+1}}{2}&\mbox{ if }n\equiv 0\pmod{4},\\\ \eta(n)&\mbox{ if
}n\equiv 2\pmod{4},\end{cases}$

where $\eta(n)$ is the largest root of
$x^{3}-x^{2}-\tfrac{n^{2}}{4}x+\tfrac{n}{2}=0$.

###### Proof of Theorem 1.3.

Suppose that $G$ is an $n$-vertex $K_{1}\vee P_{4}$-free graph that maximizes
the spectral radius. By similar argument as in the proof of Theorem 1.1, $G$
is connected. It suffices to show that $G\cong H_{n}$.

Let $\rho=\rho(G)$ and let $\mathbf{x}$ be the Perron vector of $G$ and $u$ a
vertex with maximum entry in $\mathbf{x}$. Let $X=N_{G}(u)$ and
$Y=V(G)\setminus N_{G}[u]$. From (2.1), we have

$\rho^{2}\leqslant|X|+2e(X)+e(X,Y).$

Note that $H_{n}$ is $K_{1}\vee P_{4}$-free, $\rho(G)\geqslant\rho(H_{n})$. By
Lemma 5.1,
$\rho(G)^{2}\geqslant\rho(H_{n})^{2}\geqslant\tfrac{(n+1)^{2}-1}{4}$, and
moreover, $\rho(G)^{2}\geqslant 16$ if $n=7$ and $\rho(G)^{2}\geqslant 21$ if
$n=8$. Thus

$|X|+2e(X)+e(X,Y)\geqslant\frac{(n+1)^{2}-1}{4}$ (5.1)

and

$|X|+2e(X)+e(X,Y)\geqslant\begin{cases}16&\mbox{if $n=7$},\\\ 21&\mbox{if
$n=8$}.\end{cases}$ (5.2)

As $G$ is $K_{1}\vee P_{4}$-free, $G[X]$ is $P_{4}$-free, so each component of
$G[X]$ is a triangle $K_{3}$, isolated vertex $K_{1}$, isolated edge $K_{2}$,
or a star $K_{1,r}$ with some $r\geqslant 2$. In particular,
$e(X)\leqslant|X|=d_{u}$.

######  Claim 5.1.

For any $w\in Y$, $w$ is adjacent to at most one vertex of a triangle in
$G[X]$.

###### Proof.

Suppose that there is a vertex $w\in Y$ such that it is adjacent to two
vertices, say $v_{1},v_{2}$, of a triangle with vertices $v_{1},v_{2},v_{3}$
in $G[X]$. Suppose that $G[X]$ contains a component isomorphic to $K_{3}$ with
vertices $v_{1},v_{2},v_{3}$. Assume that $v_{1}w,v_{2}w\in E(G)$. Then
$wv_{1}uv_{3}$ is a copy of $P_{4}$ in $G$ and $v_{2}$ is adjacent to all
vertices of this path, so $G$ contains $K_{1}\vee P_{4}$ as a subgraph, a
contradiction. ∎

Let $d_{2}(u)$ be the number of vertices of distance two from $u$ in $G$.

######  Claim 5.2.

$d_{2}(u)=n-1-d_{u}$.

###### Proof.

If $G[X]$ contains a triangle, then $e(X,Y)\leqslant(d_{u}-2)d_{2}(u)$ by
Claim 5.1, so

$\displaystyle d_{u}+2e(X)+e(X,Y)$ $\displaystyle\leqslant
d_{u}+2d_{u}+d_{u}d_{2}(u)-2d_{2}(u)$
$\displaystyle=d_{u}(d_{2}(u)+3)-2d_{2}(u)$
$\displaystyle\leqslant\frac{(d_{u}+d_{2}(u)+3)^{2}}{4}-2,$

and if $G[X]$ does not contain any triangle, then
$e(X)\leqslant|X|-1=d_{u}-1$, so

$d_{u}+2e(X)+e(X,Y)\leqslant
d_{u}+2(d_{u}-1)+d_{u}d_{2}(u)\leqslant\frac{(d_{u}+d_{2}(u)+3)^{2}}{4}-2.$

In either case, we have by (5.1) that

$\frac{(n+1)^{2}-1}{4}\leqslant
d_{u}+2e(X)+e(X,Y)\leqslant\frac{(d_{u}+d_{2}(u)+3)^{2}}{4}-2,$

implying that $d_{u}+d_{2}(u)+3>n+1$, i.e., $d_{u}+d_{2}(u)\geqslant n-1$,
which shows $d_{u}+d_{2}(u)=n-1$. ∎

######  Claim 5.3.

$G[X]$ does not contain a triangle.

###### Proof.

Suppose that $G[X]$ contains at least a triangle. Let $t$ be the number of
triangles in $G[X]$.

Suppose that there is a component in $G[X]$ that is not a triangle. By Claims
5.1 and 5.2,

$\displaystyle d_{u}+2e(X)+e(X,Y)$ $\displaystyle\leqslant
d_{u}+2(d_{u}-1)+(d_{u}-2t)(n-1-d_{u})$ $\displaystyle\leqslant
d_{u}+2(d_{u}-1)+(d_{u}-2)(n-1-d_{u})$
$\displaystyle=-(d_{u}^{2}-(n+4)d_{u}+2n),$

so from (5.1), we have

$d_{u}^{2}-(n+4)d_{u}+2n+\frac{(n+1)^{2}-1}{4}\leqslant 0,$

which is impossible as the discriminant of the quadratic polynomial in $d_{u}$
in the left hand side of the above inequality is $(n+4)^{2}-8n-(n+1)^{2}+1<0$
when $n\geqslant 9$. If $n=8$, then from (5.2), we have
$d_{u}^{2}-12d_{u}+37\leqslant 0$, which is also impossible. Suppose that
$n=7$. From (5.2), we have $d_{u}^{2}-11d_{u}+30\leqslant 0$, so $d_{u}=5,6$,
implying that $G\cong F_{3},K_{1}\vee(K_{3}\cup K_{1,2})$, where $F_{3}$ is a
graph obtained from $K_{1}\vee(K_{3}\cup K_{2})$ by adding a vertex adjacent
to one vertex of $K_{3}$ and one vertex of $K_{2}$. By a direct calculation,
$\rho(F_{3}),\rho(K_{1}\vee(K_{3}\cup K_{1,2}))<\rho(H_{n})$, a contradiction.
Suppose that $n=6$. Then $d_{u}^{2}-10d_{u}+24\leqslant 0$, so $d_{u}=4,5$,
implying that $G\cong F_{4},K_{1}\vee(K_{3}\cup K_{2})$, where $F_{4}$ is a
graph obtained from $K_{1}\vee(K_{3}\cup K_{1})$ by adding a vertex adjacent
to one vertex of $K_{3}$ and the vertex of degree one. By a direct
calculation, $\rho(G)<\rho(H_{6})$, a contradiction. It now follows that every
component in $G[X]$ is a triangle. So $G[X]\cong tK_{3}$ with $d_{u}=3t$ for
some $t\geqslant 1$. By (5.1), Claims 5.1 and 5.2, we have

$\frac{(n+1)^{2}-1}{4}\leqslant 3t+6t+t(n-1-3t)=-3t^{2}+(n+8)t,$

i.e.,

$3t^{2}-(n+8)t+\frac{(n+1)^{2}-1}{4}\leqslant 0.$

which is also impossible as $(n+8)^{2}-3(n+1)^{2}+3=-2(n^{2}-5n+32)<0$. ∎

By Claim 5.3, any component of $G[X]$ with at least three vertices is a star.

######  Claim 5.4.

Let $H$ be a component of $G[X]$ with at least three vertices and $v$ be its
center. For any $w\in Y$, if $vw\in E(G)$, then $v$ is the unique neighbor of
$w$ in $H$.

###### Proof.

Suppose that there is a vertex $v_{1}\in V(H)\setminus\\{v\\}$ such that
$v_{1}w\in E(G)$. Let $v_{2}$ be another vertex in $H$ different from $v$ and
$v_{1}$. Then $v_{2}uv_{1}w$ is a $P_{4}$ in $G$ and $v$ is adjacent to all
such vertices, which shows that $G$ contains $K_{1}\vee P_{4}$ as a subgraph,
a contradiction. ∎

From Claim 5.4, we have $d_{X}(w)\leqslant d_{u}-r$ for any $w\in Y$, where
$r$ denotes the number of components of $G[X]$ with at least three vertices.

######  Claim 5.5.

There is at most one component with at least three vertices in $G[X]$.
Moreover, if such a component exists, then $G[X]$ has exactly one component
and $e(X,Y)\geqslant(d_{u}-1)(n-1-d_{u})-1$.

###### Proof.

Denote by $r$ the number of components of $G[X]$ with at least three vertices.
If $r\geqslant 2$, then we have by (5.1) and Claim 5.4 that

$\frac{(n+1)^{2}-1}{4}\leqslant d_{u}+2(d_{u}-r)+(d_{u}-r)(n-1-d_{u})\leqslant
d_{u}+2(d_{u}-2)+(d_{u}-2)(n-1-d_{u}),$

i.e.,

$d_{u}^{2}-(n+4)d_{u}+2(n+1)+\frac{(n+1)^{2}-1}{4}\leqslant 0,$

which is impossible. So $r\leqslant 1$.

Suppose that $r=1$. If $G[X]$ has at least two components, then $e(X)\leqslant
d_{u}-2$, so we have by (5.1) that

$\frac{(n+1)^{2}-1}{4}\leqslant d_{u}+2(d_{u}-2)+(d_{u}-1)(n-1-d_{u}),$

i.e.,

$d_{u}^{2}-(n+3)d_{u}+(n+3)+\frac{(n+1)^{2}-1}{4}\leqslant 0,$

which is impossible as $(n+3)^{2}-4(n+3)-(n+1)^{2}+1=-3<0$. So $G[X]$ contains
exactly one component. If $e(X,Y)\leqslant(d_{u}-1)(n-1-d_{u})-2$, then by
(5.1),

$\frac{(n+1)^{2}-1}{4}\leqslant d_{u}+2(d_{u}-1)+(d_{u}-1)(n-1-d_{u})-2,$

so $d_{u}^{2}-(n+3)d_{u}+(n+3)+\frac{(n+1)^{2}-1}{4}\leqslant 0$, which is
impossible. Thus $e(X,Y)\geqslant(d_{u}-1)(n-1-d_{u})-1$. ∎

Now we consider two cases.

Case 1. There is exactly one component with at least three vertices in $G[X]$.

By Claim 5.5, $G[X]\cong K_{1,d_{u}-1}$. It follows from (5.1) that

$\frac{(n+1)^{2}-1}{4}\leqslant|X|+2e(X)+e(X,Y)\leqslant
d_{u}+2(d_{u}-1)+(d_{u}-1)(n-1-d_{u}),$

implying that $\tfrac{n+3-\sqrt{5}}{2}\leqslant
d_{u}\leqslant\tfrac{n+3+\sqrt{5}}{2}$. That is,

$d_{u}=\begin{cases}\frac{n+1}{2},\frac{n+3}{2},\frac{n+5}{2}&\mbox{ if $n$ is
odd,}\\\ \frac{n+2}{2},\frac{n+4}{2}&\mbox{ if $n$ is even.}\end{cases}$

If $n=6$, then $d_{u}=4,5$, so $G\cong H_{6},K_{1,1,4}$, and a direct
calculation shows that $\rho(K_{1,1,4})=3.3723<3.3923=\rho(H_{6})$, so $G\cong
H_{6}$. If $n=7$, then $d_{u}=4,5,6$, so $G\cong H_{n},4K_{1}\vee(K_{2}\cup
K_{1}),K_{1,1,6}$, and a direct calculation shows that
$\rho(4K_{1}\vee(K_{2}\cup
K_{1}))=3.3273<3.7016=\rho(K_{1,1,5})<4=\rho(H_{n})$, so $G\cong H_{7}$.
Suppose that $n\geqslant 8$. Then $d_{u}\geqslant 5$. Let $v$ be the center of
$G[X]$. If $vw\in E(G)$ for some $w\in Y$, then by Claim 5.4, we have
$e(X,Y)\leqslant(d_{u}-1)(n-2-d_{u})+1<(d_{u}-1)(n-1-d_{u})-2$, contradicting
Claim 5.5, so $vw\notin E(G)$ for any $w\in Y$. By Claim 5.5, there are at
least two vertices $v_{1},v_{2}\in X$ that are adjacent to each vertex in $Y$.
If $G[Y]$ contains a path $P_{3}$, say $w_{1}w_{2}w_{3}$, then
$G[\\{w_{1},v_{1},w_{3},v_{2}\\}]$ contains a path $P_{4}$ and $w_{2}$ is
adjacent to the vertices of the path, so $G$ contains $K_{1}\vee P_{4}$, a
contradiction. Thus $G[Y]$ is does not contain any $P_{3}$, i.e., $G[Y]$
consists of isolated vertices or edges. As adding edges between isolated
vertices in $G[Y]$ does not lead to a copy of $K_{1}\vee P_{4}$, we have by
Lemma 2.1 that $G[Y]$ contains at most one isolated vertex. Therefore, $G\cong
aK_{1}\vee(bK_{2}\cup cK_{1})$, where $a=d_{u}-1$, $c\leqslant 1$ and
$a+2b+c=n$.

Case 1.1 $c=0$.

In this case, $G\cong aK_{1}\vee\tfrac{n-a}{2}K_{2}$, and it is easy to see
$\rho(G)=\frac{1}{2}(1+\sqrt{1+4a(n-a)})$, so

$a=\begin{cases}\frac{n+1}{2}&\mbox{ if }n\equiv 1\pmod{4},\\\
\frac{n-1}{2}&\mbox{ if }n\equiv 3\pmod{4},\\\ \frac{n}{2}&\mbox{ if }n\equiv
0\pmod{4},\\\ \frac{n+2}{2}&\mbox{ if }n\equiv 2\pmod{4}.\end{cases}$

Therefore, $G\cong H_{n}$ if $n\equiv 0,1,3\pmod{4}$. If $n\equiv 2\pmod{4}$,
then $G\cong\tfrac{n+2}{2}K_{1}\vee\tfrac{n-2}{4}K_{2}$, and a direct
calculation and Lemma 5.1 show that
$\rho(G)=\tfrac{1+\sqrt{n^{2}-3}}{2}<\rho(H_{n})$, a contradiction.

Case 1.2. $c=1$.

In this case, $G\cong aK_{1}\vee(\tfrac{n-a-1}{2}K_{2}\cup K_{1})$ and $A(G)$
has an equitable quotient matrix

$B^{\prime}=\begin{pmatrix}0&n-a-1&1\\\ a&1&0\\\ a&0&0\end{pmatrix}$

with respect to vertex partition $V(G)=V(aK_{1})\cup
V(\tfrac{n-a-1}{2}K_{2})\cup V(K_{1})$, so by Lemma 2.3, $\rho(G)$ is equal to
the largest root of $g(x,a)=0$ with
$g(x,a):=\det(xI_{3}-B^{\prime})=x^{3}-x^{2}-a(n-a)x+a$. Note that

$g(x,a)-g(x,a+1)=(n-2a-1)x-1<0$

as $a=d_{u}-1\geqslant\tfrac{n-1}{2}$. So

$a=\begin{cases}\frac{n-1}{2}&\mbox{ if }n\equiv 1\pmod{4},\\\
\frac{n+1}{2}&\mbox{ if }n\equiv 3\pmod{4},\\\ \frac{n+2}{2}&\mbox{ if
}n\equiv 0\pmod{4},\\\ \frac{n}{2}&\mbox{ if }n\equiv 2\pmod{4}.\end{cases}$

Therefore, $G\cong H_{n}$ if $n\equiv 2\pmod{4}$. Otherwise,
$G\cong\tfrac{n-1}{2}K_{1}\vee(\tfrac{n-1}{4}K_{2}\cup K_{1})$ if $n\equiv
1\pmod{4}$, $G\cong\tfrac{n+1}{2}K_{1}\vee(\tfrac{n-3}{4}K_{2}\cup K_{1})$ if
$n\equiv 3\pmod{4}$ and $G\cong\tfrac{n+2}{2}K_{1}\vee(\tfrac{n-4}{4}K_{2}\cup
K_{1})$ if $n\equiv 0\pmod{4}$. However, by an easy calculation,

$\displaystyle g(\rho(H_{n}),a)$
$\displaystyle=\begin{cases}\frac{n-1}{2}&\mbox{ if }n\equiv 1\pmod{4}\\\
\frac{n+1}{2}&\mbox{ if }n\equiv 3\pmod{4}\\\ \frac{(n+2)(n+4)}{4}&\mbox{ if
}n\equiv 0\pmod{4}\end{cases}$ $\displaystyle>0$

so $\rho(G)<\rho(H_{n})$ if $n\equiv 0,1,3\pmod{4}$, a contradiction.

Combining Cases 1.1 and 1.2, we have $G\cong H_{n}$.

Case 2. $G[X]$ does not contain a component with at least three vertices.

In this case, $G[X]$ consists of isolated vertices and isolated edges, and
$e(X)\leqslant\lfloor\tfrac{d_{u}}{2}\rfloor$. We claim that $G[X]$ contains
at most one isolated vertex, as otherwise, $e(X)\leqslant\tfrac{d_{u}-2}{2}$,
so we have by (5.1) that

$\frac{(n+1)^{2}-1}{4}\leqslant d_{u}+d_{u}-2+d_{u}(n-1-d_{u}),$

i.e.,

$d_{u}^{2}-(n+1)d_{u}+\frac{(n+1)^{2}-1}{4}+2\leqslant 0.$

which is impossible as $(n+1)^{2}-(n+1)^{2}+1-8=-7<0$. Similarly,
$e(X,Y)\geqslant d_{u}(n-1-d_{u})-1$. By (5.1),

$\frac{(n+1)^{2}-1}{4}\leqslant|X|+2e(X)+e(X,Y)\leqslant
d_{u}+2\left\lfloor\frac{d_{u}}{2}\right\rfloor+d_{u}(n-1-d_{u}),$

so $d_{u}$ is even with $\tfrac{n}{2}\leqslant d_{u}\leqslant\tfrac{n+2}{2}$.

If $n=6$, then $d_{u}=4$, so the inequality above is actually an equality, so
$G\cong 2K_{1}\vee 2K_{2}$ with $\rho(2K_{1}\vee 2K_{2})=3.3723<\rho(H_{6})$,
a contradiction. If $n=7$, then we have from (5.2) that $16\leqslant
d_{u}+d_{u}+d_{u}(6-d_{u})$, so $d_{u}=4$ and $G\cong H_{n}$, as desired. If
$n=8$, then $21\leqslant d_{u}+d_{u}+d_{u}(7-d_{u})$, which is impossible.

Suppose that $n\geqslant 9$. Then $d_{u}\geqslant 5$, so there are at least
two adjacent vertices $v_{1},v_{2}\in X$ that are adjacent to each vertex in
$Y$. If $G[Y]$ contains an edge $w_{1}w_{2}$, then
$G[\\{u,v_{2},w_{1},w_{2}\\}]$ contains a path $P_{4}$ as a subgraph and
$v_{1}$ is adjacent to the vertices of the path, so $G$ contains $K_{1}\vee
P_{4}$ as a subgraph, a contradiction. Thus $Y$ is independent. As adding
possible edges between vertices in $X$ and $Y$ does not lead to a copy of
$K_{1}\vee P_{4}$, we have by Lemma 2.1 that each vertex in $X$ is adjacent to
all vertices in $Y$. Therefore, $G\cong(n-d_{u})K_{1}\vee(bK_{2}\cup cK_{1})$,
where $c\leqslant 1$ and $2b+c=d_{u}$. If $n\equiv 0\pmod{4}$, then
$d_{u}=\tfrac{n}{2}$, so $G\cong H_{n}$, as desired. If $n\equiv 2\pmod{4}$,
then $d_{u}=\tfrac{n+2}{2}$, so
$G\cong\tfrac{n-2}{2}K_{1}\vee\tfrac{n+2}{4}K_{2}$, for which, we have by a
direct calculation that $\rho(G)=\tfrac{1+\sqrt{n^{2}-3}}{2}<\rho(H_{n})$, a
contradiction. If $n\equiv 1\pmod{4}$, then $d_{u}=\tfrac{n+1}{2}$, which
contradicts that $d_{u}$ is even. If $n\equiv 3\pmod{4}$, then
$d_{u}=\tfrac{n+1}{2}$ and $G\cong H_{n}$, as desired. ∎

Acknowledgements

This work was supported by National Natural Science Foundation of China (No.
12071158).

## References

  * [1] B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978.
  * [2] J.A. Bondy, Large cycles in graphs, Discrete Math. 1 (2) (1971) 121–132.
  * [3] A. Brouwer, W. Haemers, Spectra of Graphs, Springer, New York, 2012.
  * [4] R.A. Brualdi, E.S. Solheid, On the spectral radius of connected graphs, Publ. Inst. Math. (Beograd) (N.S.) 39 (53) (1986) 45–54.
  * [5] R.A. Brualdi, E.S. Solheid, On the spectral radius of complementary acyclic matrices of zeros and ones, SIAM J. Algebraic Discrete Methods 7 (2) (1986) 265–272.
  * [6] J. Cai, L. Xu, B. Zhou, Spectral conditions for the existence of (doubly) chorded cycles in graphs with fixed size, ArXiv: 2405.03229v1.
  * [7] S. Chiba, T. Yamashita, Degree conditions for the existence of vertex-disjoint cycles and paths: a survey, Graphs Combin. 34 (1) (2018) 1–83.
  * [8] S. Cioabǎ, D. Desai, M. Tait, A spectral Erdős–Sós, theorem, SIAM J. Discrete Math. 37 (2023) 2228–2239.
  * [9] C.M. Conde, E. Dratman, L.N. Grippo, On the spectral radius of block graphs having all their blocks of the same size, Linear Algebra Appl., 634 (2022) 137–148.
  * [10] M. Cream, R.J. Faudree, R.J. Gould, K. Hirohata, Chorded cycles, Graphs Combin. 32 (6) (2016) 2295–2313.
  * [11] J. Czipszer, Solution to Problem 127 (in Hungarian), Mat. Lapok 14 (1963) 373–374.
  * [12] N. Draganić, A. Methuku, D. Munhá Correia, B. Sudakov, Cycles with many chords, Random Struct. Alg. 65 (2024) 3–16.
  * [13] F. Esser, F. Harary, On the spectrum of a complete multipartite graph, Eur. J. Comb. 1 (1980) 2110–218.
  * [14] Y. Gao, X. Lin, H. Wang, Vertex-disjoint double chorded cycles in bipartite graphs, Discrete Math. 342 (9) (2019) 2482–2492.
  * [15] R.J. Gould, Results and problems on chorded cycles: a survey, Graphs Combin. 38 (2022) 189, 27 pp.
  * [16] R.J. Gould, K. Hirohata, P. Horn, On independent doubly chorded cycles, Discrete Math. 338 (11) (2015) 2051–2071.
  * [17] T. Jiang, A note on a conjecture about cycles with many incident chords, J. Graph Theory 46 (3) (2004) 180–182.
  * [18] Y. Li, Y. Peng, The spectral radius of graphs with no intersecting odd cycles, Discrete Math. 345 (2022) 112907.
  * [19] L. Lovász, Combinatorial Problems and Exercises, North-Holland, 1979.
  * [20] V. Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432 (2010) 2243–2256.
  * [21] L. Pósa, Problem 127 (in Hungarian), Mat. Lapok 12 (1961) 254.
  * [22] M. Santana, M. Van Bonn, Sharp minimum degree conditions for disjoint doubly chorded cycles, J. Comb. 15 (2) (2024) 217–282.
  * [23] H. Wang, X. Hou, Y. Ma, Spectral extrema of graphs with bounded clique number and matching number, Linear Algebra Appl. 669 (2023) 125–135.
  * [24] L. Xu, B. Zhou, Answers to Gould’s question concerning the existence of chorded cycles, ArXiv: 2312.1679.
  * [25] L. Yu, Y. Li, Y. Peng, Spectral extremal graphs for an graphs, ArXiv: 2404.03423.
  * [26] Q. Yuan, R. Liu, J. Yuan, The spectral radius of $H_{2k}$-free graphs, Appl. Math. Comput. 469 (2024) 128560.
  * [27] M. Zhai, R. Liu, J. Xue, A unique characterization of spectral extrema for friendship graphs, Electron. J. Combin. 29 (3) (2022) 3.32.
  * [28] Y. Zhao, X. Huang, H. Lin, The maximum spectral radius of wheel-free graphs, Discrete Math. 344 (2021) 112341.
  * [29] J. Zheng, X. Huang, J. Wang, Spectral radius for the existence of a chorded cycle, ArXiv: 2311.13323v2.