# A spectral Erdős-Rademacher theorem††thanks:  This paper was published on
Advances in Applied Mathematics 158 (2024), No. 102720. This is the final
version; see https://doi.org/10.1016/j.aam.2024.102720. The research was
supported by the NSFC grant 11931002 and 12371362. E-mail addresses:
<EMAIL_ADDRESS>(Y. Li<EMAIL_ADDRESS>(L. Lu<EMAIL_ADDRESS>(Y.
Peng, corresponding author).

Yongtao Li†, Lu Lu†, Yuejian Peng‡
†School of Mathematics and Statistics, Central South University
Changsha, Hunan, 410083, P.R. China
‡School of Mathematics, Hunan University
Changsha, Hunan, 410082, P.R. China

###### Abstract

A classical result of Erdős and Rademacher (1955) indicates a supersaturation
phenomenon. It says that if $G$ is a graph on $n$ vertices with at least
$\lfloor{n^{2}}/{4}\rfloor+1$ edges, then $G$ contains at least
$\lfloor{n}/{2}\rfloor$ triangles. We prove a spectral version of
Erdős–Rademacher’s theorem. Moreover, Mubayi [Adv. Math. 225 (2010)] extends
the result of Erdős and Rademacher from a triangle to any color-critical
graph. It is interesting to study the extension of Mubayi from a spectral
perspective. However, it is not apparent to measure the increment on the
spectral radius of a graph comparing to the traditional edge version (Mubayi’s
result). In this paper, we provide a way to measure the increment on the
spectral radius of a graph and propose a spectral version on the counting
problems for color-critical graphs.

Key words: Extremal graph problems; Spectral radius; Counting triangles.

2010 Mathematics Subject Classification. 05C50, 05C35.

##  1 Introduction

We shall use the following standard notation; see, e.g., the monograph [3].
Let $G$ be a simple graph with vertex set $V(G)=\\{v_{1},\ldots,v_{n}\\}$ and
edge set $E(G)=\\{e_{1},\ldots,e_{m}\\}$. We write $n$ and $m$ for the number
of vertices and edges, respectively, and call the order and size of $G$. Let
$N(v)$ or $N_{G}(v)$ be the set of neighbors of $v$, and $d(v)$ or $d_{G}(v)$
be the degree of a vertex $v$ in $G$. We write $t(G)$ for the number of
triangles in $G$. For a subset $A\subseteq V(G)$, we write $e(A)$ for the
number of edges with two endpoints in $A$, and $G[A]$ for the subgraph of $G$
induced by $A$. For a vertex $w\in V(G)$, we denote by $d_{A}(w)$ the number
of neighbors of $w$ in $A$. For disjoint sets $A$ and $B$, we write $e(A,B)$
for the number of edges between $A$ and $B$. Let $K_{n}$ be the complete graph
on $n$ vertices, and $K_{s,t}$ be the complete bipartite graph with parts of
sizes $s$ and $t$. We write $C_{n}$ and $P_{n}$ for the cycle and path on $n$
vertices, respectively. The Turán graph $T_{n,r}$ is an $n$-vertex complete
$r$-partite graph with each part of size $n_{i}$ such that $|n_{i}-n_{j}|\leq
1$ for all $1\leq i,j\leq r$, that is, $n_{i}$ equals $\lfloor{n}/{r}\rfloor$
or $\lceil{n}/{r}\rceil$. Sometimes, we call $T_{n,r}$ the balanced complete
$r$-partite graph. In particular, we have
$T_{n,2}=K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}$.

###  1.1 Counting substructures for graphs with given size

A graph $G$ is called $F$-free if it does not contain an isomorphic copy of
$F$ as a subgraph. Apparently, every bipartite graph is $C_{2k+1}$-free for
every $k\geq 1$. The Turán number of a graph $F$ is the maximum number of
edges in an $n$-vertex $F$-free graph, and it is usually denoted by
$\mathrm{ex}(n,F)$. An $n$-vertex $F$-free graph with $\mathrm{ex}(n,F)$ edges
is called an extremal graph for $F$. The study of Turán problem goes back to
the work of Mantel [27], which states that if $G$ is a triangle-free graph on
$n$ vertices, then $e(G)\leq\lfloor{n^{2}}/{4}\rfloor$, and equality holds if
and only if $G$ is the balanced complete bipartite graph $T_{n,2}$. Mantel’s
theorem has many interesting applications and generalizations in the
literature; see [1, p. 294] for standard proofs. Inspired by Mantel’s theorem,
the extremal graph theory was widely studied and achieved a rapid development
in the past years; see [15, 39] for comprehensive surveys. In particular,
Rademacher (unpublished, see [10]) extended Mantel’s result by showing that
any graph with $\lfloor n^{2}/4\rfloor+1$ edges has not only one triangle, but
also at least $\lfloor{n}/{2}\rfloor$ triangles.

######  Theorem 1.1 (Erdős–Rademacher [10], 1955).

If $G$ is a graph on $n$ vertices with

$e(G)\geq\left\lfloor\frac{n^{2}}{4}\right\rfloor+1,$

then $G$ contains at least $\lfloor\frac{n}{2}\rfloor$ triangles.

To see the sharpness of Theorem 1.1, one can consider the graph obtained by
adding one edge to the larger color class of $T_{n,2}$. Moreover, $T_{n,2}$ is
the unique graph with $\lfloor n^{2}/4\rfloor$ edges which contains no
triangle. A special case of Erdős [13, Theorem 1] reveals that if
$e(G)\geq\lfloor n^{2}/4\rfloor$, then

$t(G)\geq\left\lfloor\frac{n}{2}\right\rfloor-1,$ (1)

unless $G$ is the bipartite Turán graph $T_{n,2}$.

A graph is called color-critical if its chromatic number can be decreased by
removing an edge. This is a large and important class of graphs for which the
Turán number is well understood. It was shown by Simonovits [38] that for
every color-critical graph $F$ with $\chi(F)=r+1\geq 3$, there exists an
integer $n_{0}=n_{0}(F)$ such that if $n\geq n_{0}$ and $G$ is an $n$-vertex
$F$-free graph, then

$e(G)\leq e(T_{n,r}).$ (2)

Moreover, the equality holds if and only if $G$ is the $r$-partite Turán graph
$T_{n,r}$. In 2010, Mubayi [28] extended Simonovits’ result by proving the
following counting result.

######  Theorem 1.2 (Mubayi [28], 2010).

Let $F$ be a color-critical graph with $\chi(F)=r+1\geq 3$. There exists
$\delta=\delta(F)>0$ such that if $n$ is sufficiently large, $1\leq q<\delta
n$, and $G$ is an $n$-vertex graph with

$e(G)\geq e(T_{n,r})+q,$

then $G$ contains at least $q\cdot c(n,F)$ copies of $F$, where $c(n,F)$ is
the minimum number of copies of $F$ in the graph obtained from $T_{n,r}$ by
adding an edge.

###  1.2 Counting triangles using the spectral radius

Let $G$ be a simple graph on vertex set $\\{v_{1},\ldots,v_{n}\\}$. Let
$A(G)=[a_{ij}]_{i,j=1}^{n}$ be the adjacency matrix of $G$ with the entry
$a_{ij}=a_{ji}=1$ if $v_{i}$ and $v_{j}$ are adjacent, and $a_{ij}=a_{ji}=0$
otherwise. Let $\lambda(G)$ be the spectral radius of $G$, which is defined as
the maximum of modulus of eigenvalues of $A(G)$. The classical extremal graph
problems usually study the maximum or minimum number of edges that the
extremal graphs can have. Correspondingly, we can study the spectral Turán
type problem, which asks for the maximum value $\lambda(G)$ over all $F$-free
graphs $G$ with $n$ vertices. In particular, Nikiforov [31] published the
spectral Turán theorem by showing that if $G$ is a $K_{r+1}$-free graph on $n$
vertices, then $\lambda(G)\leq\lambda(T_{n,r})$, with equality if and only if
$G=T_{n,r}$. In the past few years, the spectral Turán theorem has stimulated
the developments of the spectral extremal graph theory. Various extensions and
generalizations have been obtained in the literature; see, e.g., [43, 29, 31]
for extensions on $K_{r+1}$-free graphs; see [2] for relations between cliques
and spectral radius, [40, 21] for outerplanar and planar graphs, [22, 18, 20]
for non-bipartite triangle-free graphs, [23, 17] for non-bipartite graphs
without short odd cycles, [5, 48, 19] for intersecting triangles, [6] for odd
wheels, [7] for even cycles, [8] for spectral Erdős–Sós theorem, [47] for
$C_{5}$-free, $C_{6}$-free and $K_{2,r+1}$-free graphs with given size, [49]
for books and theta graphs, [41] for $K_{r}$-minor-free graphs, [50] for
$K_{s,t}$-minor-free graphs, [42] for a spectral extremal conjecture, [4, 26,
45] for eigenvalues and regularity, and [34] for a comprehensive survey.

In 2009, Nikiforov [32] proved a spectral generalization of the Simonovits
theorem. More precisely, Nikiforov’s result implies that if $F$ is a color-
critical graph with $\chi(F)=r+1$ where $r\geq 2$, then there exists an
$n_{0}=n_{0}(F)$ such that if $n\geq n_{0}$ and $G$ is an $n$-vertex $F$-free
graph, then

$\lambda(G)\leq\lambda(T_{n,r}),$ (3)

where the equality holds if and only if $G$ is the Turán graph $T_{n,r}$. It
is worth noting that Nikiforov’s result (3) can imply Simonovits’ result (2)
except for the uniqueness; see, e.g., [49, Fact 1.1].

The study on counting substructures and eigenvalues was initiated by Bollobás
and Nikiforov [2] in 2007, who provided a number of relations between the
spectral radius and the number of cliques for a graph $G$ with given order $n$
and size $m$. In particular, the base case gives a spectral supersaturation on
triangles, which asserts that if $G$ is a graph with the spectral radius
$\lambda$, then

$t(G)\geq\frac{\lambda\bigl{(}\lambda^{2}-m\bigr{)}}{3}$

and

$t(G)>\frac{n^{2}}{12}\left(\lambda-\frac{n}{2}\right).$ (4)

Additionally, the first inequality was independently proved by Cioabă, Feng,
Tait and Zhang [5], and it also studied by Ning and Zhai [35]. These
alternative proofs are quite different. Moreover, Ning and Zhai [35] proved a
spectral version of (1) by showing that if $\lambda(G)\geq\lambda(T_{n,2})$,
then

$t(G)\geq\left\lfloor\frac{n}{2}\right\rfloor-1,$ (5)

unless $G=T_{n,2}$. Furthermore, an even more extensive problem, first
explicitly posed by Ning and Zhai [35], is to study the spectral
supersaturation behind Mubayi’s theorem.

######  Problem 1.3 (Ning–Zhai [35], 2023).

(i) (The general case) Find a spectral version of Mubayi’s result.
(ii) (The critical case) For $q=1$, where $q$ is defined as in Theorem 1.2,
find the tight spectral versions when $F$ is some particular color-critical
graph, such as triangle, clique, book, odd cycle or even wheel, etc.

In this paper, we focus our attention on Problem 1.3 and intend to establish a
spectral version in the general case for color-critical graphs. Unlike the
size $e(G)$ of a graph $G$, it seems not obvious to measure the increment on
the spectral radius $\lambda(G)$, since $e(G)$ is always an integer, while
$\lambda(G)$ is not. As commented by Ning and Zhai on the footnote in [35],
finding a spectral version of Mubayi’s result, one had better to give an
estimate or a formula of spectral correspondence of $c(n,F)$. Our contribution
in this paper is twofold. Firstly, we shall give a new way to measure the
increment on the spectral radius and present a spectral conjecture of Theorem
1.2. Secondly, we will confirm the triangle case by showing a spectral version
of Theorem 1.1.

##  2 Main results

###  2.1 A spectral conjecture on Mubayi’s result

In what follows, we shall establish a spectral condition corresponding to the
edge condition $e(G)=e(T_{n,r})+q$. We propose the following counting problem,
which provides a spectral version on Mubayi’s result. Recall that $c(n,F)$ is
the minimum number of copies of $F$ in the graph obtained from the $r$-partite
Turán graph $T_{n,r}$ by adding exactly one edge. In particular, setting
$F=C_{3}$ or $C_{5}$, then $r=2$, we have
$c(n,C_{3})=\lfloor\frac{n}{2}\rfloor$ and
$c(n,C_{5})=\lfloor\frac{n}{2}\rfloor(\lfloor\frac{n}{2}\rfloor-1)(\lceil\frac{n}{2}\rceil-2)$.
Let $T_{n,r,q}$ be the $n$-vertex graph obtained from Turán’s graph $T_{n,r}$
by embedding a star $K_{1,q}$ with $q$ edges into a vertex part of size
$\lceil\frac{n}{r}\rceil$. We propose the following conjecture.

######  Conjecture 2.1.

Let $F$ be a color-critical graph with $\chi(F)=r+1\geq 3$. There exists
$\delta=\delta(F)>0$ such that if $n$ is sufficiently large, $1\leq q<\delta
n$, and $G$ is an $n$-vertex graph with

$\lambda(G)\geq\lambda(T_{n,r,q}),$

then $G$ contains at least $q\cdot c(n,F)$ copies of $F$. Furthermore, the
graph $T_{n,r,q}$ is the unique spectral extremal graph attaining the minimum
number of copies of $F$.

Here, we would like to give an explanation of the original ideas of proposing
such a conjecture. Recently, Pikhurko and Yilma [37] extended Mubayi’s result
and proved that there exist $\delta=\delta(F)>0$ and $n_{0}$ such that for all
$n\geq n_{0}$ and $1\leq q<\delta n$, if $G$ is an $n$-vertex graph with
$e(T_{n,r})+q$ edges which contains the smallest number of copies of $F$, then
$G$ is obtained from $T_{n,r}$ by adding $q$ edges. More precisely, the
extremal graphs with minimum copies of $F$ are obtained from $T_{n,r}$ by
embedding a small subgraph with $q$ edges into a larger vertex part. Upon
computation, we find that the resulting graph attains the maximum spectral
radius when we choose the star $K_{1,q}$ as the embedded subgraph.

Benefited from the techniques of Ning and Zhai [35], we are able to confirm
Conjecture 2.1 in the base case $q=1$ by counting the copies of triangles for
all integers $n$, not only for sufficiently large $n$. Moreover, we show
further that the spectral extremal graph is unique. Our result can be viewed
as a spectral version of Erdős–Rademacher’s result in Theorem 1.1. In the
sequel, we denote by
$K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+}$ the graph obtained
from the balanced complete bipartite graph
$K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}$ by adding exactly one
edge into the part of larger size; see Figure 1.

