固有値の交錯定理

$x=\sum_{j=1}^nc_ju_j$ と書くと、正規直交性から $x^{\mathsf T}x=\sum_jc_j^2$、$x^{\mathsf T}Ax=\sum_j\lambda_jc_j^2$ である。1 では $c_1=\dots=c_{i-1}=0$ なので
$$ \lambda_i\,x^{\mathsf T}x-x^{\mathsf T}Ax=\sum_{j\ge i}(\lambda_i-\lambda_j)c_j^2\ \ge\ 0 $$
であり、等号は $\lambda_j<\lambda_i$ となる $j$ で $c_j=0$ となること、すなわち $x$ が固有値 $\lambda_i$ の固有空間に属することと同値である。2 では $c_{i+1}=\dots=c_n=0$ なので $x^{\mathsf T}Ax-\lambda_i\,x^{\mathsf T}x=\sum_{j\le i}(\lambda_j-\lambda_i)c_j^2\ge0$ で、等号条件も同様である。$\square$

最大・最小の形．$W_0:=\langle u_1,\dots,u_i\rangle$（$u_1,\dots,u_i$ の張る部分空間）とおくと、lem-il-rayleigh-bounds の 2 により $W_0$ の上で $R_A\ge\lambda_i$ であり、$x=u_i$ で $R_A(u_i)=\lambda_i$ となる。よって $W_0$ での最小値は $\lambda_i$ である。
次に、$W$ を任意の $i$ 次元部分空間とする。$U:=\langle u_i,\dots,u_n\rangle$ は $n-i+1$ 次元なので、
$$ \dim(W\cap U)\ \ge\ \dim W+\dim U-n=i+(n-i+1)-n=1 $$
であり、$W\cap U$ は $0$ でない $x$ を含む。$x\in U$ は $u_1,\dots,u_{i-1}$ に直交するので、補題の 1 により $R_A(x)\le\lambda_i$ である。よって $W$ での最小値は $\lambda_i$ 以下である。以上から、$i$ 次元部分空間の上での最小値の最大値は $\lambda_i$ で、$W=W_0$ で達成される。
最小・最大の形．$U=\langle u_i,\dots,u_n\rangle$ の上では補題の 1 により $R_A\le\lambda_i$ で、$x=u_i$ で等号が成り立つので、$U$ での最大値は $\lambda_i$ である。$W$ が任意の $n-i+1$ 次元部分空間なら、$\dim(W\cap W_0)\ge(n-i+1)+i-n=1$ なので $0$ でない $x\in W\cap W_0$ があり、補題の 2 により $R_A(x)\ge\lambda_i$ である。よって $W$ での最大値は $\lambda_i$ 以上であり、最大値の最小値は $\lambda_i$ で、$W=U$ で達成される。$\square$

