符号なしLaplacian

$(BB^{\mathsf T})_{uv}=\sum_eB_{ue}B_{ve}$ である。$u=v$ なら、$B_{ue}^2$ は $e$ が $u$ に接続するとき $1$ なので（ループはない）、和は $d_u$ である。$u\neq v$ なら、$B_{ue}B_{ve}=1$ となるのは $e$ の両端が $u,v$ のときなので、和は $u$ と $v$ を結ぶ辺の本数 $A_{uv}$ である。よって $BB^{\mathsf T}=D+A=Q$ である。$B^{\mathsf T}x$ の $e$ 成分は $x_{u(e)}+x_{w(e)}$ なので $x^{\mathsf T}Qx=\|B^{\mathsf T}x\|^2$ はその 2 乗の和である。$Qx=qx$、$x\neq0$ なら $q\,x^{\mathsf T}x=x^{\mathsf T}Qx\ge0$ から $q\ge0$ である。$\square$

段 1（$s_i\in\ker Q$）．$G_i$ の辺は $X_i$ と $Y_i$ を結ぶので、両端での $s_i$ の値の和は $1+(-1)=0$ である。ほかの成分の辺では両端の値が $0$ である。よって $B^{\mathsf T}s_i=0$、したがって $Qs_i=B(B^{\mathsf T}s_i)=0$ である。
段 2（核の元の形）．$Qx=0$ とすると、prop-sl-quadratic により $0=x^{\mathsf T}Qx=\sum_e(x_{u(e)}+x_{w(e)})^2$ なので、すべての辺で $x_{w(e)}=-x_{u(e)}$ である。連結成分 $C$ を 1 つとり、頂点 $v_0\in C$ を固定する。$C$ の頂点 $v$ を $v_0$ と結ぶ歩道 $v_0,v_1,\dots,v_k=v$ に沿って符号が交互に変わるので、$x_v=(-1)^kx_{v_0}$ である。
$C$ が二部成分でなければ、$C$ は長さ奇数の閉路をもつ（二部グラフ の定理「閉路の長さによる特徴付け」）。$v_0$ からその閉路の頂点 $w$ へ歩道で行き、閉路を 1 周して $w$ に戻り、同じ歩道で $v_0$ に戻ると、長さが奇数の閉歩道が得られる。上の式から $x_{v_0}=-x_{v_0}$、すなわち $x_{v_0}=0$ であり、したがって $C$ の上で $x=0$ である。
$C=G_i$ が二部成分なら、$v_0\in X_i$ とすると、$v$ が $X_i$ にあるか $Y_i$ にあるかで $v_0$ からの歩道の長さの偶奇が決まる（辺は $X_i$ と $Y_i$ を行き来する）。よって $C$ の上で $x=x_{v_0}s_i$ である。合わせて $x=\sum_ic_is_i$ の形になる。
段 3（次元と重複度）．$s_1,\dots,s_b$ は台が互いに交わらない $0$ でないベクトルなので線形独立であり、$\dim\ker Q=b$ である。実対称行列では固有値の代数的重複度は固有空間の次元に等しい（スペクトル定理）。$\square$

$(SLS)_{uv}=S_{uu}L_{uv}S_{vv}$ である。$u=v$ なら $L_{uu}=d_u=Q_{uu}$ である。$u\neq v$ で $A_{uv}\neq0$ なら、$u,v$ は二部分割の異なる側にあるので $S_{uu}S_{vv}=-1$ となり、$(SLS)_{uv}=-(-A_{uv})=A_{uv}=Q_{uv}$ である。$A_{uv}=0$ ならどちらも $0$ である。$S^2=I$ も明らかである。$\square$

二部グラフなら prop-sl-similar により一致する。逆にスペクトルが一致すれば、固有値 $0$ の重複度も一致する。Laplacian 側ではそれは連結成分の個数（Laplacian行列 の定理「核の次元と連結成分の個数」）、符号なし側では二部成分の個数（thm-sl-kernel）である。よってすべての連結成分が二部成分であり、$G$ は二部グラフである。$\square$

