海默斯韧性猜想的证明

《European Journal of Combinatorics》：A proof of Haemers’s toughness conjecture

　　

# 摘要

非完全图 $G=(V,E)$ 的坚韧性定义为 $t(G)=\min\frac{|S|}{c(G-S)}: S\subseteq V(G) \text{ 且 } c(G-S)\geq 2$，其中 $c(G-S)$ 是 $G-S$ 的连通分支数。约定 $t(K_n)=+\infty$。Haemers（2020）猜想，对于每个阶数 $n\geq 2$ 的连通图 $G$，若其最小度数为 $\delta$，则 $t(G)\geq\frac{\mu_2}{\mu_n-\delta}$，其中 $\mu_n$ 和 $\mu_2$ 分别是 $G$ 的最大和次小的Laplacian特征值。我们独立地证明了该猜想，并讨论了其紧性以及若干推论。

## 1. 引言

全文中，所有图均为有限、简单、无向图。设 $G=(V,E)$ 是顶点集为 $V(G)$、边集为 $E(G)$ 的图。其阶数为 $|V(G)|$，记为 $n$。对于 $v\in V(G)$，设 $d_G(v)$ 为 $v$ 的度数。$G$ 的最大度和最小度分别记为 $\Delta(G)$ 和 $\delta(G)$（或简记为 $\Delta$ 和 $\delta$）。若 $\Delta(G)=\delta(G)=d$，则称图 $G$ 为 $d$-正则图。对于子集 $X\subseteq V(G)$，用 $G-X$ 表示 $G$ 由 $V(G)\setminus X$ 导出的子图。对于 $X,Y\subseteq V(G)$，用 $E(X,Y)$ 表示一端在 $X$ 中、另一端在 $Y$ 中的边的集合，令 $e(X,Y)=|E(X,Y)|$。

设 $L(G)=D(G)-A(G)$ 为图 $G$ 的Laplacian矩阵，其中 $A(G)$ 和 $D(G)$ 分别为 $G$ 的邻接矩阵和对角度数矩阵。$A(G)$ 和 $L(G)$ 的特征值分别称为 $G$ 的特征值和Laplacian特征值，记为 $\lambda_1(G)\geq\lambda_2(G)\geq\cdots\geq\lambda_n(G)$ 和 $\mu_n(G)\geq\mu_{n-1}(G)\geq\cdots\geq\mu_1(G)$（或简记为 $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_n$ 和 $\mu_n\geq\mu_{n-1}\geq\cdots\geq\mu_1$）。对于阶数为 $n$ 的 $d$-正则图 $G$，有 $L(G)=dI-A(G)$，因此 $\mu_i=d-\lambda_i$，$i=1,\ldots,n$。注意 $L(G)$ 是半正定的，且 $\mu_1(G)=0$。次小的Laplacian特征值 $\mu_2(G)$ 称为 $G$ 的代数连通度。已知 $\mu_2(G)=0$ 当且仅当 $G$ 不连通。对于每个阶数 $n\geq 2$ 的连通非完全图 $G$，$\mu_2(G)\leq\kappa(G)\leq\delta(G)$ [11]，其中 $\kappa(G)$ 是 $G$ 的顶点连通度。

非完全图 $G$ 的坚韧性 $t(G)$ 在文献[7]中定义为
$$t(G)=\min\frac{|S|}{c(G-S)}: S\subseteq V(G) \text{ 且 } c(G-S)\geq 2,$$
其中最小值取遍所有真子集 $S\subseteq V(G)$，$c(G-S)$ 是 $G-S$ 的连通分支数。约定完全图的坚韧性为 $+\infty$。图的坚韧性与许多图性质密切相关，包括Hamilton性、Pancyclic性、因子和支撑树。关于坚韧性的进一步结果请参阅综述[2]。

在过去几十年中，图的坚韧性与其相关特征值之间关系的研究受到了越来越多的关注，参见[4]、[5]、[6]、[9]、[16]。正则图的坚韧性从其邻接矩阵特征值出发首先由Alon [1] 研究，他证明对于任何连通 $d$-正则图 $G$，$t(G)>\frac{1}{3d}+\frac{2d\lambda+\lambda^2-1}{3d}$，其中 $\lambda\coloneqq\max\{|\lambda_2|,|\lambda_n|\}$。同时，Brouwer [3] 独立地建立了略优的界 $t(G)>\frac{d}{\lambda}-2$。此外，Brouwer [3] 进一步猜想 $t(G)\geq\frac{d}{\lambda}-1$，该猜想由Gu [12] 证实。

**定理1.1 [12]** 设 $G$ 是连通 $d$-正则图。则 $t(G)\geq\frac{d}{\lambda}-1$。

最近，Haemers [15] 提出了如下猜想。

**猜想1.2 [15]** 设 $G$ 是阶数 $n\geq 2$、最小度数为 $\delta$ 的连通图。则 $t(G)\geq\frac{\mu_2}{\mu_n-\delta}$。