Figure 1: The unique extremal graph in Theorem 2.2.

######  Theorem 2.2.

If $G$ is a graph on $n$ vertices with

$\lambda(G)\geq\lambda(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+}),$

then $t(G)\geq\lfloor\frac{n}{2}\rfloor$, with equality if and only if
$G=K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+}$.

This paper is organized as follows. In Section 3, we will provide some
preliminaries and lemmas for our purpose, and list the sketch of the proof of
Theorem 2.2. In Section 4, we shall put our attention to the proof of Theorem
2.2. The techniques of our proof of Theorem 2.2 are motivated by that in [35].
To some extent, the results in this paper could be regarded as a complement of
the works in [35, 36]. In our setting, we need to make more structural
analysis of $G$ since the uniqueness is determined. Indispensably, some
different treatments and techniques are needed in our proof. Finally, we give
some concluding remarks and open problems in Section 5.

###  2.2 Remarks on Theorem 2.2

Under the condition of Theorem 2.2, Bollobás–Nikiforov’s result (4) can also
gives a bound on $t(G)$. Indeed, using a forthcoming Lemma 3.1, one can obtain
that if $n$ is even, then $\lambda(G)>\frac{n}{2}+\frac{2}{n}$. Applying (4),
we obtain $t(G)>\frac{n}{6}$; if $n$ is odd, then
$\lambda(G)>\frac{n}{2}+\frac{1.75}{n}$ and $t(G)>0.1458n$. On the other hand,
using Lemma 3.1 again, we can get
$\lambda(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+})<\frac{n}{2}+\frac{2.1}{n}$
for large $n$. Then the lower bound on $t(G)$ guaranteed by (4) is no more
than $0.175n$. Thus, our result in Theorem 2.2 provides a stronger bound
$t(G)\geq 0.5n$ in this sense. More generally, for a graph $G$ satisfying
$\lambda(G)>\lambda(T_{n,r})$ and $\lambda(G)$ is very close to
$\lambda(T_{n,r})$, Conjecture 2.1 also provides a better bound on the number
of cliques $K_{r+1}$ than that of Bollobás and Nikiforov [2]. Although Theorem
2.2 provides a corresponding spectral version of Theorem 1.1, it is not a
generalization on spectral Mantel’s theorem. Moreover, Theorem 2.2 and the
bound in (5) are not comparable since both the condition and result of Theorem
2.2 are slightly stricter. Furthermore, the spectral extremal graph of Theorem
2.2 is determined uniquely, while the equality case in (5) is not.

Last but not least, Erdős–Rademacher’s theorem requires $e(G)>e(T_{n,2})$.
Intuitively, one may ask in Theorem 2.2 that if $G$ satisfies a weaker
condition, namely, $\lambda(G)>\lambda(T_{n,2})$, whether $G$ contains at
least $\lfloor\frac{n}{2}\rfloor$ triangles. Unfortunately, this result does
not hold. Indeed, when $n$ is even, we denote by
$K_{\frac{n}{2}+1,\frac{n}{2}-1}^{+}$ the graph obtained from the bipartite
graph $K_{\frac{n}{2}+1,\frac{n}{2}-1}$ by adding an edge to the vertex part
of size $\frac{n}{2}+1$. Upon computation, it follows that
$\lambda(K_{\frac{n}{2}+1,\frac{n}{2}-1}^{+})$ is the largest root of the
polynomial

$f_{1}(x)=x^{3}-x^{2}+(1-\tfrac{n^{2}}{4})x+\tfrac{n^{2}}{4}-n+1.$

Since $f_{1}(\frac{n}{2})=1-\frac{n}{2}<0$ for $n\geq 4$, we have

$\lambda(K_{\frac{n}{2}+1,\frac{n}{2}-1}^{+})>\lambda(T_{n,2})=\frac{n}{2}.$

However, the number of triangles in $K_{\frac{n}{2}+1,\frac{n}{2}-1}^{+}$ is
exactly $\frac{n}{2}-1$. This example demonstrates that
$t(G)\geq\lfloor\frac{n}{2}\rfloor$ can not be guaranteed in a graph $G$ with
$\lambda(G)>\lambda(T_{n,2})$.

Upon calculations, one can check the following graphs that satisfy
$\lambda(G)>\lambda(T_{n,2})$ and
$t(G)=\left\lfloor\frac{n}{2}\right\rfloor-1$. For simplicity, we provide
these graphs without details.

(a) For even integer $n$, as we have discussed above, the graph
$G=K_{\frac{n}{2}+1,\frac{n}{2}-1}^{+}$ is an extremal graph with
$t(G)=\frac{n}{2}-1$. In addition, there is one more possibility for even $n$.
We denote by $G=K_{\frac{n}{2},\frac{n}{2}}^{+|}$ the graph obtained from
$K_{\frac{n}{2},\frac{n}{2}}$ by adding an edge $e_{1}$ into the part of size
$\frac{n}{2}$ and deleting an edge $e_{2}$ between two parts such that $e_{2}$
is incident to $e_{1}$. By calculation, we obtain that
$\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+|})$ is the largest root of

$f_{2}(x)=x^{4}-\tfrac{n^{2}}{4}x^{2}-(n-2)x+1+\tfrac{n^{2}}{2}-2n.$

One can check that $f_{2}(\frac{n}{2})=1-n<0$ and hence
$\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+|})>\frac{n}{2}=\lambda(T_{n,2})$.

(b) For odd integer $n$, we take $G=K_{\frac{n+1}{2},\frac{n-1}{2}}^{+|}$,
which is the graph obtained from $K_{\frac{n+1}{2},\frac{n-1}{2}}$ by adding
an edge $e_{1}$ into the part of size $\frac{n+1}{2}$ and deleting an edge
$e_{2}$ between two parts such that $e_{2}$ is incident to $e_{1}$. By a
direct calculation, we know that
$\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+|})$ is the largest root of

$f_{3}(x)=x^{4}-\tfrac{n^{2}-1}{4}x^{2}-(n-3)x+\tfrac{n^{2}}{2}-2n+\tfrac{3}{2}.$

Moreover, one can verify that
$f_{3}(\frac{\sqrt{n^{2}-1}}{2})=\frac{n-3}{2}(n-1-\sqrt{n^{2}-1})<0$, which
implies
$\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+|})>\frac{\sqrt{n^{2}-1}}{2}=\lambda(T_{n,2})$.
It is easy to observe that
$t(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+|})=\frac{n-1}{2}-1$.

##  3 Lemmas and outline of the proof

Before stating the detailed proof of Theorem 2.2, we need to present a lemma,
which provides a characterization of the spectral radius of the graph
$K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+}$.

######  Lemma 3.1.

(a) If $n$ is even, then $\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$ is the
largest root of

$f(x)=x^{3}-x^{2}-\frac{n^{2}}{4}x+\frac{n^{2}}{4}-n.$

(b) If $n$ is odd, then $\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+})$ is the
largest root of

$g(x)=x^{3}-x^{2}+\frac{1-n^{2}}{4}x+\frac{n^{2}}{4}-n+\frac{3}{4}.$

Consequently, we have

$\lambda^{2}(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+})>\left\lfloor\frac{n^{2}}{4}\right\rfloor+2.$
(6)

###### Proof.

(a) Let $X=(x_{1},x_{2},\ldots,x_{n})^{T}$ be a Perron eigenvector
corresponding to $\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. We partition the
vertex set of $K_{\frac{n}{2},\frac{n}{2}}^{+}$ as $\Pi$:

$V(K_{\frac{n}{2},\frac{n}{2}}^{+})=X_{1}\cup X_{2}\cup Y,$

where $X_{1}=\\{u^{*},u_{0}\\}$ forms an edge, $X_{1}\cup X_{2}$ and $Y$ are
partite sets of $K_{\frac{n}{2},\frac{n}{2}}$. By comparing the neighborhoods,
we can see that $x_{u^{*}}=x_{u_{0}}$, all coordinates of the vector $X$
corresponding to vertices of $X_{2}$ are equal (the coordinates of vertices of
$Y$ are equal). Without loss of generality, we may assume that
$x_{u^{*}}=x_{u_{0}}=x$, $x_{w}=y$ for each $w\in X_{2}$, and $x_{v}=z$ for
each $v\in Y$. Then

$\begin{cases}\lambda x=x+\frac{n}{2}z,\\\ \lambda y=\frac{n}{2}z,\\\ \lambda
z=2x+(\frac{n}{2}-2)y.\end{cases}$

Thus $\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$ is the largest eigenvalue of

$B_{\Pi}=\begin{bmatrix}1&0&\frac{n}{2}\\\ 0&0&\frac{n}{2}\\\
2&\frac{n}{2}-2&0\end{bmatrix}.$

By calculation, we know that $\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$ is the
largest root of

$f(x)=\det(xI_{3}-B_{\Pi})=x^{3}-x^{2}-\frac{n^{2}}{4}x+\frac{n^{2}}{4}-n.$

(b) For odd $n$, the proof is similar with the previous case. We partition the
vertex set of $K_{\frac{n+1}{2},\frac{n-1}{2}}^{+}$ as $\Pi^{\prime}$:

$V(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+})=X_{1}\cup X_{2}\cup Y,$

where $X_{1}=\\{u^{*},u_{0}\\}$ forms an edge, $X_{1}\cup X_{2}$ and $Y$ are
partite sets of $K_{\frac{n+1}{2},\frac{n-1}{2}}$ satisfying
$|X_{1}|+|X_{2}|=\frac{n+1}{2}$ and $|Y|=\frac{n-1}{2}$. Then a similar
argument yields that $\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+})$ is the
largest eigenvalue of

$B_{\Pi^{\prime}}=\begin{bmatrix}1&0&\frac{n-1}{2}\\\ 0&0&\frac{n-1}{2}\\\
2&\frac{n+1}{2}-2&0\end{bmatrix}.$

Thus, $\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+})$ is the largest root of

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

Finally, we are ready to prove (6). By calculation, we can verify that for
even $n$,

$f\left(\sqrt{{n^{2}}/{4}+2}\right)=\sqrt{n^{2}+8}-n-2<0$

and for every odd $n$,

