谱Turán条件下三角形数量的稳定性估计

Stability Estimates for Triangle Counts under the Spectral Turán Condition

摘要: 在谱Turán理论中，图的谱半径被视为刻画图整体稠密程度的重要参数。本文研究谱Turán临界条件下三角形数量的稳定性问题。设$G$ 为一个$n$ 阶简单图，其谱半径满足$\lambda \left(G\right)\ge \lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)$ ，其中$K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}$ 表示由完全二部$K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }$ 图在大小为$\lceil \frac{n}{2}\rceil$ 的部集中添加一条独立边得到的图。我们证明：若$G$ 至少含有一个三角形，且不存在一个顶点同时属于所有三角形，则当$n$ 充分大时，图$G$ 中三角形的总数具有线性下界，即存在一个与$n$ 无关的常数$c\ge 2$ ，使得三角形数不少于$n-c$ 。该结果可视为对已有谱条件下三角形计数结果的稳定性加强。证明中结合了三角形计数不等式、二部图逼近方法以及极值图的谱半径比较等方法。

Abstract: In spectral Turán theory, the spectral radius of a graph is regarded as an important parameter for measuring its global density. In this paper, we study the stability of triangle counts under the spectral Turán threshold. Let $G$ be a simple graph on $n$ vertices whose spectral radius satisfies $\lambda \left(G\right)\ge \lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)$ , where $K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}$ denotes the graph obtained from the complete bipartite graph $K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }$ by adding one edge inside the larger part. We prove that if $G$ contains at least one triangle and no single vertex lies in all triangles, then for sufficiently large $n$ , the total number of triangles in $G$ admits a linear lower bound. More precisely, there exists a constant $c\ge 2$ independent of $n$ , such that the number of triangles in $G$ is at least $n-c$ . This result provides a stability strengthening of previous spectral triangle-counting results. The proof combines triangle counting inequalities, bipartite approximation techniques, and comparisons of spectral radii of extremal graphs.

1. 引言

子图计数问题是图论与组合数学中的一类重要研究问题，在给定边数、顶点数或谱参数等约束下，主要计算特定子图在图中出现的数量，并刻画达到极值时的图结构。三角形作为最小的非平凡圈，在图的局部致密性分析、极值图论以及复杂网络结构研究中均具有重要地位。三角形计数反映了顶点邻域之间的局部连接密度，并与图的整体稠密结构密切相关。因此，在不同约束条件下研究三角形及其相关子图的计数问题，成为了组合图论中的重要研究方向之一。

在经典极值图论中，子图计数问题通常是在边数约束或者点数约束下展开的。在这一背景下，Turán极值问题构成了极值图论中的一类基本问题：在禁用图$F$ 作为子图出现的条件下，确定具有给定点数的图所能达到的最大边数，并进一步刻画达到该极值时的图结构。该类问题不仅给出了禁用给定子图条件下图的稠密度上界，而且为刻画图在临界值约束下的结构做出贡献。作为Turán极值问题中最早且最基

本的结果，Mantel定理表明，若$G$ 为含有$n$ 个顶点的无三角形图，则它的边数至多为$\lfloor \frac{n^2}{4}\rfloor$ ，当且仅当该

图为二部Turán图$T_{n,2}$ 时取等号。这表明Mantel定理不仅给出了无三角形图的最大边数上界，而且刻画了达到该极值时的唯一图结构，为Turán极值问题的系统研究奠定了基础。进一步的问题是，当图的边数略超过禁用给定子图的极值图边数时，子图个数的数量级会发生什么变化？因此，Rademacher以及Erdős的工作揭示了当图的边数略微超过上述极值界时，图中三角形数量具有显式下界[1]。随后，Simonovits将这一思想推广至更一般的颜色临界图，系统研究了Turán极值问题的结构特征[2]；而Mubayi则从计数角度给出了颜色临界子图的线性超饱和结果[3]。这些研究共同奠定了在边数约束下计算给定子图数量的理论框架，并在极值图论中产生了深远影响。

