Friendship Theorem
Theorem: (Friendship) 任意两点有唯一公共邻居，则 $G$ 中存在某点和其他所有点都相邻。
Proof:
- 假设 $G$ d-正则，则：
Definition: (Strongly regular graph) 设 $G$ 为 $(v,k,\lambda,\mu)$-图，若 $G$ 为 $k$-正则图，任意两点有 $\lambda$ 个公共邻居，任意两点不相邻的有 $\mu$ 个公共邻居，则称 $G$ 为强正则图。
$A^2$ 的特征值为 $(n+d-1)^{(1)},d-1^{(n-1)}$，从而 $A$ 的特征值属于 $\{\pm \sqrt{n+d-1},\pm \sqrt{d-1}\}$。
因此 $d=\sqrt{n+d-1},n=d^2-d+1$
假设A的特征值为 $d^{(1)},\sqrt{d-1}^{(a)},-\sqrt{d-1}^{(b)}$，则可以用 trace 确定 $a,b$。
$$ \begin{aligned} \operatorname{tr}(A)&=\sum \lambda_i=d+\sqrt{d - 1}a-\sqrt{d - 1}b\\ \implies d^2&=(b-a)^2(d-1)\implies d-1 \mid d^2 \implies d=2,n=3 \end{aligned} .$$- 假设 $G$ 非正则图。
令 $N(u)=\{w_i\}$ ，$z_i$ 是 $w_i,v$ 的公共邻居。我们知道 $z_i$ 两两不同，否则相同的 $z_i$ 会与 $u$ 有两个公共邻居。因此 $\deg v\ge \deg u$，进而所有不相邻的顶点度数相同。
因为 $G$ 非正则，所以存在 $w,v$ 使得 $\deg w\neq \deg v$，则 $w,v$ 必须相邻。
假设 $u$ 是 $v,w$ 公共邻居，则要么 $\deg u\neq \deg v$ 要么 $\deg u\neq \deg w$。
不失一般性，假设 $u,v$ 相邻，我们说明 $u$ 与其他所有点相邻。
反证：$\exists x\text{, s.t. } v\not \sim x$，则 $\deg v =\deg x\implies \begin{cases}\deg x\neq \deg u\\ \deg x\neq \deg w \end{cases}$ 因此 $x\sim u,x\sim w$，存在 $C_{4}$ 矛盾。
其他应用
Theorem: $\operatorname{Diag}(G)\le \# \text{ distinct eigenvalue}=k$
Proof: $A$ 的极小多项式为 $f(x)=\prod_{i=1}^{k} (x-\lambda _i)$
$f(A)=0 \implies \exists a_{0},\ldots a_{k-1} \text{ s.t. } A^k=\sum_{i=0}^{k-1} A^i a_i$
若 $\operatorname{G}\ge k$，则 $\exists u,v \text{ s.t. }\operatorname{dist}(u,v)=k$，因此 $LHS_{u,v}\neq 0$，但是 $RHS_{u,v}=0$ 矛盾。
Remark:
$$ \begin{aligned} \lambda_k&=\max_{\substack{U \subset \mathbb{R}^n,\\ \dim U=k}} \min_{{x\in U,x\neq 0}} \frac{x^T Ax}{x^T x}\\ &=\min_{\substack{U \subset \mathbb{R}^n,\\ \dim U=k}} \max_{{x\in U,x\neq 0}} \frac{x^T Ax}{x^T x} \end{aligned} $$
- $\lambda_1=\max \frac{x^T Ax}{x^T x}$, $\lambda_n=\min \frac{x^T Ax}{x^T x}$
Theorem: $\frac{2m}{n}\le \lambda_1 \le \Delta (G)$ (最大度数)
Proof: $x=\mathbf{1},x^T Ax=m$
Remark（不加证明）:
- $\lambda _1\ge 0$ 则 $\exists$ 对应 $\lambda_1$ 的特征向量 $x$，且满足 $\forall i, x_i\ge 0$
- 若 $G$ 联通，则 $\lambda_1$ 重数为 1，并且$\exists$ 对应 $\lambda_1$ 的特征向量 $x$，且满足 $\forall i,x_i>1$
Theorem: $G'$ 是 $G$ 子图，则 $\lambda_1(G')\le \lambda_1(G)$ Proof: 显然
Corollary: $\lambda_1 \ge \sqrt{\Delta}$
Interlacing Eigenvalues of Matrices
Theorem: $A$ 实对称，有特征值 $\lambda_1\ge \lambda_{2}\ldots\ge \lambda_n$。
设 $m\le n$，取 $N\in \mathbb{R}^{m\times n} \text{, s.t. } N N^T=I$。令 $B\coloneqq NAN^T$，有特征值 $\mu_{1}\ge \mu_2\ge \ldots \ge \mu_n$，则我们有：
$$ \forall 1\le i\le m, \lambda _i\ge \mu_i\ge \lambda_{n-m+i} .$$Note: $N$ 的列向量取 $e_i$ 的时候，$B$ 等价于 $A$ 子图的邻接矩阵。
Proof: 设 $B$ 的特征向量为 $\mathbf{u}_i$ (相互垂直且归一化)。对于 $1\le i\le m$，定义 $U\coloneqq \operatorname{span}\{\mathbf{u}_1,\ldots \mathbf{u}_i\}, \dim(U)=i$.
$$ \begin{aligned} \forall x \in U, x&=\sum_{j=1}^{i} a_i \mathbf{u}_i,\\ \frac{x^TBx}{x^Tx}&=\frac{a_{1}^2\lambda_{1}+\ldots +a_i^2 \lambda _i}{a_{1}^2+\ldots a_i^2}\ge \lambda _i .\end{aligned} $$由于前面的 Remark 的第二条第一个等式，我们有 $\lambda _i\ge \mu _i$。
Bounding graph parameters
Theorem: $\alpha (G)$ 是最大独立集的大小，则 $\lambda_{\alpha (G)}\ge 0\ge \lambda_{n-\alpha (G)+1}$
Proof: 取子图 $G'=\text{最大独立集}$，选取 $N$ 使得 $B$ 是 $G'$ 的邻接矩阵（全 0），使用上面的定理。
Theorem: $\chi (G)\ge 1-\frac{\lambda_1}{\lambda_n}$
Proof: 按照定点颜色分块，块内没有边：
$$ A=\begin{pmatrix} 0&A_{1,2}& \ldots &A_{1,m}\\ A_{2,1}&0&\ldots &A_{2,m}\\ \vdots&\vdots&\ddots&\vdots\\ A_{m,1}&A_{m,2}&\ldots&0 \end{pmatrix} .$$取 $\lambda _1$ 的特征向量 $\mathbf{x}$，其中 $\mathbf{x}_i\ge 0$ (由于前面的 Remark 一定存在。将 $\mathbf{x}$ 分块：
$$ \mathbf{x}= \begin{pmatrix} \mathbf{x}_1\\ \mathbf{x}_2\\ \vdots\\ \mathbf{x}_m \end{pmatrix},|\mathbf{x}_i|>0 .$$令：
$$ N=\begin{pmatrix} \frac{\mathbf{x}_1^T }{|\mathbf{x}_1|}& 0 &\ldots &0\\ 0&\frac{\mathbf{x}_2^T }{|\mathbf{x}_2|}&\ldots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\ldots&\frac{\mathbf{x}_m^T }{|\mathbf{x}_m|} \end{pmatrix} ,N^T N=I,B\coloneqq NAN^T .$$由于 Interlacing Theorem $\lambda _1\ge \mu _1\ge \ldots \ge \mu _m\ge \lambda_m$
而
$$ \begin{aligned} B \begin{pmatrix} |\mathbf{x}_1|\\|\mathbf{x}_2|\\ \vdots\\ |\mathbf{x_m}| \end{pmatrix} &=NAN^T\begin{pmatrix} |\mathbf{x}_1|\\|\mathbf{x}_2|\\ \vdots\\ |\mathbf{x_m}| \end{pmatrix}\\ &=NA \begin{pmatrix} \mathbf{x}_{1}\\ \mathbf{x}_2\\ \vdots \\ \mathbf{x}_m \end{pmatrix} \\ &=NA \mathbf{x}=\lambda _1 N \mathbf{x}=\lambda _1 \begin{pmatrix} |\mathbf{x}_1|\\|\mathbf{x}_2|\\ \vdots\\ |\mathbf{x_m}| \end{pmatrix} \end{aligned} $$从而 $\lambda _1=\mu _1$，后面听懵了，放张板书：