**注1.1** 对于 $d$-正则图 $G$，由于 $\mu_2=d-\lambda_2$ 且 $\mu_n=d-\lambda_n$，猜想1.2中的界变为
$$t(G)\geq\frac{\mu_2}{\mu_n-d}=\frac{d-\lambda_2}{-\lambda_n}=\begin{cases}d-\lambda_2\lambda,&\text{若 }\lambda=-\lambda_n\\d-\frac{\lambda-\lambda_n}{\lambda},&\text{若 }\lambda=\lambda_2\geq d-\lambda\end{cases}$$
这比定理1.1中Gu的界更强。

Gu和Haemers [13] 在猜想1.2的方向上证明了以下结果，但由于 $\mu_2\leq\delta$ 且 $\mu_n\leq n$，这些结果较弱。

**定理1.3 [13]** 设 $G$ 是阶数 $n\geq 2$ 的连通非完全图。则 $t(G)\geq\frac{\mu_2}{\mu_n-\mu_2}$ 且 $t(G)\geq\frac{\mu_n}{\mu_2}\cdot\frac{n(\mu_n-\delta)}{n-\delta}$。

在本文中，我们独立地证明了猜想1.2。

**定理1.4** 设 $G$ 是阶数 $n\geq 2$、最小度数为 $\delta$ 且Laplacian特征值为 $0=\mu_1<\mu_2\leq\cdots\leq\mu_n$ 的连通图。则 $t(G)\geq\frac{\mu_2}{\mu_n-\delta}$。

**注1.2** Greaves和Zhu [10] 独立地证明了Haemers的猜想。他们的方法与我们的方法的比较见第4节末尾。

对于每个阶数 $n\geq 2$ 的连通非完全图 $G$，有 $\mu_2\leq\delta$ 且 $\mu_n\leq n$。因此，定理1.4包含了Gu和Haemers的两个界，因为
$$\frac{\mu_2}{\mu_n-\delta}\geq\frac{\mu_2}{\mu_n-\mu_2}\quad\text{且}\quad\frac{\mu_2}{\mu_n-\delta}\geq\frac{\mu_n}{\mu_2}\cdot\frac{n(\mu_n-\delta)}{n-\delta}.$$

本文其余部分安排如下。第2节建立了证明中使用的加权星形比较和Laplacian割压缩。第3节给出定理1.4的证明。第4节记录若干推论并讨论紧性和等号条件。

## 2. 加权星形矩阵和Laplacian割压缩

本节建立证明的两个主要要素：加权星形矩阵的比较定理及其在关联于顶点割的对称化Laplacian压缩中的应用。对于阶数为 $n$ 的图 $G$ 和向量 $x\in\mathbb{R}^n$，Laplacian二次型为 $x^TL(G)x=\sum_{uv\in E(G)}(x_u-x_v)^2$。

我们使用Haemers [14] 的以下特征值交错定理。对于 $1\leq q\leq n$，序列 $\beta_1\leq\beta_2\leq\cdots\leq\beta_q$ 被称为交错序列 $\rho_1\leq\rho_2\leq\cdots\leq\rho_n$，若 $\rho_i\leq\beta_i\leq\rho_{n-q+i}$，$i=1,2,\ldots,q$。

**引理2.1 [14]** 设 $U$ 是 $n\times q$ 实矩阵且 $U^TU=I_q$，设 $A$ 是对称 $n\times n$ 矩阵，特征值为 $\rho_1\leq\rho_2\leq\cdots\leq\rho_n$。定义 $B=U^TAU$，设 $B$ 的特征值为 $\beta_1\leq\beta_2\leq\cdots\leq\beta_q$。则 $B$ 的特征值交错于 $A$ 的特征值。特别地，若 $B$ 是 $A$ 的主子矩阵，则 $B$ 的特征值交错于 $A$ 的特征值。

### 2.1 加权星形矩阵

固定整数 $c\geq 2$。我们需要以下阶数为 $c+1$ 的加权星形矩阵：
$$M=\begin{pmatrix}\frac{1}{s}\sum_{i=1}^c h_i r_i & -\frac{r_1h_1}{s} & -\frac{r_2h_2}{s} & \cdots & -\frac{r_ch_c}{s}\\-\frac{r_1h_1}{s} & r_1 & 0 & \cdots & 0\\-\frac{r_2h_2}{s} & 0 & r_2 & \cdots & 0\\\vdots & \vdots & \vdots & \ddots & \vdots\\-\frac{r_ch_c}{s} & 0 & 0 & \cdots & r_c\end{pmatrix},\tag{1}$$
其中 $s>0$ 且 $h_i,r_i>0$ 对所有 $i=1,\ldots,c$。称第一个坐标为中心，其余坐标为叶。

注意对于任意 $y^T=(y_0,y_1,\ldots,y_c)$，有
$$y^TMy=\sum_{i=1}^c h_ir_i\left(\frac{y_0}{s}-\frac{y_i}{h_i}\right)^2\geq 0.\tag{2}$$
因此 $M$ 是半正定的。此外，(2)中等号成立当且仅当 $\frac{y_0}{s}=\frac{y_i}{h_i}$ 对 $i=1,\ldots,c$ 成立。故 $M$ 的核为一维，由 $(s,h_1,\ldots,h_c)^T$ 张成。将 $M$ 的特征值写为 $0=\alpha_0<\alpha_1\leq\cdots\leq\alpha_c$。