近年来，随着谱图理论的发展，谱半径在刻画图的整体结构方面显现出了独特的优势。谱Turán问题是在经典Turán极值问题的基础上，将极值参数由边数推广为谱半径：在给定顶点数并禁用给定子图$F$ 的条件下，研究图的谱半径所能达到的最大值，并刻画所有达到该极值的图结构。围绕谱条件下的子图存在性与计数问题，已有不少重要结果。Nikiforov系统地发展了谱半径约束下的谱极值问题，证明在禁用完全图$K_{r+1}$ 的条件下，谱半径的极值由相应的Turán图$T_{n,r}$ 实现，从而建立了谱Turán问题的基本框架[4] [5]。在这一框架下，图的谱半径成为衡量图稠密程度的重要参数。设图$G$ 的边数为$m$ ，谱半径记为$\lambda \left(G\right)$ 。Nosal首先证明了当图$G$ 满足$\lambda \left(G\right)>\sqrt{m}$ 时，该图至少包含一个三角形。随后，Bollobás与Nikiforov进一步给出了三角形数量与谱半径之间的不等式关系，揭示了图谱对三角形数量的影响[6]。随后，Ning和Zhai证明：对于一个含有$n$ 个顶点的图$G$ ，若其谱半径满足$\lambda \left(G\right)\ge \lambda \left(T_{n,2}\right)$ ，除非$G$ 是完全二部图$T_{n,2}$ ，

否则$G$ 至少包含$\lfloor \frac{n}{2}\rfloor -1$ 个三角形[7]。该结果可以看作是Erdős-Rademacher定理在谱版本下的对应结果，也是谱条件下三角形计数问题的代表性成果之一。

需要指出的是，上述结果主要关注在临界谱条件下三角形的存在性及其数量，而对于排除达到计数下界的极值图后，三角形的数量是否会出现数量级上的变化，仍缺乏系统刻画。在经典Turán极值框架中，稳定性理论表明：一旦图结构偏离Turán极值结构，其子图的计数往往显著增加。相应地，在谱Turán框架下建立类似的稳定性计数结果，是一个自然且尚未充分发展的方向。

基于上述背景，本文在谱半径约束条件下研究三角形数量的稳定性问题。我们证明：若图满足谱Turán临界条件，并且不属于达到谱Turán极值的极值图类，则三角形数量至少具有线性下界。该结果可以看作是对Ning和Zhai [7]研究结论的一种稳定性加强。本文所用的方法主要是对图$G$ 的边数和图结构进行分析，在一定程度上丰富了谱极值图论中关于三角形计数问题的研究。本文结构如下：第2节给出记号与预备知识；第3节陈述主要结果；第4节给出详细证明；第5节总结。

2. 预备工作

本文仅讨论有限简单无向图。设$G=\left(V\left(G\right),E\left(G\right)\right)$ 为一个图，其中$V\left(G\right)$ 表示顶点集，$E\left(G\right)$ 表示边集。记$\left|V\left(G\right)\right|=n$ ，$\left|E\left(G\right)\right|=m$ 。若$uv\in E\left(G\right)$ ，则称顶点$u$ 与$v$ 相邻。记顶点$v$ 的邻域为

$N_G\left(v\right)=\left\{u\in V\left(G\right):uv\in E\left(G\right)\right\},$

其度数记为$d_G\left(v\right)=\left|N_G\left(v\right)\right|$ 。在不引起混淆的情况下，简记为$N\left(v\right)$ 与$d\left(v\right)$ 。

设$A\left(G\right)$ 表示图$G$ 的邻接矩阵，其最大特征值称为图$G$ 的谱半径，记为$\lambda \left(G\right)$ 。由Perron–Frobenius定理可知，当图$G$ 连通时，$\lambda \left(G\right)$ 为单特征值，且存在对应的正特征向量，称为Perron向量。本文中记该向量为$x=\left(x_1,x_2,\cdots ,x_n\right)$ ，并约定${\max }_{1\le i\le n}{x}_i=1$ 。记$t\left(G\right)$ 为图$G$ 中三角形的个数。记$K_r$ 为含有$r$ 个顶点的完全图，即任意两顶点之间均有一条边相连的简单图。记$T_{n,r}$ 为$n$ 阶$r$ 部Turán图，即将顶点集$V\left(G\right)$ 划分为$r$ 个部分，使各部的大小尽可能均等，并在不同部之间连所有可能的边，而部内不连边。特别地，当