$g\left(\sqrt{{(n^{2}-1)}/{4}+2}\right)=\sqrt{n^{2}+7}-n-1<0.$

This completes the proof. ∎

Rayleigh’s formula also gives a lower bound on the spectral radius.

$\lambda(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+})>\frac{2e(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+})}{n}=\begin{cases}\frac{n}{2}+\frac{2}{n}&\text{if
$n$ is even;}\\\ \frac{n}{2}+\frac{3}{2n}&\text{if $n$ is odd.}\end{cases}$
(7)

In particular, if $n$ is even, then we get from (7) that
$\lambda^{2}>(\frac{n}{2}+\frac{2}{n})^{2}>\frac{n^{2}}{4}+2$. Thus, this
observation also provides an alternative proof of (6) for even $n$.

The following lemma [44] is also needed in our proof, it provides an operation
of a connected graph which increases the adjacency spectral radius strictly.

######  Lemma 3.2 (Wu–Xiao–Hong [44], 2005).

Let $G$ be a connected graph and $(x_{1},\ldots,x_{n})^{T}$ be a Perron vector
of $G$, where $x_{i}$ corresponds to $v_{i}$. Assume that $v_{i},v_{j}\in
V(G)$ are vertices such that $x_{i}\geq x_{j}$, and $S\subseteq
N_{G}(v_{j})\setminus N_{G}(v_{i})$ is non-empty. Denote
$G^{*}=G-\\{v_{j}v:v\in S\\}+\\{v_{i}v:v\in S\\}$. Then
$\lambda(G)<\lambda(G^{*})$.

The main steps of the proof of Theorem 2.2 can be outlined as below.

First of all, suppose that $G$ is a graph on $n$ vertices with the spectral
radius
$\lambda(G)\geq\lambda(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+})$
and the number of triangles $t(G)\leq\lfloor\frac{n}{2}\rfloor$, our aim is to
characterize the structure of $G$ and show that $G$ is the required extremal
graph $K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+}$. Let
$\bm{x}=(x_{1},\ldots,x_{n})^{T}$ be the unit Perron vector of $G$, and choose
$u^{*}\in V(G)$ as a vertex such that $x_{u^{*}}=\max_{u\in V(G)}x_{u}$. Let
$t^{*}$ be the number of triangles in $G$ containing the vertex $u^{*}$.
Denote by $A=N_{G}(u^{*})$ the set of neighbors of $u^{*}$, and $B$ the set of
remaining vertices outside $A\cup\\{u^{*}\\}$; see Figure 1.

  * $\spadesuit$

Firstly, applying Lemma 3.1, we will show that if $n$ is even, then
$|A|\geq\frac{n}{2}+1$. If $n$ is odd, then $|A|\geq\frac{n+1}{2}$; see the
forthcoming Claim 1. Moreover, we shall show that $t^{*}=e(A)\geq 1$ and
$|B|\geq 1$, and there is no vertex of $B$ which is adjacent to all vertices
of $A$; see Claims 2 and 3.

  * $\heartsuit$

Secondly, we shall prove that $t=t^{*}$. In other words, all triangles in $G$
must contain the vertex $u^{*}$; see Claim 4. By Lemma 3.2, we shall prove
further that the induced subgraph $G[A]=K_{1,t^{*}}\cup(|A|-t^{*}-1)K_{1}$;
see Claim 5.

  * $\clubsuit$

Thirdly, we denote by $u_{0}$ the central vertex of the star $K_{1,t^{*}}$ in
$G[A]$. Then we will show that $d_{B}(u_{0})=0$; see Claim 6. Moreover, we
will prove that $B$ is an independent set in $G$, and then
$N_{G}(w)=A\setminus\\{u_{0}\\}$ for each $w\in B$; see Claims 7 and 8.

  * $\diamondsuit$

Finally, denote by $A_{0}$ the set of isolated vertices of $G[A]$, we will
show that $\sum_{u\in A_{0}}x_{u}<x_{u^{*}}$; see Claim 9. Furthermore, we
will finish the proof by showing that $|A|=t+1$ and $A_{0}=\varnothing$; see
Claim 10. Consequently, $G$ must be the extremal graph
$K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+}$.

Generally speaking, the above steps introduced the key ideas of the approach
of this paper for treating the problem on counting triangles. In next section,
we shall provide the detailed proofs.

##  4 Proof of Theorem 2.2

Now, we are ready to prove Theorem 2.2.

###### Proof of Theorem 2.2.

Assume that $G$ is a graph on $n$ vertices with
$\lambda(G)\geq\lambda(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+})$
and $t(G)\leq\lfloor\frac{n}{2}\rfloor$, our goal is to prove that
$G=K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+}$. Moreover, we
may assume further that $\lambda(G)$ is the maximum. Then $G$ is connected.
Otherwise, adding an edge between two components can increase the spectral
radius and preserve the number of triangles. Let
$\bm{x}=(x_{1},x_{2},\ldots,x_{n})^{T}$ be the unit Perron vector of $G$.
Furthermore, we may assume that $u^{*}\in V(G)$ is a vertex such that
$x_{u^{*}}=\max_{u\in V(G)}x_{u}$. For convenience, we denote
$\lambda=\lambda(G)$ and $t=t(G)$. Let $t^{*}$ be the number of triangles
containing $u^{*}$ in $G$. Let $A=N_{G}(u^{*})$ and
$B=V(G)\setminus(N_{G}(u^{*})\cup\\{u^{*}\\})$. Clearly, we have $t^{*}=e(A)$.
In what follows, we shall present the proof step by step and show several key
claims.

Claim 1. If $n$ is even, then $|A|\geq\frac{n}{2}+1$. If $n$ is odd, then
$|A|\geq\frac{n+1}{2}$. Consequently, we get $|A|\geq\lceil\frac{n}{2}\rceil$.
Combining with $|A|+|B|+1=n$, we have $|B|\leq\lfloor\frac{n}{2}\rfloor-1$.

###### Proof.

By the maximality of $x_{u^{*}}$, we can get $\lambda x_{u^{*}}=\sum_{u\in
A}x_{u}\leq|A|x_{u^{*}}$, which leads to $\lambda\leq|A|$. By Lemma 3.1, we
know that $\lambda^{2}>\lfloor\frac{n^{2}}{4}\rfloor+2$. If $n$ is even, then
$|A|\geq\lambda>\frac{n}{2}$ and so $|A|\geq\lceil\frac{n}{2}\rceil+1$. If $n$
is odd, then $|A|\geq\lambda>(\frac{1}{4}(n^{2}-1)+2)^{1/2}>\frac{n-1}{2}$.
Since $|A|$ is an integer, we get
$|A|\geq\frac{n-1}{2}+1=\lceil\frac{n}{2}\rceil$. ∎

Claim 2. $t^{*}=e(A)\geq 1$ and $|B|\geq 1$.

###### Proof.

Note that $\lambda x_{u^{*}}=\sum_{u\in A}x_{u}$. Then

$\lambda^{2}x_{u^{*}}=\sum_{u\in A}\sum_{w\in
N(u)}x_{w}=|A|x_{u^{*}}+\sum_{u\in A}d_{A}(u)x_{u}+\sum_{w\in
B}d_{A}(w)x_{w}.$ (8)

Recall that $t^{*}=e(A)$. Assume on the contrary that $t^{*}=0$. Then
$d_{A}(u)=0$ for each $u\in A$. Since $\sum_{w\in B}d_{A}(w)x_{w}\leq
e(A,B)x_{u^{*}}\leq|A||B|x_{u^{*}}$. Thus (8) gives

$\lambda^{2}x_{u^{*}}\leq|A|x_{u^{*}}+\sum_{w\in
B}d_{A}(w)x_{w}\leq|A|(|B|+1)x_{u^{*}}\leq\left\lfloor\frac{n^{2}}{4}\right\rfloor
x_{u^{*}}.$

It follows that $\lambda^{2}\leq\lfloor\frac{n^{2}}{4}\rfloor$, which leads to
a contradiction with Lemma 3.1. Thus, we get $t^{*}\geq 1$. If $|B|=0$, then
$V(G)=\\{u^{*}\\}\cup A$ and $|A|=n-1$. Using (8) and $t^{*}\leq
t\leq\lfloor\frac{n}{2}\rfloor$, we have $\lambda^{2}\leq|A|+2t^{*}\leq
n-1+2\lfloor\frac{n}{2}\rfloor\leq\lfloor\frac{n^{2}}{4}\rfloor+2$, where the
last inequality holds for every $n\geq 3$ and $n\neq 4$. This is a
contradiction as Lemma 3.1. For the case $n=4$, we have $|B|=3$ and
$t^{*}\in\\{1,2\\}$. Then either $G=K_{1}\vee(K_{2}\cup K_{1})$ or
$G=K_{1}\vee P_{3}=K_{2,2}^{+}$. Since $\lambda(G)\geq\lambda(K_{2,2}^{+})$,
we get $G=K_{2,2}^{+}$, which is the desired extremal graph. ∎

In fact, the key idea of the remaining proof depends on the full use of (8).
In particular, we will analyse the structure of $G$ to refine the bound on
$e(A,B)$. Let $B_{i}$ be the set of vertices of $B$ which has exactly $i$ non-
neighbors in $A$, that is,

$B_{i}:=\\{w\in B:d_{A}(w)=|A|-i\\}.$

Denote $b_{i}=|B_{i}|$ for $i\in\\{0,1,2,\ldots,|A|\\}$. Then

$\displaystyle e(A,B)$
$\displaystyle\leq(|A|-2)(|B|-b_{0}-b_{1})+(|A|-1)b_{1}+|A|b_{0}$ (9)
$\displaystyle=(|A|-2)|B|+2b_{0}+b_{1}.$

Claim 3. $b_{0}=0$.

###### Proof.

For every $w\in B_{0}$, there are $t^{*}$ triangles consisting of $w$ and an
edge of $A$. On the other hand, each edge of $A$, together with the vertex
$u^{*}$ forms a triangle. Thus, we have $b_{0}t^{*}+t^{*}\leq t$, and then
$b_{0}\leq\frac{t}{t^{*}}-1$. Suppose on the contrary that $b_{0}\neq 0$, and
so $b_{0}\geq 1$. Then we have $1\leq t^{*}\leq\frac{t}{2}$ and $t\geq 2$.
Note that $b_{0}+b_{1}\leq|B|$ and $b_{0}\leq\frac{t}{t^{*}}-1$. It follows
that $2b_{0}+b_{1}\leq|B|+\frac{t}{t^{*}}-1$. By (9), we obtain

$\sum_{w\in B}d_{A}(w)x_{w}\leq
e(A,B)x_{u^{*}}\leq\left(|A||B|-|B|+\frac{t}{t^{*}}-1\right)x_{u^{*}}.$

Moreover, one can observe that

$\sum_{u\in A}d_{A}(u)x_{u}\leq 2e(A)x_{u^{*}}=2t^{*}x_{u^{*}}.$ (10)

Thus, we get from (8) and (10) that

$\lambda^{2}x_{u^{*}}\leq\left(|A|+|A||B|-|B|+\frac{t}{t^{*}}-1+2t^{*}\right)x_{u^{*}}.$
(11)

Denote $g(|B|)=|A|+|A||B|-|B|$ and $f(t^{*})=\frac{t}{t^{*}}-1+2t^{*}$. Recall
that $|A|=n-1-|B|$, by computation, we know that $g(|B|)$ attains the maximum
at $|B|=\lfloor\frac{n}{2}\rfloor-1$. Thus, we get $g(|B|)\leq
g(\lfloor\frac{n}{2}\rfloor-1)=\lfloor\frac{n^{2}}{4}\rfloor-\lfloor\frac{n}{2}\rfloor+1$.
On the other hand, observe that $f(t^{*})$ is convex on
$t^{*}\in[1,\frac{t}{2}]$. Then
$f(t^{*})\leq\max\\{f(1),f(\frac{t}{2})\\}=t+1\leq\lfloor\frac{n}{2}\rfloor+1$.
Therefore, we get from (11) that
$\lambda^{2}\leq\lfloor\frac{n^{2}}{4}\rfloor+2$, which contradicts with
$\lambda^{2}>\lfloor\frac{n^{2}}{4}\rfloor+2$ by Lemma 3.1. Hence, we get
$b_{0}=0$. ∎

Claim 4. We have $t=t^{*}$, that is, all triangles in $G$ contain the vertex
$u^{*}$.

###### Proof.