**引理2.2** 设 $M$ 为(1)中的矩阵。则 $\alpha_c>r_i$ 对每个 $i=1,\ldots,c$ 成立。此外，$M$ 的每个非零特征值 $\alpha$（$\alpha\notin\{r_1,\ldots,r_c\}$）满足
$$\sum_{i=1}^c\frac{h_ir_i}{\alpha-r_i}=s.\tag{3}$$
反之，(3)的每个不等于任何 $r_i$ 的正解都是 $M$ 的特征值。

*证明* 对每个 $i=1,\ldots,c$，$M$ 在中心与第 $i$ 个叶上的主子矩阵为
$$M_{0i}=\begin{pmatrix}\frac{1}{s}\sum_{j=1}^c h_jr_j & -\frac{r_ih_i}{s}\\-\frac{r_ih_i}{s} & r_i\end{pmatrix}.$$
则 $M_{0i}$ 的最大特征值为
$$\lambda_{\max}(M_{0i})=\frac{a+r_i+\sqrt{(a-r_i)^2+4b^2}}{2},$$
其中 $a=\frac{1}{s}\sum_{j=1}^c h_jr_j$，$b=-\frac{r_ih_i}{s}\neq 0$。显然 $(a-r_i)^2+4b^2>|a-r_i|$，因为 $b\neq 0$。因此
$$\lambda_{\max}(M_{0i})>\frac{a+r_i+|a-r_i|}{2}=\max\{a,r_i\}\geq r_i.$$
由引理2.1，$\alpha_c\geq\lambda_{\max}(M_{0i})>r_i$。由于 $i$ 是任意的，故 $\alpha_c>r_i$ 对所有 $i=1,\ldots,c$ 成立，结论得证。

设 $\alpha>0$ 是 $M$ 的特征值且 $\alpha\notin\{r_1,\ldots,r_c\}$，设 $y^T=(y_0,y_1,\ldots,y_c)$ 是 $\alpha$ 的特征向量。由 $My=\alpha y$ 的叶坐标得
$$-\frac{r_ih_i}{s}y_0+r_iy_i=\alpha y_i,$$
从而
$$y_i=-\frac{r_ih_i}{s(\alpha-r_i)}y_0.\tag{4}$$
若 $y_0=0$，则由(4)得 $y_i=0$ 对 $i=1,\ldots,c$，矛盾。故 $y_0\neq 0$。将(4)代入中心坐标方程 $\frac{1}{s}\sum_{i=1}^c h_ir_i y_0-\sum_{i=1}^c\frac{r_ih_i}{s}y_i=\alpha y_0$，得
$$\frac{1}{s}\sum_{i=1}^c h_ir_i+\frac{1}{s}\sum_{i=1}^c\frac{h_ir_i^2}{\alpha-r_i}=\alpha.$$
即
$$\sum_{i=1}^c h_ir_i\left(1+\frac{r_i}{\alpha-r_i}\right)=\frac{s\alpha}{1}.$$
从而
$$\alpha\sum_{i=1}^c\frac{h_ir_i}{\alpha-r_i}=s\alpha.$$
这恰好是(3)，因为 $\alpha>0$ 且 $\alpha\notin\{r_1,\ldots,r_c\}$。

反之，设正数 $\alpha\notin\{r_1,\ldots,r_c\}$ 满足(3)。取 $y_0=1$ 并由(4)定义 $y_i$。叶方程由构造成立，逆推前面的计算表明中心方程也成立。故 $\alpha$ 是 $M$ 的特征值。$\square$

以下引理给出了加权星形矩阵的关键比较估计：在其最大特征值满足一个简单上界的情况下，其第一个正特征值至多为 $s/c$。

**引理2.3** 设 $M$ 为(1)中的矩阵，特征值为 $0=\alpha_0<\alpha_1\leq\cdots\leq\alpha_c$。若
$$\alpha_c\leq r_i+h_i\tag{5}$$
对所有 $i=1,\ldots,c$ 成立，则 $\alpha_1\leq s/c$。

*证明* 由引理2.2，$\alpha_c>r_i$ 对 $i=1,\ldots,c$ 成立。故 $\alpha_c\notin\{r_1,\ldots,r_c\}$，且(3)对 $\alpha_c$ 成立。令 $w_i=\frac{h_ir_i}{\alpha_c-r_i}$，$i=1,\ldots,c$。则由引理2.2，
$$\sum_{i=1}^c w_i=s.\tag{6}$$
此外，由假设(5)，$\alpha_c-r_i\leq h_i$，即 $\frac{h_i}{\alpha_c-r_i}\geq 1$。因此
$$w_i=\frac{h_ir_i}{\alpha_c-r_i}\geq r_i\quad\text{对 }i=1,\ldots,c.\tag{7}$$
结合(6)得
$$\sum_{i=1}^c r_i\leq\sum_{i=1}^c w_i=s.\tag{8}$$