$r=2$ 时，记$T_{n,2}$ 为$n$ 阶完全二部Turán图，即将顶点集划分为两个部$V_1$ 与$V_2$ ，其中$\left|V_1\right|=\lfloor \frac{n}{2}\rfloor$ ，$\left|V_2\right|=\lceil \frac{n}{2}\rceil$ 。$T_{n,2}$ 是不含三角形的$n$ 阶图中边数最大的图，其边数为$e\left(T_{n,2}\right)=\lfloor \frac{n^2}{4}\rfloor$ ，且其谱半径满足$\lambda \left(T_{n,2}\right)=\sqrt{\lfloor \frac{n^2}{4}\rfloor }$ 。进一步地，设$K_{s,t}$ 表示顶点集被划分为大小分别为$s$ 与$t$ ($s+t=n$ )的完全二部图。记$K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}$ 表示由完全二部$K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }$ 图在大小为$\lceil \frac{n}{2}\rceil$ 的部集中添加一条独立边得到的图，$K_{s,t}^{+2}$ 为在$K_{s,t}$ 的某一侧部中嵌入两条独立

的边所得到的图；而$K_{s,t}^{++}$ 则表示在两个侧部中分别加入一条独立的边所得到的图。显然，这几类图均可视为在完全二部结构上施加轻微扰动而产生的非二部图，它们包含一些三角形，但在谱半径意义下与$T_{n,2}$

非常接近。正因如此，$K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1},K_{s,t}^{+2}$ 与$K_{s,t}^{++}$ 常作为谱Turán临界附近的典型模型图，在谱极值与谱超饱和问题的结构分析中发挥重要作用。

下面给出本文后续证明中将用到的若干结果。

定义2.1：设$G=\left(V,E\right)$ 为一张简单图。若两条边$e_1,e_2\in E$ 没有任何公共点，则称$e_1$ 与$e_2$ 相互独立。更一般地，若一组边$F\subseteq E$ 中任意两条边都相互独立，则称$F$ 是一个独立集。

引理2.2：([6])设$G$ 为一张具有$m$ 条边的图，则其三角形数量满足

$t\left(G\right)\ge \frac{\lambda \left(G\right)\left({\lambda }^2\left(G\right)-m\right)}{3},$

并且当且仅当$G$ 为完全二部图(允许存在孤立点)时取等号。

该不等式等价地可写成以下形式：

$t\left(G\right)\ge \frac{1}{3}\lambda \left(G\right)\left({\lambda }^2\left(G\right)-m\right),$

$m\ge {\lambda }^2\left(G\right)-\frac{3t\left(G\right)}{\lambda \left(G\right)}.$

定理2.3：([7])设$G$ 为一张具有$n$ 个顶点的图。若

$\lambda \left(G\right)\ge \lambda \left(T_{n,2}\right),$

则除非$G$ 为完全二部图，否则$t\left(G\right)\ge \lfloor \frac{n}{2}\rfloor -1$ 。

定义2.4：称图$G$ 是$\epsilon$ -边距离二部($\epsilon$ -far from bipartite)，其中$\epsilon$ 为非负数，若至少需要删除$\epsilon$ 条边才能使$G$ 变为二部图；等价地，对任意顶点划分$V\left(G\right)=S\cup T$ ，都有

$e\left(S\right)+e\left(T\right)\ge \epsilon .$

下面给出一个与二部图逼近相关的三角形下界定理。

定理2.5：([8])设$G$ 为一个含有$n$ 个点、$m$ 条边的图。若$G$ 是$\epsilon$ -边距离二部，则

$t\left(G\right)\ge \frac{n}{6}\left(m+\epsilon -\frac{n^2}{4}\right).$

推论2.6：设$G$ 为$n$ 阶简单图，且$e\left(G\right)=\lfloor \frac{n^2}{4}\rfloor -q\left(q\ge 0\right)$ 。若$t\left(G\right)\le kn\left(k>0\right)$ ，则$G$ 不是$\left(6k+q+1\right)$ -边距离二部。等价地，存在一个划分$V\left(G\right)=S\cup T$ 使得

$e\left(S\right)+e\left(T\right)\le 6k+q.$

从而在该划分下，有

$e\left(S,T\right)=e\left(G\right)-e\left(S\right)-e\left(T\right)\ge \lfloor \frac{n^2}{4}\rfloor -2q-6k,$

因此，$G$ 含有一个边数至少为$e\left(S,T\right)$ 的二部子图。

证明

以下采用反证法，假设$G$ 是$\left(6k+q+1\right)$ -边距离二部。由定理2.5，

$t\left(G\right)\ge \frac{n}{6}\left(e\left(G\right)+\left(6k+q+1\right)-\frac{n^2}{4}\right).$