Assume on the contrary that $t^{*}\leq t-1$. To obtain a contradiction, we are
going to prove the following three items, respectively.

  * (a)

$G[A]=K_{1,t^{*}}\cup(|A|-t^{*}-1)K_{1}$.

  * (b)

$e(B)=0$, that is, $B$ is an independent set in $G$.

  * (c)

Let $u_{0}$ be the central vertex of the star $K_{1,t^{*}}$ in $G[A]$. Then
$d_{B}(u_{0})=0$.

###### Proof.

For (a), suppose on the contrary that $G[A]\neq
K_{1,t^{*}}\cup(|A|-t^{*}-1)K_{1}$. Then for each vertex $w\in B_{1}$, i.e.,
$d_{A}(w)=|A|-1$, the non-adjacent vertices of $w$ in $A$ is a single vertex,
there is at least one edge $\\{u,v\\}\in E(G[A])$ such that
$\\{u,v\\}\subseteq N_{G}(w)\cap A$. This implies that there are at least
$b_{1}$ triangles consisting of a vertex of $B_{1}$ and an edge of $G[A]$.
Thus, we obtain $b_{1}+t^{*}\leq t$. Combining (9) with Claim 3, we get

$e(A,B)\leq(|A|-2)|B|+b_{1}\leq(|A|-2)|B|+t-t^{*}.$

Using (8) and (10) again, we have

$\lambda^{2}x_{u^{*}}\leq|A|x_{u^{*}}+2t^{*}x_{u^{*}}+e(A,B)x_{u^{*}}\leq(|A|+|A||B|-2|B|+t+t^{*})x_{u^{*}}.$
(12)

By computation, we know that the maximum of $|A|+|A||B|-2|B|$ attains at
$|B|=\lfloor\frac{n}{2}\rfloor-2$ since $|A|+|B|+1=n$. Then we get
$|A|+|A||B|-2|B|\leq\lfloor\frac{n^{2}}{4}\rfloor-2\lfloor\frac{n}{2}\rfloor+3$.
Moreover, recall that $t\leq\lfloor\frac{n}{2}\rfloor$, and then $t^{*}\leq
t-1\leq\lfloor\frac{n}{2}\rfloor-1$. Therefore, we get by (12) that
$\lambda^{2}\leq\lfloor\frac{n^{2}}{4}\rfloor+2$, which is a contradiction by
Lemma 3.1.

For (b), suppose on the contrary that there exists an edge
$\\{w_{i},w_{j}\\}\in E(G[B])$, say $w_{i}\in B_{i}$ and $w_{j}\in B_{j}$. By
using (8) and (10), we have

$\lambda^{2}\leq|A|+2t^{*}+e(A,B).$ (13)

Since $b_{0}=0$ by Claim 3, we get that $e(A,B)\leq|A||B|-(|B|-2)-i-j$. Note
that $d_{A}(w_{i})=|A|-i$ and $d_{A}(w_{j})=|A|-j$. Then $w_{i},w_{j}$ have at
least $d_{A}(w_{i})+d_{A}(w_{j})-|A|$ common neighbors. Thus there are
$|A|-i-j$ triangles containing $w_{i}$ and $w_{j}$, and we have
$t^{*}+(|A|-i-j)\leq t$, which together with (13) yields

$\displaystyle\lambda^{2}$ $\displaystyle\leq|A|+2t^{*}+|A||B|-|B|+2-i-j$
$\displaystyle\leq t^{*}+t+|A||B|-|B|+2.$

Similarly, we have $t^{*}+t\leq 2t-1\leq 2\lfloor\frac{n}{2}\rfloor-1$. Since
$|A|+|B|+1=n$ and $|A||B|-|B|$ attains the maximum at
$|B|=\lfloor\frac{n}{2}\rfloor-1$. Then we get
$(|A|-1)|B|\leq(\lceil\frac{n}{2}\rceil-1)(\lfloor\frac{n}{2}\rfloor-1)\leq\lfloor\frac{n^{2}}{4}\rfloor-n+1$.
Thus, we have
$\lambda^{2}\leq\lfloor\frac{n^{2}}{4}\rfloor-n+1+2\lfloor\frac{n}{2}\rfloor-1+2\leq\lfloor\frac{n^{2}}{4}\rfloor+2$,
a contradiction.

For (c), assume on the contrary that there exists an integer
$i\in\\{1,2,\ldots,|A|\\}$ and $w_{i}\in B_{i}$ such that $u_{0}w_{i}$ is an
edge in $G[B]$. We know from Claim 3 that $b_{0}=0$. Since
$d_{A}(w_{i})=|A|-i$, we obtain

$e(A,B)\leq(|A|-1)|B|-(i-1).$ (14)

If $i\leq t^{*}$, then by applying Part (a), there are at least $t^{*}-i$
triangles consisting of $u_{0},w_{i}$ and a leaf vertex of $K_{1,t^{*}}$.
Thus, we have $t^{*}+(t^{*}-i)\leq t$, and so $-i\leq t-2t^{*}$. Then
$e(A,B)\leq(|A|-1)|B|+1+t-2t^{*}$. By (13), we have

$\lambda^{2}\leq|A|+(|A|-1)|B|+1+t.$

Since $t\leq\lfloor\frac{n}{2}\rfloor$ and $|A|+(|A|-1)|B|$ attains the
maximum at $|B|=\lfloor\frac{n}{2}\rfloor-1$. Therefore, we get
$\lambda^{2}\leq\lceil\frac{n}{2}\rceil+(\lceil\frac{n}{2}\rceil-1)(\lfloor\frac{n}{2}\rfloor-1)+1+\lfloor\frac{n}{2}\rfloor\leq\lfloor\frac{n^{2}}{4}\rfloor+2$,
a contradiction. Therefore, we must have $i\geq t^{*}+1$, that is,
$-i+1\leq-t^{*}$. Then (14) gives $e(A,B)\leq(|A|-1)|B|-t^{*}$. Furthermore,
(13) reduces to

$\lambda^{2}\leq|A|+(|A|-1)|B|+t^{*}\leq|A|+(|A|-1)|B|+t-1\leq\lfloor\tfrac{n^{2}}{4}\rfloor,$

which is a contradiction. Thus, we get $d_{B}(u_{0})=0$. ∎

In conclusion, if we assume that $t^{*}\leq t-1$, then by the items (a), (b)
and (c), we see that $G[A]$ consists of a star $K_{1,t^{*}}$ with some
isolated vertices, $B$ is an independent set of $G$, and $N_{G}(w)\subseteq
A\setminus\\{u_{0}\\}$ for every vertex $w\in B$, where $u_{0}$ is the center
of the star $K_{1,t^{*}}$ in $G[A]$. Consequently, it follows that $t=t^{*}$,
which contradicts with the previous assumption. Therefore, we have $t^{*}=t$.
∎

Claim 5. $G[A]=K_{1,t^{*}}\cup(|A|-t^{*}-1)K_{1}$.

###### Proof.

Suppose on the contrary that $G[A]\neq K_{1,t^{*}}\cup(|A|-t^{*}-1)K_{1}$.
First of all, we can see that $b_{1}=0$. Otherwise, if $b_{1}\neq 0$, then
there exists a triangle consisting of a vertex of $B_{1}$ and an edge of
$G[A]$, which leads to $t^{*}<t$. This contradicts with Claim 4. Applying (9)
and Claim 3, we get $e(A,B)\leq(|A|-2)|B|$, equality holds if and only if
$d_{A}(w)=|A|-2$ for every $w\in B$, that is, $B=B_{2}$. By (13), we get

$\displaystyle\lambda^{2}\leq|A|+2t^{*}+(|A|-2)|B|\leq\begin{cases}\frac{n^{2}}{4}+3&\text{if
$n$ is even;}\\\\[2.84526pt] \frac{n^{2}}{4}+2&\text{if $n$ is
odd,}\end{cases}$

where the last inequality holds since $t^{*}\leq\lfloor\frac{n}{2}\rfloor$ and
$|A|+(|A|-2)|B|$ attains the maximum at $|B|=\lfloor\frac{n}{2}\rfloor-2$.
Therefore, if $n$ is odd, then we get a contradiction to (6).

In what follows, we shall also show a contradiction for even $n$. In this
case, by Claim 1, we get $|A|\geq\frac{n}{2}+1$ and $|B|\leq\frac{n}{2}-2$. If
$|B|\neq\frac{n}{2}-2$, then $|B|\leq\frac{n}{2}-3$ and
$\lambda^{2}\leq(\frac{n}{2}+2)+2\frac{n}{2}+\frac{n}{2}(\frac{n}{2}-3)\leq\frac{n^{2}}{4}+2$,
which is a contradiction. Hence we get $|B|=\frac{n}{2}-2$ and
$|A|=\frac{n}{2}+1$. If $t^{*}\leq\frac{n}{2}-1$, then we get
$\lambda^{2}\leq(\frac{n}{2}+1)+2(\frac{n}{2}-1)+(\frac{n}{2}-1)(\frac{n}{2}-2)=\frac{n^{2}}{4}+1$,
a contradiction. Thus, we obtain $t=t^{*}=\frac{n}{2}$. Similarly, if
$b_{i}\neq 0$ for some $i\geq 3$, then $e(A,B)\leq(|A|-2)|B|-1$, which yields
$\lambda^{2}\leq\frac{n^{2}}{4}+2$, a contradiction. Therefore, we have
$b_{3}=b_{4}=\cdots=b_{|A|}=0$ and $B=B_{2}$. To sum up, for even $n$, we have
proved that $|A|=\frac{n}{2}+1$, $|B|=\frac{n}{2}-2$, $t^{*}=t=\frac{n}{2}$
and $d_{A}(w)=|A|-2$ for every $w\in B$.

Next, we continue the proof in two cases, and show that
$\lambda(G)<\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$.

Case 1. $G[A]$ is a tree. Since $G[A]$ is not a star $K_{1,\frac{n}{2}}$, the
longest path of $G[A]$ has at least $4$ vertices. On the other hand, since
$t=t^{*}$ and each vertex of $B$ has exactly $|A|-2$ neighbors in $A$, we can
observe that the longest path of $G[A]$ has at most $5$ vertices. Otherwise,
if $G[A]$ contains a path $P_{6}$, say $u_{1}u_{2}\cdots u_{6}$, then for any
$w\in B$, there exists an $i$ such that the edge $\\{u_{i},u_{i+1}\\}\subseteq
N(w)$, since $w$ has exactly two non-neighbors in $A$. This leads to
$t^{*}<t$, a contradiction. Invoking this observation, the longest path in
$G[A]$ is either $P_{4}$ or $P_{5}$.

Subcase 1.1. If $P_{4}$ is a longest path in $G[A]$, denote by
$P_{4}=u_{0}u_{1}u_{2}u_{3}$, then other vertices of $A$ are adjacent to
either $u_{1}$ or $u_{2}$. Moreover, for each vertex $w\in B$, we have
$d_{A}(w)=|A|-2$. Since $t=t^{*}$, we get $N(w)=A\setminus\\{u_{1},u_{2}\\}$;
see the graph $G_{1}$ in Figure 2.

Figure 2: The longest path of $G[A]$ is $P_{4}$.

Without loss of generality, we may assume that $x_{u_{1}}\leq x_{u_{2}}$. We
define $G_{2}$ as the graph obtained from $G_{1}$ by deleting $d_{A}(u_{1})-1$
neighbors of $u_{1}$, and joining these vertices to $u_{2}$. By Lemma 3.2, we
have $\lambda(G_{1})<\lambda(G_{2})$. Next, we shall show that
$\lambda(G_{2})<\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. By a direct
computation, we know that $\lambda(G_{2})$ is the largest root of

$g_{2}(x):=x^{6}-(\tfrac{n^{2}}{4}-\tfrac{n}{2}+3)x^{4}-nx^{3}+(\tfrac{5n^{2}}{4}-7n+8)x^{2}+(2n-8)x-(n-4)^{2}.$

Recall in Lemma 3.1 that $\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$ is the
largest root of $f(x)=x^{3}-x^{2}-\frac{n^{2}}{4}x+\frac{n^{2}}{4}-n$. For
every $x$ satisfying $x^{2}\geq\frac{n^{2}}{4}+2$, it follows that