重排叶使得 $r_1\leq r_2\leq\cdots\leq r_c$。这不改变 $M$ 的特征值。我们先处理最小叶参数重复的情形。设 $r_1=r_j$ 对某个 $j\geq 2$。取 $p=1$，$q=j$，定义 $z\in\mathbb{R}^{c+1}$ 为 $z_0=0$，$z_p=h_q$，$z_q=-h_p$，$z_k=0$ 对 $k\notin\{0,p,q\}$。

对于两个非零叶坐标，$(Mz)_p=r_pz_p=r_1z_p$，$(Mz)_q=r_qz_q=r_1z_q$。所有其他叶坐标为零。在中心坐标，$(Mz)_0=-\frac{r_1h_p}{s}h_q+\frac{r_1h_q}{s}h_p=0$。因此 $Mz=r_1z$，故 $r_1>0$ 是 $M$ 的特征值。从而 $\alpha_1\leq r_1$。此外，由(8)，$cr_1\leq\sum_{i=1}^c r_i\leq s$，即 $r_1\leq s/c$。因此 $\alpha_1\leq r_1\leq s/c$。

余下考虑 $r_1r_2$ 且 $\xi\in(r_1,r_2)$，$\xi\neq\alpha_c$。由(9)，
$$\sum_{i=1}^c\frac{h_ir_i}{\xi-r_i}-s=(\alpha_c-\xi)F(\xi)=0.$$
即
$$\sum_{i=1}^c\frac{h_ir_i}{\xi-r_i}=s.$$
由引理2.2的反向，$\xi$ 是 $M$ 的正特征值。因此 $\alpha_1\leq\xi$。

若 $r_2\leq s/c$，则 $\alpha_1\leq\xis/c$。

结合(8)，$r_1s/c$，与(8)矛盾。

令 $y_1=\frac{s/c-r_1}{s/c}$，$y_i=\frac{r_i-s/c}{s/c}$ 对 $i=2,\ldots,c$。则 $y_i>0$ 对 $i=1,\ldots,c$，$r_1=(s/c)(1-y_1)$，$r_i=(s/c)(1+y_i)$ 对 $i=2,\ldots,c$。由(8)，
$$\frac{s}{c}(1-y_1)+\sum_{i=2}^c\frac{s}{c}(1+y_i)\leq s,$$
即
$$\frac{s}{c}-\frac{sy_1}{c}+\frac{s(c-1)}{c}+s\sum_{i=2}^c y_i\leq s.$$
从而
$$\sum_{i=2}^c y_i\leq y_1.\tag{10}$$
由于 $r_1>0$，$y_1<1$ 且 $\sum_{i=2}^c y_i>0$。故 $0<\sum_{i=2}^c y_i\leq y_1<1$。

现在估计 $F(s/c)$。由于 $s/c\in(r_1,r_2)$，
$$F(s/c)=\frac{w_1}{s/c-r_1}-\sum_{i=2}^c\frac{w_i}{r_i-s/c}.\tag{11}$$

对于正项部分，由(6)和(7)，
$$w_1=s-\sum_{i=2}^c w_i\leq s-\sum_{i=2}^c r_i=s-\sum_{i=2}^c\frac{s}{c}(1+y_i)=\frac{s}{c}\left(1-\sum_{i=2}^c y_i\right).\tag{12}$$

由于 $s/c-r_1=(s/c)y_1$，由(10)和(12)，
$$\frac{w_1}{s/c-r_1}\leq\frac{\frac{s}{c}(1-\sum_{i=2}^c y_i)}{\frac{s}{c}y_1}=\frac{1-\sum_{i=2}^c y_i}{y_1}\leq\frac{1-\sum_{i=2}^c y_i}{\sum_{i=2}^c y_i}.\tag{13}$$

对于负项部分，由(7)，
$$\sum_{i=2}^c\frac{w_i}{r_i-s/c}\geq\sum_{i=2}^c\frac{r_i}{r_i-s/c}=\sum_{i=2}^c\frac{\frac{s}{c}(1+y_i)}{\frac{s}{c}y_i}=\sum_{i=2}^c\frac{1+1}{y_i}\geq\sum_{i=2}^c\frac{1}{y_i}.\tag{14}$$

由Cauchy-Schwarz不等式，
$$\sum_{i=2}^c\frac{1}{y_i}\geq\frac{(c-1)^2}{\sum_{i=2}^c y_i}\geq\frac{1}{\sum_{i=2}^c y_i}.\tag{15}$$

由于 $0<\sum_{i=2}^c y_i<1$，
$$\frac{1}{\sum_{i=2}^c y_i}\geq\frac{1-\sum_{i=2}^c y_i}{\sum_{i=2}^c y_i}.\tag{16}$$

结合(14)、(15)和(16)，
$$\sum_{i=2}^c\frac{w_i}{r_i-s/c}\geq\frac{1-\sum_{i=2}^c y_i}{\sum_{i=2}^c y_i}.\tag{17}$$

将(13)和(17)代入(11)得 $F(s/c)\leq 0$。由于 $F$ 在 $(r_1,r_2)$ 上严格递减且 $F(\xi)=0$，不等式 $F(s/c)\leq 0$ 蕴含 $\xi\leq s/c$。又 $\alpha_1\leq\xi$，因此
$$\alpha_1\leq\xi\leq s/c,$$
结论得证。$\square$