将$e\left(G\right)=\lfloor \frac{n^2}{4}\rfloor -q$ 代入，得

$t\left(G\right)\ge \frac{n}{6}\left(\lfloor \frac{n^2}{4}\rfloor -q+6k+q+1-\frac{n^2}{4}\right)=\frac{n}{6}\left(6k+1-\left(\frac{n^2}{4}-\lfloor \frac{n^2}{4}\rfloor \right)\right).$

注意到$0\le \frac{n^2}{4}-\lfloor \frac{n^2}{4}\rfloor <1$ ，故括号内严格大于$6k$ ，从而

$t\left(G\right)>\frac{n}{6}\cdot 6k=kn,$

与假设$t\left(G\right)\le kn$ 矛盾。故$G$ 不是$\left(6k+q+1\right)$ -边距离二部。$\square$

引理2.7：([9])设$n$ 足够大，且$G$ 是$K_{s,t}^{+2}$ 的子图，其中

$\lfloor \frac{n}{2}\rfloor -2\le s\le \lceil \frac{n}{2}\rceil +2,t=n-s.$

若$G$ 至多含$n-4$ 个三角形，则$\lambda \left(G\right)<\lambda \left(T_{n,2}\right)$ 。

引理2.8：([9])设$n$ 足够大，且$G$ 是$K_{s,t}^{++}$ 的子图，其中$\lfloor \frac{n}{2}\rfloor -2\le s\le \lceil \frac{n}{2}\rceil +2$ ，$t=n-s$ 。若$G$ 至多含$n-4$ 个三角形，则$\lambda \left(G\right)<\lambda \left(T_{n,2}\right)$ 。

说明：引理2.7~2.8的证明依赖对有限多个“删边图”的谱半径进行直接计算与比较。本文第4节仅需其结论用于导出最终矛盾，因此在此不重复计算细节。

3. 主要结果

本节给出本文的主要结果。我们在谱Turán临界条件下，研究当图不具有最极端的三角形分布结构时，其三角形数量所满足的稳定性下界。

定理3.1：设$G$ 为一张具有$n$ 个顶点的简单图(n足够大)，其谱半径满足$\lambda \left(G\right)\ge \lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)$ 并且$G$ 至少含一个三角形(即$t\left(G\right)\ge 1$ )。若图$G$ 中不存在一个顶点同时属于所有三角形，则图$G$ 中三角形的个数满足

$t\left(G\right)\ge n-c,$

其中$c\ge 2$ ，是与$n$ 无关的常数。

定理3.1表明，在谱Turán临界条件下，只要图的三角形分布不完全集中在某一个顶点附近，其三角形数量便具有线性下界。这一结论可以视为Ning-Zhai有关三角形的谱结果的一个稳定性补充。

本节仅陈述主要结果，其证明将在下一节中给出。

4. 定理证明

本节给出定理3.1的证明。证明思路主要是：先由谱三角形计数不等式推出边数下界，再用“边二部逼近”得到近似二部结构，刻画二部图的点集取值范围和边集连接情况，最后比较极值图的谱半径导出矛盾。

设$G$ 为一张$n$ 阶简单图，满足$\lambda \left(G\right)\ge \lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)\ge \lambda \left(T_{n,2}\right)$ ，且$G$ 至少含一个三角形，并且不存在一个顶点同时属于所有三角形。我们将证明当$n$ 足够大时，$t\left(G\right)\ge n-2$ 。

为此，采用反证法，设$t\left(G\right)\le n-3$ 。注意到$\lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)\ge \frac{n}{2}+\frac{7}{4n}+\frac{2}{n^2}+O\left(\frac{1}{n^3}\right)$ ，于是当$n$ 足够大时有

$\lambda \left(G\right)>\frac{n}{2}+\frac{3}{2n}.$ (4.1)

由引理2.2的等价形式得

$m\ge {\lambda }^2\left(G\right)-\frac{3t\left(G\right)}{\lambda \left(G\right)},$

并结合(4.1)得到

$e\left(G\right)\ge {\lambda }^2\left(G\right)-\frac{3t\left(G\right)}{\lambda \left(G\right)}>{\lambda }^2\left(G\right)-\frac{6t\left(G\right)}{n-1}.$

再由${\lambda }^2\left(G\right)\ge {\lambda }^2\left(T_{n,2}\right)=\lfloor \frac{n^2}{4}\rfloor$ 与$t\left(G\right)\le n-3$ 得