$B^{\mathsf T}=S^{\mathsf T}A^{\mathsf T}S=B$ なので $B$ は $m$ 次の実対称行列であり、thm-il-courant-fischer を $B$ にも使える。
段 1（Rayleigh 商の移し替え）．$s\in\mathbb R^m$、$s\neq0$ に対し $x:=Ss$ とおく。$x^{\mathsf T}x=s^{\mathsf T}S^{\mathsf T}Ss=s^{\mathsf T}s>0$ なので $x\neq0$ であり、
$$ R_A(Ss)=\frac{s^{\mathsf T}S^{\mathsf T}ASs}{s^{\mathsf T}S^{\mathsf T}Ss}=\frac{s^{\mathsf T}Bs}{s^{\mathsf T}s}=R_B(s) $$
である。また $Ss=0$ なら $s=S^{\mathsf T}Ss=0$ なので、線形写像 $s\mapsto Ss$ は単射であり、$\mathbb R^m$ の $j$ 次元部分空間 $V$ を $\mathbb R^n$ の $j$ 次元部分空間 $SV:=\{Ss\mid s\in V\}$ に写す。
段 2（上からの評価 $\mu_i\le\lambda_i$）．thm-il-courant-fischer の最大・最小の形を $B$ に使うと、$\mathbb R^m$ の $i$ 次元部分空間 $V$ があって、$V$ の $0$ でないすべての $s$ で $R_B(s)\ge\mu_i$ である。段 1 により $SV$ は $\mathbb R^n$ の $i$ 次元部分空間で、$SV$ の $0$ でないすべての元 $x=Ss$ について $R_A(x)=R_B(s)\ge\mu_i$ である。したがって
$$ \lambda_i=\max_{\dim W=i}\ \min_{x\in W,\ x\neq0}R_A(x)\ \ge\ \min_{x\in SV,\ x\neq0}R_A(x)\ \ge\ \mu_i $$
である。
段 3（下からの評価 $\mu_i\ge\lambda_{n-m+i}$）．thm-il-courant-fischer の最小・最大の形を $B$ に使うと、$\mathbb R^m$ の $m-i+1$ 次元部分空間 $V'$ があって、$V'$ の $0$ でないすべての $s$ で $R_B(s)\le\mu_i$ である。$SV'$ は $\mathbb R^n$ の $m-i+1$ 次元部分空間であり、$j:=n-m+i$ とおくと $n-j+1=m-i+1$ なので、同じ定理の最小・最大の形を $A$ と番号 $j$ に使って
$$ \lambda_{n-m+i}=\min_{\dim W=m-i+1}\ \max_{x\in W,\ x\neq0}R_A(x)\ \le\ \max_{x\in SV',\ x\neq0}R_A(x)\ \le\ \mu_i $$
を得る。段 2 と段 3 で主張が示された。$\square$

$a:=\alpha(G)$ とし、大きさ $a$ の独立集合 $C$ をとる。$a=n$ なら $G$ は辺をもたず、固有値はすべて $0$ なので主張は成り立つ。$a< n$ とする。$G[C]$ の隣接行列は $a$ 次の零行列で、固有値は $\mu_1=\dots=\mu_a=0$ である。cor-il-induced により、$i=1,\dots,a$ について $\lambda_i\ge\mu_i=0$ なので、$\lambda_1,\dots,\lambda_a$ はすべて $0$ 以上であり、$0$ 以上の固有値は $a$ 個以上ある。同じく $\lambda_{n-a+i}\le\mu_i=0$ なので、$\lambda_{n-a+1},\dots,\lambda_n$ はすべて $0$ 以下であり、$0$ 以下の固有値も $a$ 個以上ある。$\square$

$G$ は辺をもつので $\operatorname{tr}A=0$ かつ $A\neq0$ であり、固有値の和が $0$ で全部が $0$ ではないから、負の固有値がある。よって $\lambda_n< 0$ である。
$a:=\alpha(G)$、$C$ を大きさ $a$ の独立集合とする。$a=n$ なら辺がないので $a< n$ である。$C$ の特性ベクトル（$C$ の頂点で $1$、ほかで $0$）を $\mathbf 1_C$、$D:=V\setminus C$ の特性ベクトルを $\mathbf 1_D$ とし、$n\times2$ 行列
$$ S:=\Bigl(\tfrac1{\sqrt a}\mathbf 1_C\ \ \tfrac1{\sqrt{n-a}}\mathbf 1_D\Bigr) $$
をとる。2 本の列は台が交わらない単位ベクトルなので $S^{\mathsf T}S=I_2$ である。$B:=S^{\mathsf T}AS$ の成分を数える。$\mathbf 1_C^{\mathsf T}A\mathbf 1_C$ は $C$ の中の辺の本数の 2 倍で $0$ である。$C$ の各頂点の $k$ 個の隣接頂点はすべて $D$ にあるので $\mathbf 1_C^{\mathsf T}A\mathbf 1_D=ka$ である。全体では $\mathbf 1^{\mathsf T}A\mathbf 1=kn$ なので $\mathbf 1_D^{\mathsf T}A\mathbf 1_D=kn-2ka$ である。よって
$$ B=\begin{pmatrix}0&\dfrac{ka}{\sqrt{a(n-a)}}\\[2mm]\dfrac{ka}{\sqrt{a(n-a)}}&\dfrac{k(n-2a)}{n-a}\end{pmatrix} $$
である。$w:=(\sqrt a,\sqrt{n-a})^{\mathsf T}$ とおくと $Sw=\mathbf 1$、$S^{\mathsf T}\mathbf 1=w$ なので、$A\mathbf 1=k\mathbf 1$ から $Bw=S^{\mathsf T}ASw=S^{\mathsf T}(k\mathbf 1)=kw$ であり、$k$ は $B$ の固有値である。もう 1 つの固有値は $\operatorname{tr}B-k=\frac{k(n-2a)}{n-a}-k=-\frac{ka}{n-a}$ である。
thm-il-main（$m=2$、$i=2$）により、$B$ の小さいほうの固有値は $\lambda_{n-2+2}=\lambda_n$ 以上なので
$$ -\frac{ka}{n-a}\ \ge\ \lambda_n,\qquad\text{すなわち}\qquad ka\ \le\ -\lambda_n\,(n-a) $$
である。整理すると $a\,(k-\lambda_n)\le n\,(-\lambda_n)$ で、$k-\lambda_n>0$ で割って主張を得る。$\square$