我们还需要以下Laplacian最大特征值的下界。

**引理2.4 [11]** 若 $G$ 是阶数 $n\geq 2$ 的连通图，则 $\mu_n\geq\Delta+1$。

特别地，对于阶数 $n\geq 2$ 的每个连通图 $G$，$\mu_n\geq\Delta+1>\delta$，从而 $\mu_n-\delta>0$。

### 2.2 Laplacian割压缩

设 $G$ 是阶数为 $n$ 的连通非完全图，$S\subseteq V(G)$ 且 $c(G-S)\geq 2$。令 $s=|S|$，$c=c(G-S)$。设 $G_1,G_2,\ldots,G_c$ 是 $G-S$ 的连通分支，记 $n_i=|V(G_i)|$，$e_i=|E(V(G_i),S)|$，$i=1,2,\ldots,c$。由于 $G$ 连通，每个 $e_i>0$。

对于 $X\subseteq V(G)$，设 $\mathbf{1}_X$ 为 $X$ 的特征向量，$\mathbf{1}$ 为全1向量（维度明确时）。将 $G$ 的顶点集分拆为 $V(G)=S\cup V(G_1)\cup\cdots\cup V(G_c)$，令
$$u_0^T=\left(\underbrace{\frac{1}{\sqrt{s}},\ldots,\frac{1}{\sqrt{s}}}_{s},\underbrace{0,\ldots,0}_{n_1},\ldots,\underbrace{0,\ldots,0}_{n_c}\right)=\frac{\mathbf{1}_S^T}{\sqrt{s}},$$
$$u_1^T=\left(\underbrace{0,\ldots,0}_{s},\underbrace{\frac{1}{\sqrt{n_1}},\ldots,\frac{1}{\sqrt{n_1}}}_{n_1},\ldots,\underbrace{0,\ldots,0}_{n_c}\right)=\frac{\mathbf{1}_{V(G_1)}^T}{\sqrt{n_1}},$$
$$\vdots$$
$$u_c^T=\left(\underbrace{0,\ldots,0}_{s},\underbrace{0,\ldots,0}_{n_1},\ldots,\underbrace{\frac{1}{\sqrt{n_c}},\ldots,\frac{1}{\sqrt{n_c}}}_{n_c}\right)=\frac{\mathbf{1}_{V(G_c)}^T}{\sqrt{n_c}}.$$

令 $U=[u_0\; u_1\;\cdots\; u_c]$。则 $U^TU=I_{c+1}$。令 $L_S=U^TL(G)U$。

矩阵 $L_S$ 是 $L(G)$ 到各部分归一化特征向量张成的子空间的正交压缩；等价地，它是与分拆 $S,V(G_1),\ldots,V(G_c)$ 相关联的对称化商矩阵。

下面逐块计算 $L_S$ 的条目。

对于 $i,j\in\{1,\ldots,c\}$，若 $i\neq j$，则 $e(V(G_i),V(G_j))=0$，故 $u_i^TL(G)u_j=0$。

对于 $1\leq i\leq c$，只有 $E(V(G_i),S)$ 中的边对 $\mathbf{1}_{V(G_i)}^TL(G)\mathbf{1}_{V(G_i)}$ 有贡献。故
$$u_i^TL(G)u_i=\frac{\mathbf{1}_{V(G_i)}^TL(G)\mathbf{1}_{V(G_i)}}{n_i}=\frac{e_i}{n_i}.$$

对于 $S$，对 $\mathbf{1}_S^TL(G)\mathbf{1}_S$ 有贡献的只有 $E(S,V(G)\setminus S)$ 中的边。注意 $e(S,V(G)\setminus S)=\sum_{i=1}^c e_i$。因此
$$u_0^TL(G)u_0=\frac{\mathbf{1}_S^TL(G)\mathbf{1}_S}{s}=\frac{e(S,V(G)\setminus S)}{s}=\frac{\sum_{i=1}^c e_i}{s}.$$

最后，$E(S,V(G_i))$ 中的每条边对 $\mathbf{1}_S^TL(G)\mathbf{1}_{V(G_i)}$ 贡献 $-1$。因此
$$u_0^TL(G)u_i=\frac{\mathbf{1}_S^TL(G)\mathbf{1}_{V(G_i)}}{\sqrt{s}\sqrt{n_i}}=-\frac{e_i}{s\cdot n_i}\cdot\frac{\sqrt{s}\sqrt{n_i}}{\sqrt{s}\sqrt{n_i}}$$

更准确地说：
$$u_0^TL(G)u_i=-\frac{e_i}{\sqrt{s}\sqrt{n_i}}\quad\text{对 }i=1,\ldots,c.$$

因此
$$L_S=U^TL(G)U=\begin{pmatrix}\frac{\sum_{i=1}^c e_i}{s} & -\frac{e_1}{\sqrt{s}\sqrt{n_1}} & -\frac{e_2}{\sqrt{s}\sqrt{n_2}} & \cdots & -\frac{e_c}{\sqrt{s}\sqrt{n_c}}\\-\frac{e_1}{\sqrt{s}\sqrt{n_1}} & \frac{e_1}{n_1} & 0 & \cdots & 0\\-\frac{e_2}{\sqrt{s}\sqrt{n_2}} & 0 & \frac{e_2}{n_2} & \cdots & 0\\\vdots & \vdots & \vdots & \ddots & \vdots\\-\frac{e_c}{\sqrt{s}\sqrt{n_c}} & 0 & 0 & \cdots & \frac{e_c}{n_c}\end{pmatrix}.\tag{18}$$