$e\left(G\right)\ge \lfloor \frac{n^2}{4}\rfloor -\frac{6\left(n-3\right)}{n-1}.$

由于$e\left(G\right)$ 为整数，推出

$e\left(G\right)\ge \lfloor \frac{n^2}{4}\rfloor -5.$ (4.2)

接下来利用二部图逼近思想证明：$G$ 非常接近二部图。

引理4.1：存在一个划分$V\left(G\right)=S\cup T$ ，使得

$e\left(S\right)+e\left(T\right)<12,$

并且

$e\left(S,T\right)\ge \lfloor \frac{n^2}{4}\rfloor -16,\frac{n}{2}-4\le \left|S\right|,\left|T\right|\le \frac{n}{2}+4.$

证明：由不等式(4.2)，可写

$e\left(G\right)=\lfloor \frac{n^2}{4}\rfloor -q其中0\le q\le 5.$

已知$t\left(G\right)\le n-3$ ，取$k=1$ ，应用推论2.6可知，若$G$ 是$\left(6k+q+1\right)$ -边距离二部，则必有$t\left(G\right)>n$ ，与假设矛盾。由于$6k+q+1\le 12$ ，可推出$G$ 不是12-边距离二部。因此，存在划分$V\left(G\right)=S\cup T$ 使得

$e\left(S\right)+e\left(T\right)<12.$

于是

$e\left(S,T\right)=e\left(G\right)-e\left(S\right)-e\left(T\right)\ge e\left(G\right)-11\ge \lfloor \frac{n^2}{4}\rfloor -16.$

最后，由$e\left(S,T\right)\le \left|S\right|\left|T\right|$ 且$\left|S\right|+\left|T\right|=n$ ，结合AM-GM不等式即可推出

$\frac{n}{2}-4\le \left|S\right|,\left|T\right|\le \frac{n}{2}+4.$

证毕。$\square$

引理4.2：在引理4.1的划分$V\left(G\right)=S\cup T$ 下，有

$e\left(S\right)+e\left(T\right)=2,$

并且$G\left[S\right]\cup G\left[T\right]$ 中的两条在同一部集中的边相互独立。

证明：记$s:=e\left(S\right)+e\left(T\right)$ 。由于$G$ 至少含有一个三角形，显然$s\ge 1$ 。

1) $s\ne 1$ 。

假设$e\left(S\right)=1$ ，$e\left(T\right)=0,$ 即$G\left[S\right]$ 仅有一条边$uv$ 。注意到若$G$ 存在三角形，则该三角形必含$uv$ 作为三角形的一条边，因此所有三角形都包含边$uv$ 。于是顶点$u$ (或$v$ )属于所有三角形，与“不存在一个顶点同时属于所有三角形”矛盾。故$e\left(S\right)+e\left(T\right)\ne 1$ 。

2) $s\le 2$ 。

设同部边集合为

$M:=E\left(G\left[S\right]\right)\cup E\left(G\left[T\right]\right),\left|M\right|=s.$

对任意同部边$xy\in M$ ，定义

