---
title: Notes on Graph Theory
tags:
  - Kirchhoff's Theorem
  - Note
id: "1055"
categories:
  - [OI, Graph Theory]
  - [OI, Number Theory]
date: 2017-07-05 15:10:37
---

### Matrix-Tree

矩阵的秩、迹、特征值、特征向量

对角化

$G \rightarrow M, M^k, k \in N^*$.

$G=k_n$.

---

### Hoffman-Singleton

$G, \Delta-free, C_4-free, r-regular$.

$(1) |v| \ge r^2+1$.

$(2) r, |v|=r^2+1$.

$G \rightarrow A, (1, 1, ..., 1)A=r(1, 1, ..., 1)$.

$A^2=\begin{bmatrix} r & 0/1 & 0/1 & ... & 0/1 \\\\ 0/1 & r & 0/1 & ... & 0/1 \\\\ 0/1 & 0/1 & r & ... & 0/1 \\\\ ... & ... & ... & ... & ... \\\\ 0/1 & 0/1 & 0/1 & 0/1 & r\end{bmatrix}$.

$A^2+A=\begin{bmatrix} r & 1 & 1 & ... & 1 \\\\ 1 & r & 1 & ... & 1 \\\\ 1 & 1 & r & ... & 1 \\\\ ... & ... & ... & ... & ... \\\\ 1 & 1 & 1 & 1 & r\end{bmatrix}$.

$I=\begin{bmatrix} 1 & 0 & ... & 0 \\\\ 0 & 1 & ... & 0 \\\\ ... & ... & ... & ... \\\\ 0 & 0 & 0 & 1\end{bmatrix}$.

$J=\begin{bmatrix} 1 & 1 & ... & 1 \\\\ 1 & 1 & ... & 1 \\\\ ... & ... & ... & ... \\\\ 1 & 1 & 1 & 1\end{bmatrix}$.

$A\alpha=\lambda\alpha, \lambda$是$A$特征值，$\alpha$是$A$特征向量。

$A\alpha=\lambda\alpha=\lambda I\alpha$.

$(A-\lambda I)\alpha=0$.

$f(x)=|A-\lambda I|$.

$I$特征值为$1$.

$A^2+A=(r-1)I+J$.

特征值为$r-1+n, r-1, r-1, ..., r-1 (n-1)$个。

$r^2+r, r-1, r-1, ..., r-1 (n-1)$个。

$\lambda^2+\lambda=r^2+r, r-1$.

$\lambda=r || {-1 \pm \sqrt{4r-3} \over 2}$.

$tr(A)=0=r+k_1{-1+\sqrt{4r-3} \over 2}+k_2{-1-\sqrt{4r-3} \over 2}, k_1+k_2=n-1$.

$r=2, 3, 7, 57$.

---

### Cauchy Binet

$\begin{bmatrix} x_1 & x_2 & ... & x_n \\\\ y_1 & y_2 & ... & y_n \end{bmatrix}\begin{bmatrix} z_1 & w_1 \\\\ z_2 & w_2 \\\\ ... & ... \\\\ z_n & w_n \end{bmatrix}=\begin{bmatrix} \sum x_iz_i & \sum x_iw_i \\\\ \sum y_iz_i & \sum y_iw_i\end{bmatrix}=A$.

$|A|=\sum_{i, j} \begin{vmatrix}\begin{bmatrix} x_i & x_j \\\\ y_i & y_j \end{bmatrix}\begin{bmatrix} z_i & w_i \\\\ z_j & w_j \end{bmatrix}\end{vmatrix}$.

$m \times n A, n \times m B$.

$|AB|=\sum_{i_1, i_2, ..., i_m} \begin{vmatrix}A\begin{bmatrix} 1 & 2 & ... & m \\\\ i_1 & i_2 & ... & i_m \end{bmatrix} B\begin{bmatrix} i_1 & i_2 & ... & i_m \\\\ 1 & 2 & ... & m \end{bmatrix}\end{vmatrix}$.

---

### Laplace

$a_{i, i}=deg(v_i), a_{i, j}=v_i-v_j$间连边数的相反数。

$L(G) \rightarrow L_v(G), G=det(L_v(G))$.

$\begin{matrix} & & & e(G) & & & \\\\ & & e_1 & e_2 & e_3 & ... & e_m \\\\ & v_1 & 1 & 1 & & & \\\\ & v_2 & 1 & & 1 & & 1 \\\\ v(G) & v_3 & & 1 & & & 1 \\\\ & ... & & & & & \\\\ & v_n & & & 1 & & \end{matrix}$.

随意为$G$定向$\overline{G}=Q \rightarrow Q_v$。

$QQ'=L(G)$.

$det(L_v(G))=det(Q_vQ_v')$.

Cayley Formula

完全图$K_n$的生成树个数为$n^{n-2}$。

Proofs from THE BOOK.