由于对每个 $i=1,2,\ldots,c$，$\frac{e_i}{s\cdot n_i}=\frac{e_i}{n_i}\cdot\frac{1}{s}$，矩阵 $L_S$ 在(18)中与(1)中的加权星形矩阵一致，中心质量为 $s$，叶质量为 $n_1,\ldots,n_c$，叶参数为 $\frac{e_i}{n_i}$，$i=1,2,\ldots,c$。特别地，由(2)，$L_S$ 半正定且具有核维数为一。因此将 $L_S$ 的特征值记为 $0=\theta_0<\theta_1\leq\cdots\leq\theta_c$。

由引理2.1，$L_S$ 的特征值交错于 $L(G)$ 的特征值。特别地，我们使用以下两个不等式。

**引理2.5** $\mu_2\leq\theta_1$ 且 $\theta_c\leq\mu_n$。

为对 $L_S$ 的缩放副本应用引理2.3，我们需要以下对 $G-S$ 每个连通分支的局部比较。

**引理2.6** 对于 $G-S$ 的每个连通分支 $G_i$，
$$\frac{e_i}{n_i}+(\mu_n-\delta)(n_i-1)\geq\delta.\tag{19}$$
从而
$$\theta_c\leq\frac{e_i}{n_i}+(\mu_n-\delta)n_i\quad\text{对 }i=1,\ldots,c.\tag{20}$$

*证明* 对 $i=1,\ldots,c$，设 $L_i=L[G_i]$ 是 $L(G)$ 以 $V(G_i)$ 为指标的主子矩阵。等价地，$L_i=L(G_i)+D_i$，其中 $D_i$ 是对角矩阵，对应 $v\in V(G_i)$ 的对角元素为 $d_S(v)\coloneqq|N_G(v)\cap S|=e(\{v\},S)$。

若 $n_i=1$，设 $V(G_i)=\{v\}$，则 $v$ 的所有邻居均在 $S$ 中。故 $e_i=d_G(v)\geq\delta$，(19)成立。

现设 $n_i\geq 2$。令 $a_i^T=\left(\underbrace{\frac{1}{\sqrt{n_i}},\ldots,\frac{1}{\sqrt{n_i}}}_{n_i}\right)=\frac{\mathbf{1}_{n_i}^T}{\sqrt{n_i}}$。$a_i$ 处 $L_i$ 的Rayleigh商为
$$a_i^TL_ia_i=\frac{\mathbf{1}_{n_i}^TL_i\mathbf{1}_{n_i}}{n_i}=\frac{e_i}{n_i},\tag{21}$$
因为 $\mathbf{1}_{n_i}^TL(G_i)\mathbf{1}_{n_i}=0$ 且 $\mathbf{1}_{n_i}^TD_i\mathbf{1}_{n_i}=e_i$。另外，
$$\text{tr}(L_i)=\sum_{v\in V(G_i)}d_G(v)\geq\delta n_i.\tag{22}$$

将 $a_i$ 扩展为 $\mathbb{R}^{n_i}$ 的正交基 $a_i,b_1,\ldots,b_{n_i-1}$。$L_i$ 到 $a_i^\perp$ 的压缩的迹为
$$\sum_{j=1}^{n_i-1}b_j^TL_ib_j=\text{tr}(L_i)-a_i^TL_ia_i.$$
由(21)和(22)，此和至少为 $\delta n_i-\frac{e_i}{n_i}\cdot n_i=\delta n_i-e_i$（注意：$a_i^TL_ia_i=\frac{e_i}{n_i}$，$\text{tr}(L_i)\geq\delta n_i$，故 $\text{tr}(L_i)-a_i^TL_ia_i\geq\delta n_i-\frac{e_i}{n_i}$）。

因此 $\{b_j\}$ 上Rayleigh商的平均值至少为 $\frac{\delta n_i-e_i}{n_i-1}$。从而 $a_i^\perp$ 中存在单位向量其Rayleigh商至少达到此值，因此
$$\lambda_{\max}(L_i)\geq\frac{\delta n_i-e_i}{n_i-1}.\tag{23}$$

由于 $L_i$ 是 $L(G)$ 的主子矩阵，由引理2.1，$\lambda_{\max}(L_i)\leq\mu_n$。结合(23)，
$$\frac{\delta n_i-e_i}{n_i-1}\leq\mu_n.$$
即 $\delta n_i-e_i\leq(n_i-1)\mu_n$。从而
$$\delta\leq\frac{e_i}{n_i}+(n_i-1)(\mu_n-\delta),$$
(19)得证。

由(19)，$\mu_n\leq\frac{e_i}{n_i}+(\mu_n-\delta)n_i$ 对 $i=1,\ldots,c$。结合引理2.5，
$$\theta_c\leq\mu_n\leq\frac{e_i}{n_i}+(\mu_n-\delta)n_i\quad\text{对 }i=1,\ldots,c,$$
结论得证。$\square$