$c\left(xy\right):=\{\begin{array}{ll}\left|N_T\left(x\right)\cap N_T\left(y\right)\right|,\hfill & xy\subseteq S,\hfill \\ \left|N_S\left(x\right)\cap N_S\left(y\right)\right|,\hfill & xy\subseteq T.\hfill \end{array}$

则包含边$xy$ 的三角形数恰为$c\left(xy\right)$ ，从而

$t\left(G\right)={\displaystyle \sum }_{xy\in M}c\left(xy\right).$

由引理4.1，跨边数满足

$e\left(S,T\right)\ge \lfloor \frac{n^2}{4}\rfloor -16,$

且$\left|S\right|,\left|T\right|=\frac{n}{2}\pm O\left(1\right)$ 。这意味着除常数个顶点外，任一顶点在对侧均有线性数量的邻居。具体地，对任意同部边$xy\subseteq S$ ，有

$c\left(xy\right)\ge d_T\left(x\right)+d_T\left(y\right)-\left|T\right|\ge \left|T\right|-O\left(1\right)=\frac{n}{2}-O\left(1\right).$

于是

$t\left(G\right)\ge s\left(\frac{n}{2}-O\left(1\right)\right).$

当$s\ge 3$ 且$n$ 足够大时，上式严格大于$n-3$ ，与假设矛盾。综上，只能有$s=2$ ，即$e\left(S\right)+e\left(T\right)=2$ 。

最后证明两条在同一部集的边相互独立。若两条在同一侧的边有公共顶点$x$ ，则任何三角形都必须含这两条边，因此$x$ 属于所有三角形，矛盾，因此两条同部边必须相互独立。证毕。$\square$

引理4.3：仍在上述划分$V\left(G\right)=S\cup T$ 下，有

$e\left(S,T\right)\ge \lfloor \frac{n^2}{4}\rfloor -7,\lfloor \frac{n}{2}\rfloor -2\le \left|S\right|,\left|T\right|\le \lceil \frac{n}{2}\rceil +2.$

证明：由引理4.2得$e\left(S\right)+e\left(T\right)=2$ ，结合(4.2)得

$e\left(S,T\right)=e\left(G\right)-e\left(S\right)-e\left(T\right)\ge \lfloor \frac{n^2}{4}\rfloor -5-2=\lfloor \frac{n^2}{4}\rfloor -7.$

又因$e\left(S,T\right)\le \left|S\right|\left|T\right|$ 且$\left|S\right|+\left|T\right|=n$ ，当$\left|S\right|$ 与$\frac{n}{2}$ 的差值超过2时，则$\left|S\right|\left|T\right|\le \lfloor \frac{n^2}{4}\rfloor -8$ ，与上述不等式矛盾。故结论成立。$\square$

由引理4.2可知，在划分$S\cup T$ 下，两个点集中恰有两条且相互独立的边，因此(交换$S,T$ 得到的研究过程是等价的)只有两种可能：

情况1：两条边都在同一侧(例如$e\left(S\right)=2,e\left(T\right)=0$ )，此时$G$ 是某个$K_{s,t}^{+2}$ 的子图；

情况2：两条边分别位于两侧(即$e\left(S\right)=e\left(T\right)=1$ )，此时$G$ 是某个$K_{s,t}^{++}$ 的子图。

结合引理4.3，可知$\lfloor \frac{n}{2}\rfloor -2\le s\le \lceil \frac{n}{2}\rceil +2,\left(s=\left|S\right|,t=n-s\right)$ 。如果$t\left(G\right)\ge n-4$ ，分别应用引理2.7与引理2.8，可得$\lambda \left(G\right)<\lambda \left(T_{n,2}\right)<\lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)$ ，即与假设矛盾。因此为了证明假设不成立，接下来还需要证明当$t\left(G\right)=n-3$ 时，也能推出矛盾。

引理4.4：设$n$ 足够大，且$G\subseteq K_{s,t}^{+2}$ ，其中

$\lfloor \frac{n}{2}\rfloor -2\le s\le \lceil \frac{n}{2}\rceil +2,t=n-s.$

若$t\left(G\right)=n-3$ ，并且图中不存在一个顶点同时属于所有三角形，则$\lambda \left(G\right)<\lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)$ 。

证明：沿用引理4.3中的划分$V\left(G\right)=S\cup T$ ，其中$e\left(S\right)=2,e\left(T\right)=0$ ，并记$\left|S\right|=s,\left|T\right|=t$ ，则$s+t=n$ 。不妨设$S$ 中含有两条独立边$x_1{y}_1$ 与$x_2{y}_2$ 。令

$c_i:=\left|N_T\left(x_i\right)\cap N_T\left(y_i\right)\right|,i=1,2.$

则每个三角形必包含$x_1{y}_1$ 或$x_2{y}_2$ ，从而$t\left(G\right)=c_1+c_2$ 。考虑$S$ 和$T$ 之间边全连接的图：以$K_{s,t}$ 为底图并在$S$ 内加入两条独立边$x_1{y}_1,x_2{y}_2$ 。此时有$c_1=c_2=t$ ，从而$t\left(K_{s,t}^{+2}\right)=2t$ 。由假设$t\left(G\right)=n-3$ ，定义相对于上述$K_{s,t}^{+2}$ 需要减少的三角形数

$\text{Δ}\left(s\right):=t\left(K_{s,t}^{+2}\right)-t\left(G\right)=2t-\left(n-3\right).$