$\displaystyle g_{2}(x)-x^{3}f(x)$
$\displaystyle=x^{5}+(\tfrac{n}{2}-3)x^{4}-\tfrac{n^{2}}{4}x^{3}+(\tfrac{5}{4}n^{2}-7n+8)x^{2}+(2n-8)x-(n-4)^{2}$
$\displaystyle>(\tfrac{n}{2}-3)x^{4}+2x^{3}+(\tfrac{5}{4}n^{2}-7n+8)x^{2}+(2x-n+4)(n-4)>0.$

Consequently, we get $g_{2}(x)>x^{3}f(x)$ for every
$x\geq\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. Then
$g_{2}(\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+}))>0$ and $g_{2}(x)>0$ for every
$x\geq\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$, which implies
$\lambda(G_{2})<\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. This is a
contradiction with the assumption.

Subcase 1.2. If $P_{5}$ is a longest path of $G[A]$, say
$P_{5}=u_{0}u_{1}u_{2}u_{3}u_{4}$, then we have
$N(w)=A\setminus\\{u_{1},u_{3}\\}$ for every $w\in B$. Otherwise, if $N(w)\neq
A\setminus\\{u_{1},u_{3}\\}$, then by $d_{A}(w)=|A|-2$, there exists a
triangle containing $w$, which contradicts with $t^{*}=t$. Furthermore, each
vertex of $A\setminus\\{u_{0},\ldots,u_{4}\\}$ is adjacent to either $u_{1}$
or $u_{3}$. Indeed, such a vertex can not adjacent to $u_{0}$ or $u_{4}$ since
$P_{5}$ is a longest path. Moreover, such a vertex can not be adjacent to
$u_{2}$. Otherwise, if $uu_{2}$ is an edge in $G[A]$, then $wuu_{2}$ is a
triangle, contradicting with $t^{*}=t$. Therefore, the structure of $G$ can be
determined as below; see the graph $G_{3}$ in Figure 3.

Figure 3: The longest path of $G[A]$ is $P_{5}$.

Similarly, we may assume further that $x_{u_{1}}\leq x_{u_{3}}$. Let $G_{4}$
be the graph obtained from $G_{3}$ by removing $d_{A}(u_{1})-1$ neighbors of
$u_{1}$, and adding these vertices adjacent to $u_{3}$. By Lemma 3.2 again, we
have $\lambda(G_{3})<\lambda(G_{4})$. Moreover, we shall show that
$\lambda(G_{4})<\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. By computations, we
obtain that $\lambda(G_{4})$ is the largest root of

$\displaystyle g_{4}(x)$
$\displaystyle:=x^{7}-(\tfrac{n^{2}}{4}-\tfrac{n}{2}+3)x^{5}-nx^{4}+(\tfrac{5}{4}n^{2}-7n+5)x^{3}$
$\displaystyle\quad+(3n-16)x^{2}-(\tfrac{3}{2}n^{2}-14n+31)x.$

Moreover, for $x^{2}\geq\frac{n^{2}}{4}+2$, one can verify that

$\displaystyle\tfrac{1}{x}g_{4}(x)-x^{3}f(x)$
$\displaystyle=x^{5}+(\tfrac{n}{2}-3)x^{4}-\tfrac{n^{2}}{4}x^{3}+(\tfrac{5}{4}n^{2}-7n+5)x^{2}+(3n-16)x-(\tfrac{3}{2}n^{2}-14n+31)$
$\displaystyle>(\tfrac{n}{2}-3)x^{4}+2x^{3}+(\tfrac{5}{4}n^{2}-7n+5)x^{2}+(3n-16)x-(\tfrac{3}{2}n^{2}-14n+31)>0.$

In other words, we get $g_{4}(x)>x^{4}f(x)$ for every
$x\geq\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. Recall in Lemma 3.1 that
$\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$ is the largest root of $f(x)$. As a
result, it follows that $g_{4}(\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+}))>0$,
and $g_{4}(x)>0$ for every $x\geq\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$,
which yields $\lambda(G_{4})<\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$.

Case 2. $G[A]$ is not a tree. In this case, $G[A]$ has a cycle. We claim that
$G[A]$ has no cycle of length at least $5$. Otherwise, if $G[A]$ contains a
cycle $C_{t}$ with $t\geq 5$, then there exists a triangle consisting of an
edge of $C_{t}$ and a vertex of $B$, since each vertex of $B$ has exactly two
non-neighbors in $A$. Therefore, we get $t^{*}<t$, which is a contradiction.
Similarly, we can see that $G[A]$ has no triangle. Thus, the longest cycle of
$G[A]$ is $C_{4}$, and the copy of $C_{4}$ is an induced copy. Otherwise, if
this copy of $C_{4}$ is not induced, then it has a chord, and so $G[A]$
contains a triangle, which contradicts with $t^{*}=t$. Assume that
$C_{4}=u_{0}u_{1}u_{2}u_{3}$ is the longest cycle of $G[A]$.

Subcase 2.1. $|A|=5$, that is, $n=8$ and $|B|=2$. Then $G[A]=C_{4}\cup K_{1}$.
For each $w\in B$, we know that $w$ has exactly two non-neighbors in
$\\{u_{0},u_{1},u_{2},u_{3}\\}$. Since $t^{*}=t$ and there is no triangle
containing any vertex $w\in B$, we have two possibilities, i.e., either
$N_{A}(w)=A\setminus\\{u_{1},u_{2}\\}$ or
$N_{A}(w)=A\setminus\\{u_{0},u_{3}\\}$. Thus, $G$ is determined as $G_{5}$ or
$G_{6}$ in Figure 4. By calculations, we obtain that $\lambda(G_{5})\approx
3.934<\lambda(K_{4,4}^{+})$, and $\lambda(G_{6})\approx
3.884<\lambda(K_{4,4}^{+})$, which contradicts with the assumption.

Figure 4: The longest cycle of $G[A]$ is $C_{4}$ and $|A|=5$.

Subcase 2.2. $|A|\geq 6$. In this case, we have $n\geq 10$ and $e(A)=|A|-1\geq
5$. Keeping in mind that $t^{*}=t$, and there is no triangle containing any
vertex $w\in B$. Moreover, each vertex $w\in B$ has exactly two non-neighbors
in $\\{u_{0},u_{1},u_{2},u_{3}\\}$. Fixing a vertex $w_{0}\in B$, we may
assume that $N_{A}(w_{0})=A\setminus\\{u_{1},u_{2}\\}$. For each $u\in
A\setminus\\{u_{0},u_{1},u_{2},u_{3}\\}$, we have $uw\in E(G)$, and $u$ can
not be adjacent to $u_{0}$ or $u_{3}$, that is,
$N_{A}(u)\subseteq\\{u_{1},u_{2}\\}$. Since $e(A)\geq 5$, there exists an edge
in $G[A]$ outside $C_{4}$, say $uu_{2}\in E(G)$, which leads to
$N_{A}(w)=A\setminus\\{u_{1},u_{2}\\}$ for other vertex $w\in
B\setminus\\{w_{0}\\}$. Otherwise, if there is a vertex $w\in
B\setminus\\{w_{0}\\}$ such that $N_{A}(w)\neq A\setminus\\{u_{1},u_{2}\\}$,
then $N_{A}(w)=A\setminus\\{u_{0},u_{3}\\}$, i.e., $w$ is adjacent to both
$u_{1}$ and $u_{2}$, so $wu_{2}u$ forms a triangle, contradicting with
$t^{*}=t$. Thus, the structure of $G$ is determined as in Figure 5.

Figure 5: The longest cycle of $G[A]$ is $C_{4}$ and $|A|\geq 6$.

Without loss of generality, we assume further that $x_{u_{1}}\geq x_{u_{2}}$.
By Lemma 3.2, removing the vertices that are adjacent only to $u_{2}$, and
adding them adjacent to $u_{1}$, we get a new graph $G_{8}$ with larger
spectral radius than $G_{7}$; see Figure 5. Finally, some tedious computations
can yield $\lambda(G_{8})<\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. Indeed,
let $a=|N_{A}(u_{1})\cap N_{A}(u_{2})|$ be the number of vertices of $A$
adjacent to both $u_{1}$ and $u_{2}$, let $b=|N_{A}(u_{1})\setminus
N_{A}(u_{2})|$ be the number of vertices of $A$ adjacent only to $u_{1}$, and
let $c$ be the number of isolated vertices of $G[A]$. Then
$a+b+c=\frac{n}{2}-1$ and $2a+b=e(A)=\frac{n}{2}$. Upon computation, we obtain
that $\lambda(G_{8})$ is the largest root of

$\displaystyle g_{8}(x)$
$\displaystyle:=x^{7}-(\tfrac{a+b+c}{2}n+a+2-c)x^{5}-(4a+2b)x^{4}$
$\displaystyle\quad+((a+b+c)n+\tfrac{ab}{2}n+acn+\tfrac{bc}{2}n-3b-4c-2ac-
bc-4a)x^{3}$
$\displaystyle\quad+2abx^{2}+(2ab+2bc+abc-\tfrac{ab}{2}n-\tfrac{bc}{2}n-\tfrac{abc}{2}n)x.$

It is easy to calculate that for every $x^{2}>\frac{n^{2}}{4}+2$,

$\displaystyle\tfrac{1}{x}g_{8}(x)-x^{3}f(x)$
$\displaystyle=x^{5}+(\tfrac{n^{2}}{4}-\tfrac{a+b+c}{2}x+c-a-2)x^{4}-(\tfrac{n^{2}}{4}-n+4a+2b)x^{3}$
$\displaystyle\quad+((a+b+c)n+\tfrac{ab}{2}n+acn+\tfrac{bc}{2}n-3b-4c-2ac-
bc-4a)x^{2}$
$\displaystyle\quad+2abx+(2ab+2bc+abc-\tfrac{ab}{2}n-\tfrac{bc}{2}n-\tfrac{abc}{2}n)$
$\displaystyle>(\tfrac{n^{2}}{4}-\tfrac{a+b+c}{2}x+c-a-2)x^{4}+(n+2-4a-2b)x^{3}$
$\displaystyle\quad+((a+b+c)n+\tfrac{ab}{2}n+acn+\tfrac{bc}{2}n-3b-4c-2ac-
bc-4a)x^{2}$
$\displaystyle\quad+2abx+(2ab+2bc+abc-\tfrac{ab}{2}n-\tfrac{bc}{2}n-\tfrac{abc}{2}n)>0.$

Henceforth, we get $g_{8}(x)>x^{4}f(x)$ for every
$x\geq\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. Furthermore, it follows that
$g_{8}(\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+}))>0$ and $g_{8}(x)>0$ for every
$x\geq\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$, which implies
$\lambda(G_{8})<\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$, a contradiction. ∎

Claim 6. Let $u_{0}$ be the central vertex of the star $K_{1,t^{*}}$ in
$G[A]$. Then $d_{B}(u_{0})=0$.

###### Proof.

The proof is similar with that of Part (c) in Claim 4. Assume on the contrary
that there exists an integer $i\in\\{1,2,\ldots,|A|\\}$ and $w_{i}\in B_{i}$
such that $u_{0}w_{i}$ is an edge in $G[B]$. Since $d_{A}(w_{i})=|A|-i$ and
$b_{0}=0$, we obtain by (9) that

$e(A,B)\leq(|A|-1)|B|-(i-1).$

If $i\leq t^{*}-1$, then by Claim 5, there are at least $t^{*}-i\geq 1$
triangles consisting of $u_{0},w_{i}$ and a leaf vertex of the star
$K_{1,t^{*}}$, which leads to $t>t^{*}$, contradicting with Claim 4. Hence, we
get $i\geq t^{*}$. Then

$e(A,B)\leq(|A|-1)|B|-t^{*}+1.$

Furthermore, inequality (13) reduces to

$\lambda^{2}\leq|A|+(|A|-1)|B|+t^{*}+1\leq|A|+(|A|-1)|B|+t+1\leq\lfloor\tfrac{n^{2}}{4}\rfloor+2,$

which is a contradiction. Thus, we get $d_{B}(u_{0})=0$. ∎

Claim 7. $e(B)=0$, that is, $B$ is an independent set in $G$.

###### Proof.

Suppose on the contrary that $\\{w_{i},w_{j}\\}$ is an edge of $G[B]$, where
$w_{i}\in B_{i}$ and $w_{j}\in B_{j}$. By Claim 4, we get $t=t^{*}$, which
implies that $N_{A}(w_{i})\cap N_{A}(w_{j})=\varnothing$. By Claim 6, we know
that $N_{A}(w)\subseteq A\setminus\\{u_{0}\\}$ for every $w\in B$. It follows
that $(|A|-i)+(|A|-j)\leq|A|-1$, which yields $i+j\geq|A|+1$. Recall in Claim
3 that $b_{0}=0$. Then