## 3. 定理1.4的证明

**定理1.4的证明** 若 $G=K_n$，则 $t(K_n)=+\infty$，断言显然成立。故可设 $G\neq K_n$。

设 $S\subseteq V(G)$ 为任意满足 $c(G-S)\geq 2$ 的顶点集。令 $s=|S|$，$c=c(G-S)$。使用第2节引入的记号。由于 $\mu_n-\delta>0$，考虑缩放矩阵 $\frac{1}{\mu_n-\delta}L_S$，其中 $L_S$ 是(18)中的矩阵。

显然，矩阵 $\frac{1}{\mu_n - \delta}L_S$ 具有星形 (1)，其中心质量为 $s$，叶节点质量为 $n_1, \ldots, n_c$，叶参数 $(24)$ $r_i = \frac{e_i n_i}{\mu_n - \delta}$，$i = 1, \ldots, c$。因此 $\frac{1}{\mu_n - \delta}L_S$ 的特征值为 $0, \frac{\theta_1}{\mu_n - \delta}, \ldots, \frac{\theta_c}{\mu_n - \delta}$，其中 $0 < \frac{\theta_1}{\mu_n - \delta} \leq \cdots \leq \frac{\theta_c}{\mu_n - \delta}$。由引理 2.6，对每个 $i \in \{1, \ldots, c\}$，$\theta_i \leq \frac{e_i n_i}{\mu_n - \delta} + n_i$。除以 $\mu_n - \delta$ 并利用 (24)，得到

$$\frac{\theta_i}{\mu_n - \delta} \leq \frac{e_i n_i}{\mu_n - \delta} + n_i = r_i + n_i, \quad 1 \leq i \leq c.$$

因此缩放矩阵 $\frac{L_S}{\mu_n - \delta}$ 满足引理 2.3 的假设。由引理 2.3 可得 $\frac{\theta_1}{\mu_n - \delta} \leq s c$，即等价地，$\theta_1 \leq sc(\mu_n - \delta)$。将此与引理 2.5 结合，得到 $\mu_2 \leq \theta_1 \leq sc(\mu_n - \delta)$。由于 $\mu_n - \delta > 0$，可得 $sc \geq \frac{\mu_2}{\mu_n - \delta}$。在 $t(G)$ 的定义中对所有这样的 $S$ 取最小值，得到 $t(G) \geq \frac{\mu_2}{\mu_n - \delta}$，即为所求。$\square$

## 4. 推论与紧性

对于 $r > 0$，若 $t(G) \geq r$，则称图 $G$ 为 $r$-坚韧的。主定理立即给出如下判据。

**推论 4.1** 设 $G$ 为阶数 $n \geq 2$ 的连通图，$r > 0$。若 $\mu_2 \geq r(\mu_n - \delta)$，则 $G$ 是 $r$-坚韧的。特别地，$\mu_2 > r(\mu_n - \delta)$ 蕴含 $t(G) > r$。

对于连通非完全图，$\delta \geq \mu_2$。因此推论 4.1 的条件不比 $\mu_2 \geq r(\mu_n - \mu_2)$ 更强，等价地 $\mu_2/\mu_n \geq r/(r+1)$，这正是由定理 1.3 中第一个 Gu–Haemers 界得到的判据。由其第二个界导出的判据为 $\mu_n \mu_2 \geq rn(\mu_n - \delta)$，由于 $\mu_n \leq n$，该条件至少与推论 4.1 的条件一样强。因此，主定理在 $\delta > \mu_2$ 时给出比第一个 Gu–Haemers 判据严格更弱的假设，在 $\mu_n < n$ 时给出比第二个 Gu–Haemers 判据严格更弱的假设。

下面记录几个有代表性的推论。设 $p$ 为正整数。阶数至少为 $2p+2$ 的图称为 $p$-可延展的，如果它具有完美匹配且每个大小为 $p$ 的匹配都包含在某个完美匹配中。Plummer [18] 证明了每个阶数为偶数且 $t(G) > p$ 的图 $G$ 是 $p$-可延展的。因此，由推论 4.1 可得如下结论。

**推论 4.2** 设 $G$ 为偶阶 $n$ 的连通图，$p$ 为正整数且 $p < n/2 - 1$。若 $\mu_2 > p(\mu_n - \delta)$，则 $G$ 是 $p$-可延展的。

设 $1 \leq a \leq b$ 为整数。$G$ 的 $[a,b]$-因子是生成子图 $H$，满足对所有顶点 $v$ 有 $a \leq d_H(v) \leq b$。Katerinis [17] 证明，对阶数 $n \geq a+1$ 的图，若 $a < b$ 或 $bn$ 为偶数，则 $t(G) \geq a + \frac{a}{b} - 1$ 保证存在 $[a,b]$-因子。因此我们得到如下改进，改进了由 Gu–Haemers 界导出的相应判据。