1) 若$\text{Δ}\left(s\right)<0$ ，则$2t<n-3$ 。由于删去$S$ 和$T$ 之间的连边会减少三角形的个数，故当$\text{Δ}\left(s\right)<0$ 时，不存在满足$t\left(G\right)=n-3$ 的图$G\subseteq K_{s,t}^{+2}$ 。下文仅需考虑$\text{Δ}\left(s\right)\ge 0$ 的情形。

2) 若$\text{Δ}\left(s\right)=0$ ，则已经满足$t\left(K_{s,t}^{+2}\right)=n-3$ 。注意到在保持边$x_1{y}_1,x_2{y}_2$ 不变的前提下，删去两个点集之间的连边都会严格降低谱半径，且三角形的个数也不会增加。因此，在$\text{Δ}\left(s\right)=0$ 的情形下，为了在满足

三角形约束的前提下使谱半径尽可能大，$S$ 与$T$ 之间必须全连。并且由于$\lfloor \frac{n}{2}\rfloor -2\le s\le \lceil \frac{n}{2}\rceil +2$ ，且$2t=n-3$ ，可得到唯一满足条件的图$H$ ，此时$H\cong G$ 。

3) 若$\text{Δ}\left(s\right)>0$ ，则必须通过删去$S$ 和$T$ 之间的部分连边使三角形数减少$\text{Δ}\left(s\right)$ 。进一步地，删去的连边必须以集合$\left\{x_1,y_1,x_2,y_2\right\}$ 中的某个顶点为端点；否则$c_1$ 与$c_2$ 均保持不变，从而三角形总数不变，矛盾。

由于$\lfloor \frac{n}{2}\rfloor -2\le s\le \lceil \frac{n}{2}\rceil +2$ 且$t=n-s$ ，故$\text{Δ}\left(s\right)=t-s+3$ 仅取有限多个固定整数值；同时要使三角形数减少

$\text{Δ}\left(s\right)$ ，所需删去的边数也是有限个固定的整数值。于是，在同构意义下，$S$ 与$T$ 之间连边的删减方式仅有有限多个，从而可得到有限个满足条件的图$H$ 。

综上，无论$\text{Δ}\left(s\right)=0$ 或$\text{Δ}\left(s\right)>0$ ，在给定$s,t$ 的条件下都只会得到有限个代表图$H$ 。对每一类代表图$H$ ，只需利用计算机得到图$H$ 的特征多项式，此时谱半径最大的特征方程是

$\begin{array}{l}{\lambda }^5-{\lambda }^4+\left(\Delta -st-1\right){\lambda }^3+\left(\Delta +st-4t+1\right){\lambda }^2+\left(-{\Delta }^{2}s+{\Delta }^2+\Delta st-\Delta t-2\Delta +st\right)\lambda \\ +\left({\Delta }^{2}s-3{\Delta }^2-\Delta st+3\Delta t-st+4t\right)=0\end{array}$

由上述特征方程对最大实根作渐近展开，可得最大的谱半径为

$\lambda \left(H\right)=\frac{n}{2}-\frac{1}{n}+o\left(\frac{1}{n^2}\right)$

显然，当$n$ 足够大时，有

$\lambda \left(H\right)<\lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right),$

由于子图的谱半径单调不增，任意$G\subseteq H$ 都满足$\lambda \left(G\right)\le \lambda \left(H\right)$ ，与谱半径条件矛盾。引理得证。$\square$

引理4.5：设$n$ 足够大，且$G\subseteq K_{s,t}^{++}$ ，其中

$\lfloor \frac{n}{2}\rfloor -2\le s\le \lceil \frac{n}{2}\rceil +2,t=n-s.$

若$t\left(G\right)=n-3$ ，并且图中不存在一个顶点同时属于所有三角形，则$\lambda \left(G\right)<\lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)$ 。

证明：沿用引理4.3中的划分$V\left(G\right)=S\cup T$ ，其中$e\left(S\right)=1,e\left(T\right)=1$ ，并记$\left|S\right|=s,\left|T\right|=t$ ，故$s+t=n$ 。设$S$ 内的独立边为$x_1{y}_1$ ，$T$ 内独立边为$x_2{y}_2$ 。令

$c_1:=\left|N_T\left(x_1\right)\cap N_T\left(y_1\right)\right|,c_2:=\left|N_S\left(x_2\right)\cap N_S\left(y_2\right)\right|.$

由于$S$ 与$T$ 内各只有一条独立边，图中任一三角形必包含边$x_1{y}_1$ 或$x_2{y}_2$ ，因此

$t\left(G\right)=c_1+c_2.$

