グラフのラプラシアン固有値0の重複度と連結成分の関係

ラプラシアン固有値$0$の重複度を$m_0$，グラフの連結成分を$C_l$（$1\leq l\leq c$）とする．
$C_l$（$1\leq l\leq c$）に対応した値が全て$1$，その他の値が全て$0$という$n$次ベクトル$x'_l={}^t[0,\dots,0,\underbrace{1,\dots,1}_{\text{$C_l$に対応した部分}},0,\dots,0] \quad \text{（$1\leq l\leq c$）}$が線形独立な固有値$0$の固有ベクトルとして構成できるので，$m_0\geq c$である．$x={}^t[x_1,x_2,\dots,x_n]$をラプラシアン固有値$0$の固有ベクトルとすると，${}^tx'Lx'=0$ であるから，

$0={}^tx'Lx'$
$=\sum_{l=1}^c\sum_{j\in C_l} x_j(L x)_j$
$=\sum_{l=1}^c\left(\sum_{j\in C_l} D_{j,j}x_j^2-\sum_{j,k\in C_l} A_{j,k}x_jx_k\right)$ （$L=D-A$より）
$=\sum_{l=1}^c\left(\sum_{j\in C_l} \sum_{k\in C_l} A_{j,k}x_j^2-\sum_{j,k\in C_l} A_{j,k}x_jx_k\right)$
$=\sum_{l=1}^c\sum_{j\in C_l} x_j \sum_{k\in C_l} A_{j,k} (x_j-x_k)$
$=\frac{1}{2}\sum_{l=1}^c\sum_{j,k\in C_l} \left(x_jA_{j,k}(x_j-x_k)+x_kA_{k,j}(x_k-x_j)\right)$
$=\frac{1}{2}\sum_{l=1}^c\sum_{j,k\in C_l} (x_jA_{j,k}-x_kA_{k,j})(x_j-x_k)$

ここで，$A_{j,k}=A_{k,j}$（$1\leq j,k\leq n$）より，

$=\frac{1}{2}\sum_{l=1}^c\sum_{j,k\in C_l} A_{j,k}(x_j-x_k)^2$

である．

連結成分$C_l$（$1\leq l\leq c$）上の任意の$2$頂点$j,k\in C_l$（$1\leq l\leq c$）は経路$j\rightarrow p_1\rightarrow p_2\rightarrow \dots \rightarrow p_s\rightarrow k$（$p_1,\dots,p_s\in C_l$（$1\leq l\leq c$））が存在して，$A_{j,p_1}=A_{p_1,p_2}=\dots=A_{p_s,k}=1 \quad \text{（$1\leq l\leq c$）}$である．
したがって，$x_j=x_{p_1}=x_{p_2}=\dots=x_{p_s}=x_k \quad \text{（$j,p_1,\dots,p_s,k\in C_l$（$1\leq l\leq c$））}$であるから，$x$がラプラシアン固有値$0$の固有ベクトルとなるとき，$x={}^t[\underbrace{a_1,\dots,a_1}_{\text{$C_1$に対応した部分}},\underbrace{a_2,\dots,a_2}_{\text{$C_2$に対応した部分}},\dots,\underbrace{a_c,\dots,a_c}_{\text{$C_c$に対応した部分}}] \quad \text{（$a_l\in\mathbb{C}$，$1\leq l\leq c$）}$である．

よって，ラプラシアン固有値$0$の固有ベクトル$x$は$x'_l$（$1\leq l\leq c$）を用いて$x=\sum_{l=1}^ca_lx'_l \quad \text{（$a_l\in\mathbb{C}$，$1\leq l\leq c$）}$である．
$x'_l$（$1\leq l\leq c$）の線形結合として表せるから，$c\geq m_0$である．

よって，$m_0=c$であるから，グラフ$G$のラプラシアン固有値$0$の重複度は，連結成分の個数に等しい．