**推论 4.3** 设 $G$ 为阶数 $n \geq a+1$ 的连通图，$1 \leq a \leq b$ 为整数，且 $a < b$ 或 $bn$ 为偶数。若 $\mu_2 \geq a + \frac{ab}{b-1}(\mu_n - \delta)$，则 $G$ 具有 $[a,b]$-因子。特别地，若 $k \geq 1$，$n \geq k+1$，$kn$ 为偶数，且 $\mu_2 \geq k(\mu_n - \delta)$，则 $G$ 具有 $k$-因子。

对每个整数 $k \geq 3$，Win [19] 证明了每个 $1/(k-2)$-坚韧图具有最大度至多为 $k$ 的生成树。Ellingham 和 Zha [8] 证明了每个 $4$-坚韧图具有 $2$-行走，即每个顶点至多访问两次的闭生成行走。这些结果给出两个进一步的推论。

**推论 4.4** 设 $G$ 为阶数 $n \geq 2$ 的连通图。

(i) 若 $k \geq 3$ 且 $(k-2)\mu_2 \geq \mu_n - \delta$，则 $G$ 具有最大度至多为 $k$ 的生成树。

(ii) 若 $\mu_2 \geq 4(\mu_n - \delta)$，则 $G$ 具有 $2$-行走。

**定理 1.4 中的界是紧的。** 设 $G = K_{n_1, \ldots, n_q}$ 为完全多部图，$n_1 \geq \cdots \geq n_q$，$q \geq 2$，$n_1 \geq 2$，令 $n = n_1 + \cdots + n_q$。计算其坚韧度时，设 $S$ 使 $G - S$ 不连通，则 $G - S$ 的所有顶点都位于某一部分，设为 $V_i$。令 $k = |V_i \setminus S|$，则 $|S|/c(G-S) = (n-k)/k$。该比值随 $k$ 增大而递减，因此首先通过取 $k = n_i$ 最小化，再通过选择最大部即 $n_i = n_1$ 最小化。此外，$\delta = \mu_2 = n - n_1$，$\mu_n = n$，且 $t(G) = \frac{n - n_1}{n_1}$。因此 $t(G) = \mu_2 / (\mu_n - \delta)$。在正则情形下，这些例子恰好是平衡完全多部图 $K_{m, \ldots, m}$。

等号情形不限于完全多部图。Greaves 和 Zhu [10] 注意到以下构造。从 $K_{n_1, \ldots, n_q}$ 出发，其中 $n_1 \geq \cdots \geq n_q$，令 $r$ 为最大阶部集合的个数，即 $n_1 = \cdots = n_r$，若 $r < q$ 则 $n_r > n_{r+1}$。假设 $n_1 \geq 3$；若 $r = 1$，还需假设 $n_2 \geq 3$。在一个阶数至少为 $3$ 且不同于 $V_1$ 的部分内部添加一条边。所得图不再是完全多部图，但其最小度、代数连通度和最大 Laplacian 特征值仍分别为 $n - n_1$、$n - n_1$ 和 $n$。割集 $V_2 \cup \cdots \cup V_q$ 仍给出比值 $(n - n_1)/n_1$，因此新图也达到等号。当代数连通度特征空间维数足够时，反复进行此构造可得到更多的等号例子。因此目前尚不知晓完整的等号刻画。

我们的证明中隐含了一个基本的必要条件。设 $G$ 在定理 1.4 中达到等号，且 $S$ 在 $t(G)$ 的定义中取到最小值。按第 2 节的记号，最后一串不等式迫使 $\mu_2 = \theta_1 = \frac{|S|}{c(G-S)}(\mu_n - \delta)$。

设 $y$ 为 $L_S$ 的 $\theta_1$-特征向量。由于 $\theta_1 > 0$，$y$ 与 $L_S$ 的核正交，而该核由 $U\mathbf{1}$ 张成。因此 $x = Uy$ 属于 $\mathbf{1}^\perp$。此外，$x^T L(G) x / x^T x = y^T L_S y / y^T y = \theta_1 = \mu_2$。$\mu_2$ 的变分刻画表明 $x$ 是 $L(G)$ 的 $\mu_2$-特征向量。由 $U$ 的定义，该特征向量在 $S$ 上和 $G-S$ 的每个连通分量上是常数。任何完整的等号刻画都必须考虑具有这种谱结构的顶点割。

前面那些非完全多部图的等号例子都不是正则的。平衡完全多部图表明等号在正则情形下成立，但自然的问题是它们是否为唯一的正则例子。

**问题 4.5** 设 $G$ 为连通非完全的 $d$-正则图。若 $t(G) = \mu_2 / (\mu_n - d)$，则 $G$ 是否为平衡完全多部图？

**与独立工作的关系。** 本手稿于 2026 年 5 月 17 日提交出版。我们仅在 2026 年 5 月 18 日 arXiv 公开列表发布后才了解到 Greaves 和 Zhu [10] 的预印本。他们的证明依赖于商矩阵和 Schur 补论证，而我们的证明基于第 2 节中发展的一般加权星图比较引理。特别地，我们的方法隔离出了一个独立于图论应用而表述的矩阵比较结果。

**Hongzhang Chen | Jianxi Li | Shou-Jun Xu**

兰州大学数学与统计学院，甘肃省应用数学中心，甘肃兰州，730000，中国