考虑$S$ 和$T$ 之间边全连接的图：以完全二部图$K_{s,t}$ 为底图，在$S$ 内加入边$x_1{y}_1$ ，在$T$ 内加入边$x_2{y}_2$ 。此时$N_T\left(x_1\right)=N_T\left(y_1\right)=T$ ，$N_S\left(x_2\right)=N_S\left(y_2\right)=S$ ，从而$c_1=t,c_2=s$ ，并有$t\left(K_{s,t}^{++}\right)=s+t=n$ 。由假设$t\left(G\right)=n-3$ ，可知相对于上述图，三角形数需要减少3个。因此，为了得到$t\left(G\right)=n-3$ ，必须通过删去$S$ 与$T$ 之间的3条连边使三角形数恰减少3。注意到删去任意跨边都不会增加$c_1$ 或$c_2$ ，因此不会增加三角形总数。进一步地，删去的连边必须以集合$\left\{x_1,y_1,x_2,y_2\right\}$ 中的某个顶点为端点；否则$c_1$ 与$c_2$ 均保持不变，从而三角形总数不变，矛盾。由于需要减少的三角形数为3，且相关的端点集合是固定的四个顶点，

上述连边删减方式在同构意义下仅有有限多个。于是，在满足$\lfloor \frac{n}{2}\rfloor -2\le s\le \lceil \frac{n}{2}\rceil +2$ 且$t=n-s$ 的条件下，仅能得到有限个满足$t\left(H\right)=n-3$ 且“不存在一个顶点同时属于所有三角形”的代表图$H$ 。

对每一类代表图$H$ ，只需利用计算机得到图$H$ 的特征多项式，此时谱半径最大的特征方程是

${\lambda }^6-st{\lambda }^4-2\left(s+t-3\right){\lambda }^3+\left(4st-4s-6t+2\right){\lambda }^2+2\left(s+t-5\right)\lambda -\left(2st-3s-5t+7\right)=0$

由上述特征方程对最大实根作渐近展开，可得最大的谱半径为

$\lambda \left(H\right)=\frac{n}{2}+\frac{8}{n^2}+O\left(\frac{1}{n^3}\right)$

显然，当$n$ 足够大时，有

$\lambda \left(H\right)<\lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right),$

由于谱半径对子图单调不增，任意$G\subseteq H$ 都满足$\lambda \left(G\right)\le \lambda \left(H\right)$ ，与谱半径条件矛盾。引理得证。$\square$

综上所述，结合引理4.4和引理4.5可知，当$t\left(G\right)=n-3$ 时，在定理3.1的全部假设条件下必有$\lambda \left(G\right)<\lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)$ ，这与$\lambda \left(G\right)\ge \lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)$ 矛盾。因此，当$n$ 足够大时，$t\left(G\right)\ge n-2$ 。更一般地，可得存在一个与$n$ 无关的常数$c\ge 2$ ，使得

$t\left(G\right)\ge n-c.$

定理3.1得证。$\square$

5. 结论

本文在谱Turán临界条件下研究了图中三角形数量的稳定性问题。具体而言，我们证明：当一个$n$ 阶简单图$G$ 的谱半径满足$\lambda \left(G\right)\ge \lambda \left(K_{\lceil \frac{n}{2}\rceil ,\lfloor \frac{n}{2}\rfloor }^{+1}\right)$ ，且图中不存在一个顶点同时属于所有三角形时，$G$ 中的三

角形数量必然具有线性下界，即存在与$n$ 无关的常数$c\ge 2$ ，使得$t\left(G\right)\ge n-c$ 。该结果表明，在谱Turán临界情形下，只要三角形的分布未完全集中于单个顶点，整个图中便会强制产生线性数量的三角形，从而体现出谱Turán极值结构的稳定性。这一结论可视为对已有谱Turán结果的一种稳定性补充。在方法上，本文将谱三角形计数问题与二部图结构逼近思想相结合，通过分析近似二部图中点集的连边分布，并结合谱半径的比较导出矛盾。这种“谱不等式 + 结构近似”的策略在研究谱极值问题的稳定性方面具有一定的通用性。

未来的研究可以从多个方向展开。特别地，可以考虑将本文的分析推广至更一般的完全图或圈的计数问题，研究谱Turán临界条件下更复杂子图的稳定性现象。此外，对线性下界中常数的取值最优性也值得进一步研究。