$e(A,B)\leq|A||B|-(|B|-2)-i-j\leq|A||B|-|B|-|A|+1.$

By (13), we get

$\lambda^{2}\leq|A|+2t^{*}+e(A,B)\leq|A||B|-|B|+2t^{*}+1.$

Since $|A||B|-|B|$ attains the maximum at $|B|=\lfloor\frac{n}{2}\rfloor-1$
and $t^{*}\leq\lfloor\frac{n}{2}\rfloor$, we get
$\lambda^{2}\leq\lceil\frac{n}{2}\rceil(\lfloor\frac{n}{2}\rfloor-1)-(\lfloor\frac{n}{2}\rfloor-1)+2\lfloor\frac{n}{2}\rfloor+1\leq\lfloor\frac{n^{2}}{4}\rfloor+2$,
a contradiction. ∎

Finally, we are ready to show that $G$ is the desired extremal graph
$K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+}$.

Claim 8. $N_{G}(w)=A\setminus\\{u_{0}\\}$ for each $w\in B$.

###### Proof.

By Claims 4, 5, 6 and 7 above, we know that all triangles in $G$ must contain
the vertex $u^{*}$, that is, $t^{*}=t\leq\lfloor\frac{n}{2}\rfloor$. Moreover,
$G[A]$ consists of a star $K_{1,t^{*}}$ on the center $u_{0}$ together with
$|A|-t^{*}-1$ isolated vertices. Furthermore, we have $N_{A}(w)\subseteq
A\setminus\\{u_{0}\\}$ for every $w\in B$. In addition, we observe that both
$A\setminus\\{u_{0}\\}$ and $B$ are independent sets, and adding edges between
$B$ and $A\setminus\\{u_{0}\\}$ does not increase the number of triangles. In
our assumption, $G$ is chosen as a graph with the maximum spectral radius,
Thus we obtain $N_{G}(w)=A\setminus\\{u_{0}\\}$ for each $w\in B$. ∎

Let $A_{0}:=\\{u\in A:d_{A}(u)=0\\}$ be the set of isolated vertices in
$G[A]$, and denote by $A_{1}=A\setminus A_{0}$. Then, we have $|A_{1}|=t+1$
and $G[A_{1}]=K_{1,t}$.

Claim 9. We obtain that $\sum_{u\in A_{0}}x_{u}<x_{u^{*}}$.

###### Proof.

Otherwise, if $\sum_{u\in A_{0}}x_{u}\geq x_{u^{*}}$, then we define a new
graph $G^{\prime}$ on vertex set $V(G^{\prime})=V(G)$ with edge set

$E(G^{\prime})=E(G)-\\{u_{0}u^{*}\\}+\\{u_{0}u:u\in A_{0}\\}.$

Observe that $G^{\prime}$ is a bipartite graph on $n$ vertices with two color
classes $A\setminus\\{u_{0}\\}$ and $B\cup\\{u^{*},u_{0}\\}$. Then Nikiforov’s
result implies
$\lambda(G^{\prime})\leq\lambda(T_{n,2})=\sqrt{\lfloor{n^{2}}/{4}\rfloor}$. On
the other hand, we can show that $\lambda(G)\leq\lambda(G^{\prime})$. Indeed,
since $\bm{x}$ is unit, Rayleigh’s formula gives
$\lambda(G^{\prime})\geq\bm{x}^{T}A(G^{\prime})\bm{x}$ and then

$\lambda(G^{\prime})-\lambda(G)\geq\bm{x}^{T}A(G^{\prime})\bm{x}-\bm{x}^{T}A(G)\bm{x}=2x_{0}\left(\sum_{u\in
A_{0}}x_{u}-x_{u^{*}}\right)\geq 0,$

which yields
$\lambda(G)\leq\lambda(G^{\prime})\leq\sqrt{\lfloor{n^{2}}/{4}\rfloor}$, a
contradiction111In fact, it follows further that
$\lambda(G)<\lambda(G^{\prime})$ since $\bm{x}$ can not be a Perron vector of
$G^{\prime}$.. ∎

Claim 10. $|A|=t+1$, that is, $A=A_{1}$ and $A_{0}=\varnothing$.

###### Proof.

Note that Claim 8 gives $N_{G}(u)=\\{u^{*}\\}\cup B$ for every $u\in A_{0}$,
which implies $\lambda x_{u}=x_{u^{*}}+\sum_{w\in B}x_{w}$. By Claim 9, it
follows that

$\lambda x_{u^{*}}>\sum_{u\in A_{0}}\lambda
x_{u}=|A_{0}|x_{u^{*}}+|A_{0}|\sum_{w\in B}x_{w}.$

Thus, by Claim 8 again, we obtain

$\sum_{w\in B}d_{A}(w)x_{w}=(|A|-1)\sum_{w\in
B}x_{w}<(|A|-1)\frac{\lambda-|A_{0}|}{|A_{0}|}x_{u^{*}}\leq\frac{(|A|-1)(t+1)}{|A|-t-1}x_{u^{*}},$

where the last inequality holds by $\lambda\leq|A|$ and $|A_{0}|=|A|-t-1$.
Combining this with (8) and (10), we have

$\lambda^{2}x_{u^{*}}\leq|A|x_{u^{*}}+2tx_{u^{*}}+\sum_{w\in
B}d_{A}(w)x_{w}<\left(|A|+2t+\frac{(|A|-1)(t+1)}{|A|-t-1}\right)x_{u^{*}}.$
(15)

For convenience, we denote

$h(|A|):=|A|+2t+\frac{(|A|-1)(t+1)}{|A|-t-1}.$

Clearly, we have $|A|\geq|A_{1}|=t+1$. Next, we proceed the proof in three
cases.

Case 1. $|A|\geq t+4$.

In this case, to obtain a contradiction, we shall show that
$\lambda^{2}\leq\lfloor\frac{n^{2}}{4}\rfloor+2$. Since $|A|\in[t+4,n-2]$ and
$h(|A|)$ is convex in terms of $|A|$, we get from (15) that

$\lambda^{2}<h(|A|)\leq\max\\{h(t+4),h(n-2)\\}.$ (16)

To determine the maximum in (16), we divide the proof in two subcases.

Subcases 1.1. $t\leq\lfloor\frac{n}{2}\rfloor-1$. By computation, we get

$h(t+4)=\frac{1}{3}t^{2}+\frac{13}{3}t+5\leq\frac{1}{3}\left(\lfloor\frac{n}{2}\rfloor-1\right)^{2}+\frac{13}{3}\left(\lfloor\frac{n}{2}\rfloor-1\right)+5.$

One can check that $h(t+4)\leq\lfloor\frac{n^{2}}{4}\rfloor+2$ for every even
$n\geq 12$ and odd $n\geq 9$. On the other hand, we have

$h(n-2)=(n-2)+2t+\frac{(n-3)(t+1)}{n-t-3}\leq
n-2+2\lfloor\frac{n}{2}\rfloor-2+\frac{(n-3)\lfloor\frac{n}{2}\rfloor}{n-\lfloor\frac{n}{2}\rfloor-2},$

where the inequality holds due to $t\leq\lfloor\frac{n}{2}\rfloor-1$. Then we
can verify that $h(n-2)\leq\lfloor\frac{n^{2}}{4}\rfloor+2$ for every $n$. To
sum up, for $n=9$ and $n\geq 11$, we get from (16) that $\lambda^{2}\leq
h(|A|)\leq\lfloor\frac{n^{2}}{4}\rfloor+2$, a contradiction. Next, we consider
the remaining cases $n\leq 8$ and $n=10$. By Claim 2, we have $t\geq 1$ and
$|B|\geq 1$. Recall that $|A|\geq t+4\geq 5$ and $|A|\leq n-2$. Thus, we get
$n\in\\{7,8,10\\}$. For $n=7$, we must have $t=1$, $|A|=5$ and $|B|=1$. Since
Claim 4 gives $t^{*}=t$, Claim 8 implies $e(A,B)=(|A|-1)|B|$, then by (13), we
get

$\lambda^{2}\leq|A|+2t+(|A|-1)|B|.$ (17)

Consequently, for $n=7$, we obtain $\lambda^{2}\leq
11<\lfloor\frac{n^{2}}{4}\rfloor+2$, a contradiction. For $n=8$, we have
$(t,|A|)=(2,6),(1,5)$ or $(1,6)$. For $n=10$, we have
$(t,|A|)=(4,8),(3,7),(3,8)$, $(2,6),(2,7),(2,8)$, $(1,5),(1,6),(1,7),(1,8)$.
Similarly, using (17), we can verify that
$\lambda^{2}<\lfloor\frac{n^{2}}{4}\rfloor+2$. This is a contradiction.

Subcases 1.2. $t=\lfloor\frac{n}{2}\rfloor$. In this case, we have

$h(t+4)\leq\frac{1}{3}\lfloor\frac{n}{2}\rfloor^{2}+\frac{13}{3}\lfloor\frac{n}{2}\rfloor+5$

It is easy to verify that $h(t+4)\leq\lfloor\frac{n^{2}}{4}\rfloor+2$ holds
for even $n\geq 16$ and odd $n\geq 13$.

Moreover, we have

$h(n-2)\leq
n-2+2\lfloor\frac{n}{2}\rfloor+\frac{(n-3)(\lfloor\frac{n}{2}\rfloor+1)}{n-\lfloor\frac{n}{2}\rfloor-3}.$

One can check that $h(n-2)\leq\lfloor\frac{n^{2}}{4}\rfloor+2$ for every
$n\geq 13$. Therefore, for odd $n\geq 13$ and even $n\geq 16$, we get
$\lambda^{2}\leq h(|A|)\leq\lfloor\frac{n^{2}}{4}\rfloor+2$, a contradiction.
In addition, we have $n-2\geq|A|\geq t+4=\lfloor\frac{n}{2}\rfloor+4$, which
gives rise to $n\geq 11$, and then $n\in\\{11,12,14\\}$. For $n=11$, we have
$t=5$, $|A|=9$ and $|B|=1$. By (17), we get $\lambda^{2}\leq
27<\lfloor\frac{n^{2}}{4}\rfloor+2$, a contradiction. For $n=12$, we have
$t=6$, $|A|=10$ and $|B|=1$, which leads to $\lambda^{2}\leq
31<\lfloor\frac{n^{2}}{4}\rfloor+2$, a contradiction. For $n=14$, we have
$t=7$, and $(|A|,|B|)=(11,2)$ or $(12,1)$, which yields anyway that
$\lambda^{2}<\lfloor\frac{n^{2}}{4}\rfloor+2$, a contradiction.

Case 2. $|A|=t+3$.

By (15), we need to calculate the value $h(|A|)$. If
$t\leq\lfloor\frac{n}{2}\rfloor-1$, then

$h(|A|)=h(t+3)=\frac{1}{2}t^{2}+\frac{9}{2}t+4\leq\frac{1}{2}\left(\lfloor\frac{n}{2}\rfloor-1\right)^{2}+\frac{9}{2}\left(\lfloor\frac{n}{2}\rfloor-1\right)+4.$

For even $n\geq 14$ and odd $n\geq 9$, one can verify that
$h(t+3)\leq\lfloor\frac{n^{2}}{4}\rfloor+2$, a contradiction. Since
$4\leq|A|=t+3\leq n-2$, we have $n\geq 6$. Thus, we need to check the
remaining case $n\in\\{6,7,8,10,12\\}$. For $n=6$, we have $t=1$ and $|A|=4$,
it follows from (17) that $\lambda^{2}\leq 9<\lfloor\frac{n^{2}}{4}\rfloor+2$.
For $n=7$, we have $(t,|A|)=(1,4)$ or $(2,5)$. Using (17), we get
$\lambda^{2}<13<\lfloor\frac{n^{2}}{4}\rfloor+2$, a contradiction. For $n=8$,
we have $(t,|A|)=(1,4),(2,5)$ or $(3,6)$, in which one can verify by (17) that
$\lambda^{2}\leq\lfloor\frac{n^{2}}{4}\rfloor+2$. Moreover, the similar
argument also holds for $n=10$ and $n=12$, respectively. This is a
contradiction.