段 1（不等式）．実対称行列 $M$ の最大固有値 $\theta$ は、単位ベクトル $y$ にわたる $y^{\mathsf T}My$ の最大値であり、最大値をとる $y$ は $\theta$ の固有ベクトルに限る（Rayleigh商。固有ベクトルの正規直交基底で $y=\sum c_iw_i$ と展開すると $y^{\mathsf T}My=\sum\theta_ic_i^2\le\theta\sum c_i^2=\theta$ で、等号は $\theta_i< \theta$ の $i$ で $c_i=0$ のときに限る）。$x$ を $L$ の $\mu_{\max}$ の単位固有ベクトルとし、$\lvert x\rvert:=(\lvert x_1\rvert,\dots,\lvert x_n\rvert)$ とおく。各辺で $(x_u-x_v)^2\le(\lvert x_u\rvert+\lvert x_v\rvert)^2$ なので
$$ \mu_{\max}=\sum_{uv\in E}(x_u-x_v)^2\ \le\ \sum_{uv\in E}(\lvert x_u\rvert+\lvert x_v\rvert)^2=\lvert x\rvert^{\mathsf T}Q\lvert x\rvert\ \le\ q_1 $$
である。
段 2（等号の場合）．$\mu_{\max}=q_1$ なら、上の 2 つの不等号はどちらも等号である。2 つ目の等号から、$\lvert x\rvert$ は $Q$ の $q_1$ の固有ベクトルである。もし $\lvert x_v\rvert=0$ となる頂点 $v$ があれば、$0=q_1\lvert x_v\rvert=(Q\lvert x\rvert)_v=d_v\lvert x_v\rvert+\sum_{u}A_{vu}\lvert x_u\rvert$ から $v$ の隣接頂点でも $\lvert x_u\rvert=0$ であり、$G$ は連結なのですべての頂点で $x=0$ となって矛盾する。よって $x$ はどの頂点でも $0$ でない。1 つ目の等号から、各辺で $(x_u-x_v)^2=(\lvert x_u\rvert+\lvert x_v\rvert)^2$、すなわち $x_ux_v=-\lvert x_u\rvert\lvert x_v\rvert< 0$ である。したがって $x_v>0$ の頂点と $x_v< 0$ の頂点への分割は二部分割であり、$G$ は二部グラフである。逆に二部グラフなら prop-sl-similar により $\mu_{\max}=q_1$ である。$\square$

下界：Rayleigh商 により $q_1\ge\mathbf 1^{\mathsf T}Q\mathbf 1/n=\sum_e(1+1)^2/n=4m/n$ である。また次数 $\Delta$ の頂点 $v$ をとり、$x_v=\Delta$、$v$ の $\Delta$ 個の隣接頂点で $x_u=1$、ほかで $0$ とおくと、$x^{\mathsf T}x=\Delta^2+\Delta$ である。$v$ に接続する $\Delta$ 本の辺はそれぞれ $(\Delta+1)^2$ を寄与し、ほかの辺の寄与は $0$ 以上なので $x^{\mathsf T}Qx\ge\Delta(\Delta+1)^2$ である。よって $q_1\ge\Delta(\Delta+1)^2/(\Delta^2+\Delta)=\Delta+1$ である（この $x$ は星 $K_{1,\Delta}$ の $Q$ の最大固有値 $\Delta+1$ の固有ベクトルである）。
上界：$Q=BB^{\mathsf T}$ と $B^{\mathsf T}B$ は同じ $0$ でない固有値をもつ（線グラフ の定理「線グラフの固有値」の証明の中の等式 $t^{\,n}\det(tI_m-B^{\mathsf T}B)=t^{\,m}\det(tI_n-BB^{\mathsf T})$）。$B^{\mathsf T}B$ は非負行列で、辺 $e=uv$ の行の和は $\sum_f\sum_wB_{we}B_{wf}=\sum_wB_{we}d_w=d_u+d_v$ である。非負行列の固有値の絶対値は行和の最大値以下なので（固有ベクトルの成分の絶対値が最大の行を見る）、$q_1\le\max_{uv\in E}(d_u+d_v)$ である。$k$-正則なら $4m/n=2k$ と $2\Delta=2k$ が一致する。$\square$

$BB^{\mathsf T}=Q$ と $B^{\mathsf T}B$ は $0$ でない固有値を重複度こめて共有する（prf-sl-bounds で引いた等式）。$B^{\mathsf T}B$ は $m$ 次で半正定値なので、残りの $m-r$ 個の固有値は $0$ である。$A(L(G))=B^{\mathsf T}B-2I_m$ から従う。$\square$