If $t=\lfloor\frac{n}{2}\rfloor$, then
$h(|A|)=h(t+3)=\frac{1}{2}\lfloor\frac{n}{2}\rfloor^{2}+\frac{9}{2}\lfloor\frac{n}{2}\rfloor+4$.
By computation, we know that $h(|A|)\leq\lfloor\frac{n^{2}}{4}\rfloor+2$ for
even $n\geq 20$ and odd $n\geq 17$, which leads to
$\lambda^{2}\leq\lfloor\frac{n^{2}}{4}\rfloor+2$, a contradiction. Next, we
will check the exceptions for $n\leq 16$ and $n=18$. Since
$n-2\geq|A|=t+3=\lfloor\frac{n}{2}\rfloor+3$, we have $n\geq 9$, and the
following cases in Table 1.

$n$ | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 18
---|---|---|---|---|---|---|---|---|---
$t$ | 4 | 5 | 5 | 6 | 6 | 7 | 7 | 8 | 9
$|A|$ | 7 | 8 | 8 | 9 | 9 | 10 | 10 | 11 | 12
$|B|$ | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5
Table 1: Some examinations in the case $|A|=t+3$ and
$t=\lfloor\frac{n}{2}\rfloor$.

For $n\in\\{9,10,11,12,14\\}$, one can directly verify by (17) that
$\lambda^{2}\leq\lfloor\frac{n^{2}}{4}\rfloor+2$, which is a contradiction.
For the remaining cases $n\in\\{13,15,16,18\\}$, to deduce a contradiction, we
need to refine the bound in (17). Since $G[A]=K_{1,t}\cup 2K_{1}$ and $u_{0}$
is the center, we have

$\sum_{u\in A}d_{A}(u)x_{u}=tx_{u_{0}}+\sum_{u\in N_{A}(u_{0})}x_{u}\leq
tx_{u_{0}}+tx_{u^{*}}.$ (18)

Recall that $N_{G}(w)=A\setminus\\{u_{0}\\}$ for every $w\in B$. We get
$\lambda x_{w}=\sum_{u\in A\setminus\\{u_{0}\\}}x_{u}=\lambda
x_{u^{*}}-x_{u_{0}}$ and then $x_{w}=x_{u^{*}}-\frac{x_{u_{0}}}{\lambda}$.
Therefore, we obtain

$\sum_{w\in
B}d_{A}(w)x_{w}=(|A|-1)|B|x_{w}=(|A|-1)|B|\left(x_{u^{*}}-\frac{x_{u_{0}}}{\lambda}\right).$
(19)

Then by (8), (18) and (19), we get

$\lambda^{2}x_{u^{*}}\leq|A|x_{u^{*}}+tx_{u^{*}}+(|A|-1)|B|x_{u^{*}}+\left(t-\frac{(|A|-1)|B|}{\lambda}\right)x_{u_{0}}.$

Recall that $\lambda\leq|A|$. It follows that

$\lambda^{2}\leq|A|+2t+(|A|-1)|B|-\frac{(|A|-1)|B|}{|A|}.$ (20)

Clearly, the upper bound in (20) refines that in (17). In particular, for
$n=13$, we get from Table 1 that $t=6$, $|A|=9$ and $|B|=3$. Then (20) yields
$\lambda^{2}\leq 45-\frac{24}{9}<\lfloor\frac{n^{2}}{4}\rfloor+2$. For $n=15$,
by (20), we have $\lambda^{2}\leq 60-3.6<\lfloor\frac{n^{2}}{4}\rfloor+2$.
Similarly, for $n=16$ and $n=18$, some computations also lead to
$\lambda^{2}<\lfloor\frac{n^{2}}{4}\rfloor+2$. This is a contradiction.

Case 3. $|A|=t+2$. We present the proof in two subcases.

Subcase 3.1. $n$ is even. Then $t\leq\frac{n}{2}$. Recall in Claim 1 that
$|A|\geq\frac{n}{2}+1$. Hence, we have two possibilities, namely,
$(|A|,t)=(\frac{n}{2}+1,\frac{n}{2}-1)$ or $(\frac{n}{2}+2,\frac{n}{2})$. In
the former case, we have $|B|=n-1-|A|=\frac{n}{2}-2$. Using (20), we obtain

$\lambda^{2}\leq\frac{n^{2}}{4}+\frac{n}{2}-1-\frac{\frac{n}{2}(\frac{n}{2}-2)}{\frac{n}{2}+1}<\frac{n^{2}}{4}+2.$

For the latter case, we have $|B|=\frac{n}{2}-3$. We remark that it is not
sufficient to apply the bound (20) only. In this case, the structure of $G$ is
uniquely determined. By a direct calculation, we know that $\lambda(G)$ is the
largest root of

$p_{1}(x):=x^{5}+(1-\tfrac{n^{2}}{4})x^{3}-nx^{2}+\tfrac{n^{2}}{2}x-2nx-3x.$

By Lemma 3.1, $\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$ is the largest root
of $f(x)=x^{3}-x^{2}-\frac{n^{2}}{4}x+\frac{n^{2}}{4}-n$. Then

$\displaystyle
p_{1}(x)-x^{2}f(x)=x^{4}+x^{3}-\tfrac{n^{2}}{4}x^{2}+\tfrac{n^{2}}{2}x-2nx-3x.$

One can verify that $p_{1}(x)>x^{2}f(x)$ for every $x\geq\frac{n}{2}$. Since
$\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})>\lambda(K_{\frac{n}{2},\frac{n}{2}})=\frac{n}{2}$,
it follows that $p_{1}(\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+}))>0$. Moreover,
$p_{1}(x)>0$ for every $x\geq\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. Thus,
we obtain $\lambda(G)<\lambda(K_{\frac{n}{2},\frac{n}{2}}^{+})$. This
contradicts with the assumption.

Subcase 3.2. $n$ is odd. In this subcase, Claim 1 implies
$|A|\geq\frac{n+1}{2}$ and $t\leq\frac{n-1}{2}$. Thus, there are two
possibilities, more precisely, $(|A|,t)=(\frac{n+1}{2},\frac{n-1}{2}-1)$ or
$(\frac{n+1}{2}+1,\frac{n-1}{2})$. In the first case, we have
$|B|=\frac{n-1}{2}-1$. Applying (20), we get

$\lambda^{2}\leq\frac{n^{2}-1}{4}+\frac{n-3}{2}-\frac{(\frac{n+1}{2}-1)(\frac{n-1}{2}-1)}{\frac{n+1}{2}}<\frac{n^{2}-1}{4}+1.$

For the second case, we have $|B|=\frac{n-1}{2}-2$. Nevertheless, it is also
not sufficient to use (20). By computation, we obtain that $\lambda(G)$ is the
largest root of

$p_{2}(x):=x^{5}+\tfrac{1-n^{2}}{4}x^{3}+(1-n)x^{2}+\tfrac{n^{2}}{2}x-2nx-\tfrac{1}{2}x.$

In view of Lemma 3.1, we know that
$\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+})$ is the largest root of
$g(x)=x^{3}-x^{2}+\frac{1-n^{2}}{4}x+\frac{n^{2}}{4}-n+\frac{3}{4}$. Upon
computation, we get

$p_{2}(x)-x^{2}g(x)=x^{4}+\tfrac{1}{4}x^{2}-\tfrac{n^{2}}{4}x^{2}+\tfrac{n^{2}}{2}x-2nx-\tfrac{x}{2}.$

It is easy to check that $p_{2}(x)>x^{2}g(x)$ for every $x\geq\frac{n-1}{2}$.
Observe that
$\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+})>\lambda(T_{2}(n))>\frac{n-1}{2}$.
It follows that $p_{2}(\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+}))>0$ and
moreover $p_{2}(x)>0$ for every
$x\geq\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+})$. Thus, we get
$\lambda(G)<\lambda(K_{\frac{n+1}{2},\frac{n-1}{2}}^{+})$, contradicting with
the assumption. ∎

From the above discussions, we conclude that $|A|=t+1$. If $n$ is even, then
Claim 1 gives $|A|\geq\frac{n}{2}+1$. Note that $|A|=t+1\leq\frac{n}{2}+1$.
Thus, we must have $|A|=\frac{n}{2}+1,t=\frac{n}{2}$ and $|B|=\frac{n}{2}-2$.
Putting $\\{u^{*},u_{0}\\}$ and $B$ together, one can observe that
$G=K_{\frac{n}{2},\frac{n}{2}}^{+}$, which is the desired extremal graph. If
$n$ is odd, then Claim 1 implies $|A|\geq\frac{n+1}{2}$. Moreover, we have
$t\leq\frac{n-1}{2}$ and $|A|=t+1\leq\frac{n+1}{2}$. Therefore, we obtain
$|A|=\frac{n+1}{2},t=\frac{n-1}{2}$ and $|B|=\frac{n-1}{2}-1$. Moving
$\\{u^{*},u_{0}\\}$ and $B$ together, we see that
$G=K_{\frac{n+1}{2},\frac{n-1}{2}}^{+}$, as desired. This completes the proof.
∎

##  5 Concluding remarks

In the Concluding remarks of [35], Ning and Zhai wrote that for the case of
triangles, is there some interesting phenomenon when we consider the
relationship between the number of triangles and signless Laplacian spectral
radius, Laplacian spectral radius, distance spectral radius and etc?

We answer here that the counting result of triangles does not hold for the
signless Laplacian spectral radius. A result of He, Jin and Zhang [16] implies
that if $G$ is a triangle-free graph on $n$ vertices, then the signless
Laplacian radius $q(G)\leq n$, with equality if and only if $G$ is a complete
bipartite graph. However, for an $n$-vertex graph $G$ with $q(G)>n$, it is
possible that $G$ has exactly one triangle. Indeed, adding one edge into the
independent set of $K_{n-1,1}$, we get a new graph, denote $K_{n-1,1}^{+}$,
which satisfies $q(K_{n-1,1}^{+})>n$, but $t(K_{n-1,1}^{+})=1$. Although the
counting result in terms of $q(G)$ does not hold for triangles, it seems
possible that the spectral counting result is feasible for cliques $K_{r+1}$
for every $r\geq 3$, since it was proved in [16] that for $r\geq 3$, the
$r$-partite Turán graph $T_{n,r}$ is the unique $K_{r+1}$-free graph attaining
the maximum of the signless Laplacian spectral radius.

A well-known result of Nikiforov [30] implies that if $G$ is a triangle-free
graph with $m$ edges, then $\lambda(G)\leq\sqrt{m}$, and equality holds if and
only if $G$ is a complete bipartite graph (possibly with some isolated
vertices). Furthermore, Ning and Zhai [35] proved a counting result, which
asserts that if $\lambda(G)\geq\sqrt{m}$, then $G$ has at least
$\lfloor\frac{\sqrt{m}-1}{2}\rfloor$ triangles, unless $G$ is a complete
bipartite graph. Correspondingly, we illustrate that the counting result is
invalid for graphs with given size in terms of the signless Laplacian radius.
Indeed, it is not difficult to show that if $G$ is a graph with $m\geq 4$
edges, then $q(G)\leq m+1$, where the equality holds if and only if $G$ is a
star $K_{1,m}$. Consequently, for a triangle-free graph $G$, it follows
trivially that $q(G)\leq m+1$, with equality if and only if $G=K_{1,m}$. These
results can also be deduced from a theorem of Zhai, Xue and Lou [46]. With the
help of these results, we obtain that if $G$ satisfies $q(G)\geq m+1$, then
$G=K_{1,m}$, which has no triangle. Moreover, there does not exist a graph $G$
with $m$ edges satisfying $q(G)>m+1$.

Let us mention a couple of problems related to our result. Theorem 2.2 has
confirmed Conjecture 2.1 in the base case $q=1$ for triangles, and it can also
be viewed as a spectral version of Theorem 1.1. In addition, one can also
consider the case $q=1$ in Conjecture 2.1 by counting odd cycles.

######  Problem 5.1 (Counting five-cycles).

If $G$ is an $n$-vertex graph with

$\lambda(G)\geq\lambda(K_{\lceil\frac{n}{2}\rceil,\lfloor\frac{n}{2}\rfloor}^{+}),$

then $G$ contains at least
$\lfloor\frac{n}{2}\rfloor(\lfloor\frac{n}{2}\rfloor-1)(\lceil\frac{n}{2}\rceil-2)$
copies of $C_{5}$.

Next, we intend to propose a possible generalization of Theorem 2.2. In 1962,
Erdős [11, 12] showed that there exists a small constant $c>0$ such that if
$n$ is large enough and $1\leq q<cn$, then every $n$-vertex graph with
$\lfloor n^{2}/4\rfloor+q$ edges has at least $q\lfloor\frac{n}{2}\rfloor$
triangles. Moreover, Erdős conjectured $c=\frac{1}{2}$, which was confirmed by
Lovász and Simonovits [24, 25].

######  Theorem 5.2 (Lovász–Simonovits [24, 25], 1975).

Let $1\leq q<\frac{n}{2}$ be a positive integer and $G$ be an $n$-vertex graph
with

$e(G)\geq\left\lfloor\frac{n^{2}}{4}\right\rfloor+q.$

Then $G$ contains at least $q\lfloor\frac{n}{2}\rfloor$ triangles.

Incidentally, we point out that the condition $q<\frac{n}{2}$ is necessary,
since for even $n$ and $q=\frac{n}{2}$, one can add $q+1$ extra edges to the
larger vertex part of the complete bipartite graph
$K_{\frac{n}{2}+1,\frac{n}{2}-1}$ such that there is no triangle among these
$q+1$ edges. Hence, we get a graph with $\frac{n^{2}}{4}+q$ edges and
$(q+1)(\frac{n}{2}-1)=\frac{n^{2}}{4}-1$ triangles, which is less than
$q\lfloor\frac{n}{2}\rfloor$. It is natural to propose a spectral version of
Theorem 5.2. Recall that $T_{n,2,q}$ is the graph obtained from $T_{n,2}$ by
embedding a star $K_{1,q}$ into the larger vertex part. This suggests the
following question.

######  Problem 5.3.

Let $1\leq q<\frac{n}{2}$ and $G$ be an $n$-vertex graph with

$\lambda(G)\geq\lambda(T_{n,2,q}).$

Then $t(G)\geq q\lfloor\frac{n}{2}\rfloor$, with equality if and only if
$G=T_{n,2,q}$.

Finally, we conclude the spectral supersaturation result for all general
graphs. In 2009, Nikiforov [33] proved a spectral Erdős–Stone–Bollobás
theorem, which implies that for every graph $F$ with $\chi(F)=r+1$ and
$\varepsilon>0$, there exists $n_{0}$ such that if $G$ is a graph on $n\geq
n_{0}$ vertices and $\lambda(G)\geq(1-\frac{1}{r}+\varepsilon)n$, then $G$
contains a copy of $F$. More generally, we can extend this result as follows.

Fact. For any $\varepsilon>0$, there exist $\delta>0$ and $n_{0}$ such that if
$G$ has $n\geq n_{0}$ vertices and

$\lambda(G)\geq\left(1-\frac{1}{r}+\varepsilon\right)n,$

then $G$ contains at least $\delta n^{f}$ copies of $F$, where $f$ is the
number of vertices of $F$.

This spectral supersaturation can be guaranteed by the celebrated graph
removal lemma, which states that for every graph $F$ and $\varepsilon>0$,
there exists $\delta=\delta(F,\varepsilon)>0$ such that any graph on $n$
vertices with at most $\delta n^{f}$ copies of $F$ can be made $F$-free by
removing at most $\varepsilon n^{2}$ edges; see the comprehensive survey [9].
Suppose that $G$ satisfies $\lambda(G)\geq(1-\frac{1}{r}+\varepsilon)n$ and
$G$ has less than $\delta(F,{\varepsilon^{2}}/{8})\cdot n^{f}$ copies of $F$.
Then the graph removal lemma yields that we can remove at most
${\varepsilon^{2}}n^{2}/8$ edges from $G$ such that the remaining subgraph
$G_{1}$ is $F$-free. Another famous result due to Erdős, Frankl and Rödl [14,
Theorem 1.5] states that if $n\geq n_{0}(F,{\varepsilon^{2}}/{8})$ and $G_{1}$
is an $n$-vertex $F$-free graph, then we can remove at most
${\varepsilon^{2}}n^{2}/8$ edges from $G_{1}$ so that the resulting graph
$G_{2}$ is $K_{r+1}$-free. The Wilf theorem (see [43] or [29]) gives that
$\lambda(G_{2})\leq(1-\frac{1}{r})n$. Consequently, the Rayleigh formula gives

$\displaystyle\lambda(G)$
$\displaystyle\leq\lambda(G_{2})+\lambda(G_{1}\setminus
G_{2})+\lambda(G\setminus G_{1})$
$\displaystyle<\lambda(G_{2})+\sqrt{2e(G_{1}\setminus
G_{2})}+\sqrt{2e(G\setminus G_{1})}$
$\displaystyle\leq\left(1-\frac{1}{r}\right)n+\varepsilon n,$

a contradiction. Hence $G$ contains at least
$\delta(F,{\varepsilon^{2}}/{8})\cdot n^{f}$ copies of $F$, as desired.

### Acknowledgements

This work was supported by the NSFC grant (Nos. 11931002 and 12371362), the
Natural Science Foundation of Hunan Province (No. 2021JJ40707) and the
Postdoctoral Fellowship Program of CPSF (No. GZC20233196).

## References

  * [1] B. Bollobás, Extremal Graph Theory, Academic Press, New York, 1978.
  * [2] B. Bollobás, V. Nikiforov, Cliques and the spectral radius, J. Combin. Theory Ser. B 97 (2007) 859–865.
  * [3] J.A. Bondy, U.S.R. Murty, Graph Theory, Vol. 244 of Graduate Texts in Mathematics, Springer, 2008.
  * [4] S. Cioabă, On the extreme eigenvalues of regular graphs, J. Combin. Theory Ser. B 96 (2006) 367–373.
  * [5] S. Cioabă, L. Feng, M. Tait, X.-D. Zhang, The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Combin. 27 (4) (2020), No. P4.22.
  * [6] S. Cioabă, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, European J. Combin. 99 (2022), No. 103420.
  * [7] S. Cioabă, D.N. Desai, M. Tait, The spectral even cycle problem, 10 pages, (2022), arXiv:2205.00990. See https://arxiv.org/abs/2205.00990
  * [8] S. Cioabă, D.N. Desai, M. Tait, A spectral Erdős–Sós theorem, SIAM J. Discrete Math. 37 (3) (2023) 2228–2239.
  * [9] D. Conlon, J. Fox, Graph removal lemmas, in Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., vol. 409, Cambridge Univ. Press, Cambridge, 2013, pp. 1–49.
  * [10] P. Erdős, Some theorems on graphs, Riveon Lematematika 9 (1955) 13–17.
  * [11] P. Erdős, On a theorem of Rademacher–Turán, Illinois J. Math. 6 (1962) 122–127.
  * [12] P. Erdős, On the number of complete subgraphs contained in certain graphs, Magy. Tud. Acad. Mat. Kut. Int. Közl. 7 (1962) 459–474.
  * [13] P. Erdős, On the number of triangles contained in certain graphs, Canad. Math. Bull. 7 (1) (1964) 53–56.
  * [14] P. Erdős, P. Frankl, V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin. 2 (2) (1986) 113–121.
  * [15] Z. Füredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdős Centennial, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013, pp. 169–264.
  * [16] B. He, Y.-L. Jin, X.-D. Zhang, Sharp bounds for the signless Laplacian spectral radius in terms of clique number, Linear Algebra Appl. 438 (2013) 3851–3861.
  * [17] S. Li, W. Sun, Y. Yu, Adjacency eigenvalues of graphs without short odd cycles, Discrete Math. 345 (2022), No. 112633.
  * [18] Y. Li, Y. Peng, Refinement on spectral Turán’s theorem, SIAM J. Discrete Math. 37 (4) (2023) 2462–2485.
  * [19] Y. Li, L. Lu, Y. Peng, Spectral extremal graphs for the bowtie, Discrete Math. 346 (12) (2023), No. 113680.
  * [20] Y. Li, L. Feng, Y. Peng, A spectral extremal problem on non-bipartite triangle-free graphs, Electron. J. Combin. 31 (1) (2024), No. P1.52.
  * [21] H. Lin, B. Ning, A complete solution to the Cvetković–Rowlinson conjecture, J. Graph Theory 97 (3) (2021) 441–450.
  * [22] H. Lin, B. Ning, B. Wu, Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2) (2021) 258–270.
  * [23] H. Lin, H. Guo, A spectral condition for odd cycles in non-bipartite graphs, Linear Algebra Appl. 631 (2021) 83–93.
  * [24] L. Lovász, M. Simonovits, On the number of complete subgraphs of a graph, in: Proc. of Fifth British Comb. Conf., Aberdeen, 1975, pp.431–442.
  * [25] L. Lovász, M. Simonovits, On the Number of Complete Subgraphs of a Graph II, in: Studies in Pure Math, Birkhäuser (dedicated to P. Turán), 1983, pp. 459–495.
  * [26] H. Lu, Regular graphs, eigenvalues and regular factors, J. Graph Theory 69 (2012) 349–355.
  * [27] W. Mantel, Problem 28, Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff. Wiskundige Opgaven, 10 (1907) 60–61.
  * [28] D. Mubayi, Counting substructures I: color critical graphs, Adv. Math. 225 (2010) 2731–2740.
  * [29] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002) 179–189.
  * [30] V. Nikiforov, Walks and the spectral radius of graphs, Linear Algebra Appl. 418 (2006) 257–268.
  * [31] V. Nikiforov, Bounds on graph eigenvalues II, Linear Algebra Appl. 427 (2007) 183–189.
  * [32] V. Nikiforov, Spectral saturation: inverting the spectral Turán theorem, Electron. J. Combin. 16 (1) (2009), No. R33.
  * [33] V. Nikiforov, A spectral Erdős–Stone–Bollobás theorem, Combin. Probab. Comput. 18 (2009) 455–458.
  * [34] V. Nikiforov, Some new results in extremal graph theory, Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011, pp. 141–181.
  * [35] B. Ning, M. Zhai, Counting substructures and eigenvalues I: triangles, European J. Combin. 110 (2023), No. 103685.
  * [36] B. Ning, M. Zhai, Counting substructures and eigenvalues II: quadrilaterals, 14 pages, (2021), arXiv:2112.15279. See https://arxiv.org/abs/2112.15279.
  * [37] O. Pikhurko, Z. B. Yilma, Supersaturation problem for color-critical graphs, J. Combin. Theory Ser. B 123 (2017) 148–185.
  * [38] M. Simonovits, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs, Proc. Colloq., Tihany, 1966, Academic Press, New York, (1968), pp. 279–319.
  * [39] M. Simonovits, Paul Erdős’ influence on extremal graph theory, in The Mathematics of Paul Erdős II, R.L. Graham, Springer, New York, 2013, pp. 245–311.
  * [40] M. Tait, J. Tobin, Three conjectures in extremal spectral graph theory, J. Combin. Theory Ser. B 126 (2017) 137–161.
  * [41] M. Tait, The Colin de Verdière parameter, excluded minors, and the spectral radius, J. Combin. Theory Ser. A 166 (2019) 42–58.
  * [42] J. Wang, L. Kang, Y. Xue, On a conjecture of spectral extremal problems, J. Combin. Theory Ser. B 159 (2023) 20–41.
  * [43] H. Wilf, Spectral bounds for the clique and indendence numbers of graphs, J. Combin. Theory Ser. B 40 (1986) 113–117.
  * [44] B. Wu, E. Xiao, Y. Hong, The spectral radius of trees on $k$-pendant vertices, Linear Algebra Appl. 395 (2005) 343–349.
  * [45] J. Xue, R. Liu, J. Guo, J. Shu, The maximum spectral radius of irregular bipartite graphs, Adv. in Appl. Math. 142 (2023), No. 102433.
  * [46] M. Zhai, J. Xue, Z. Lou, The signless Laplacian spectral radius of graphs with a prescribed number of edges, Linear Algebra Appl. 603 (2020) 154–165.
  * [47] M. Zhai, H. Lin, J. Shu, Spectral extrema of graphs with fixed size: Cycles and complete bipartite graphs, European J. Combin. 95 (2021), No. 103322.
  * [48] M. Zhai, R. Liu, J. Xue, A unique characterization of spectral extrema for friendship graphs, Electron. J. Combin. 29 (3) (2022), No. 3.32.
  * [49] M. Zhai, H. Lin, A strengthening of the spectral color critical edge theorem: books and theta graphs, J. Graph Theory 102 (3) (2023) 502–520.
  * [50] M. Zhai, H. Lin, Spectral extrema of $K_{s,t}$-minor free graphs —– on a conjecture of M. Tait, J. Combin. Theory Ser. B 157 (2022) 184–215.