完全二部グラフ

1：$x\in X$ の隣接頂点はちょうど $Y$ の元なので次数は $n$、同様に $Y$ の頂点の次数は $m$ である。辺は $X\times Y$ の元と 1 対 1 に対応するので $mn$ 本ある。次数が $m$ と $n$ の 2 種類なので、正則であることは $m=n$ と同値である。
2：異なる部集合の 2 頂点は定義により隣接し、同じ部集合の 2 頂点を結ぶ辺はない。
3：相異なる 2 頂点は、異なる部集合にあれば隣接し、同じ部集合にあれば他方の部集合の頂点（$m,n\ge1$ なので存在する）を経由する長さ $2$ の道で結ばれる。よって連結で、距離は $2$ 以下である。$m+n\ge3$ なら一方の部集合に 2 頂点があり、2 によりそれらは隣接しないので距離はちょうど $2$ である。
4：同型なグラフの頂点数と辺数は等しい（グラフ の記事の命題「同型の基本性質」）ので、$m+n=m'+n'$、$mn=m'n'$ である。$\{m,n\}$ と $\{m',n'\}$ はどちらも 2 次方程式 $t^2-(m+n)t+mn=0$ の解の組なので一致する。逆は $K_{m,n}\cong K_{n,m}$ による。$\square$

1 ⇒ 3：部集合を $X,Y$ とする。3 頂点のうち 2 頂点は同じ部集合に属し、隣接しないので、三角形はない。3 頂点 $u,v,w$ で辺が $uv$ だけだとすると、$u,v$ は異なる部集合に属する。$w$ は $u$ か $v$ と同じ部集合にあり、前者なら $w$ は $v$ と、後者なら $u$ と隣接するので、辺は 2 本以上になり矛盾する。
3 ⇒ 2：関係を $\sim$ と書く。反射的かつ対称的であることは明らかである。推移性を示す。$u\sim v$、$v\sim w$ とし、$u,v,w$ のどれか 2 つが等しければ $u\sim w$ は明らかなので、相異なるとする。このとき $uv\notin E$、$vw\notin E$ であり、もし $uw\in E$ なら $\{u,v,w\}$ は辺 $uw$ だけを持ち、$K_2\cup K_1$ を誘導して仮定に反する。よって $uw\notin E$、$u\sim w$ である。相異なる同値類が 3 個あれば、各類から 1 頂点ずつとった 3 頂点は互いに $\sim$ でなく、すなわち互いに隣接して三角形をなすので、仮定に反する。
2 ⇒ 1：同値類を $C_1,C_2$ とする（類が 1 個なら $C_2:=\emptyset$）。同じ類の相異なる 2 頂点は $\sim$ なので隣接せず、異なる類の 2 頂点は $\sim$ でないので隣接する。よって $G$ は部集合 $C_1,C_2$ の完全二部グラフである。$\square$

$\pi$ を自己同型とする。prop-complete-bipartite-basic の 2 により、相異なる 2 頂点が同じ部集合に属することは隣接しないことと同値であり、$\pi$ は隣接しないことを保つので、同じ部集合に属することも保つ。よって $\pi(X)$ の元はすべて同じ部集合に属し（$X$ が 1 元なら明らか）、$\pi(Y)$ の元も同様である。$\pi(X)$ と $\pi(Y)$ が同じ部集合 $P$ に含まれるとすると、$\pi$ の全射性から $X\cup Y\subset P$ となり、もう一方の部集合が空でないことに反する。したがって $\pi(X)$ と $\pi(Y)$ は異なる部集合に含まれ、$\pi$ は全単射なので $\{\pi(X),\pi(Y)\}=\{X,Y\}$ である。
逆に $\{\pi(X),\pi(Y)\}=\{X,Y\}$ なら、$\pi$ は「異なる部集合に属する」という関係を保ち、これは隣接と同値なので $\pi$ は自己同型である。
$\pi(X)=X$、$\pi(Y)=Y$ となる置換は、$X$ の置換と $Y$ の置換の組と 1 対 1 に対応し、$m!\,n!$ 個あり、この対応は群の同型 $S_m\times S_n\to\{\pi\mid\pi(X)=X,\ \pi(Y)=Y\}$ を与える。$\pi(X)=Y$ となる置換は $m=n$ のときに限って存在し、そのとき $X$ と $Y$ を入れ替える 1 つの置換 $\tau$ を固定すれば、それらは $\tau\circ\rho$（$\rho(X)=X$、$\rho(Y)=Y$）の形にちょうど 1 通りに書けるので $(n!)^2$ 個ある。$\square$

$m\le n$ としてよい。最大次数は $n$ なので $\chi'(K_{m,n})\ge n$ である。部集合を $X=\{x_0,\dots,x_{m-1}\}$、$Y=\{y_0,\dots,y_{n-1}\}$ とし、辺 $x_iy_j$ に色 $c(x_iy_j):=i+j\bmod n\in\mathbb{Z}/n\mathbb{Z}$ を塗る。$x_i$ に集まる辺 $x_iy_j$（$0\le j\le n-1$）の色は $j$ ごとに異なる。$y_j$ に集まる辺 $x_iy_j$（$0\le i\le m-1$）の色も、$0\le i< i'\le m-1$ なら $0< i'-i< m\le n$ なので $i+j\not\equiv i'+j\pmod n$ となり、互いに異なる。よって $c$ は $n$ 色の辺彩色であり、$\chi'(K_{m,n})\le n$ である。$\square$

行列の積を計算すると
$$\begin{pmatrix}A&B\\ C&D\end{pmatrix}=\begin{pmatrix}I_p&0\\CA^{-1}&I_q\end{pmatrix}\begin{pmatrix}A&B\\0&D-CA^{-1}B\end{pmatrix}$$
である。右辺の第 1 因子は対角成分が $1$ の下三角行列なので行列式は $1$、第 2 因子はブロック上三角行列なので行列式は $\det A\cdot\det(D-CA^{-1}B)$ である（行列式）。$\square$

頂点を $x_1,\dots,x_m,y_1,\dots,y_n$ の順に並べると、prop-complete-bipartite-basic の 1 により Laplace 行列は
$$L=\begin{pmatrix}nI_m&-J_{m\times n}\\-J_{n\times m}&mI_n\end{pmatrix}$$
である。$K_{m,n}$ はループを持たない連結なグラフなので、行列木定理を $y_n$ の行と列を除いた $L_0$ に使う。
$n=1$ なら $L_0=nI_m=I_m$ なので $\tau=1=m^0\cdot1^{m-1}$ である（$K_{m,1}$ は星で、それ自身が唯一の全域木である）。
$n\ge2$ とする。$L_0=\begin{pmatrix}nI_m&-J_{m\times(n-1)}\\-J_{(n-1)\times m}&mI_{n-1}\end{pmatrix}$ に lem-complete-bipartite-block-det を $A=nI_m$ として使う。$J_{(n-1)\times m}J_{m\times(n-1)}=mJ_{n-1}$ なので
$$\det L_0=n^m\det\Bigl(mI_{n-1}-\frac1n\,J_{(n-1)\times m}J_{m\times(n-1)}\Bigr)=n^m\det\Bigl(mI_{n-1}-\frac mn\,J_{n-1}\Bigr)$$
である。$M:=mI_{n-1}-\frac mnJ_{n-1}$ とおく。すべての成分が $1$ のベクトル $\mathbf 1\in\mathbb{R}^{n-1}$ について $J_{n-1}\mathbf 1=(n-1)\mathbf 1$ なので $M\mathbf 1=\bigl(m-\frac mn(n-1)\bigr)\mathbf 1=\frac mn\mathbf 1$ である。成分の和が $0$ のベクトル $w$ では $J_{n-1}w=0$ なので $Mw=mw$ である。$\mathbf 1$ と、成分の和が $0$ のベクトル全体（$n-2$ 次元）の基底を合わせると $\mathbb{R}^{n-1}$ の基底になり、この基底で $M$ は対角成分 $\frac mn,m,\dots,m$ の対角行列で表されるので、$\det M=\frac mn\cdot m^{n-2}$ である。よって
$$\tau(K_{m,n})=\det L_0=n^m\cdot\frac{m^{n-1}}{n}=m^{n-1}n^{m-1}$$
である。$\square$

$V=\{1,\dots,n\}$ とし、$x=(x_1,\dots,x_n)\in\mathbb{R}^n$ を考える。部分集合 $S\subset V$ に対し $s_S(x):=\sum_{u\in S}x_u$ とおく。$A_i\cap B_i=\emptyset$ なので
$$s_{A_i}(x)\,s_{B_i}(x)=\sum_{u\in A_i}\sum_{v\in B_i}x_ux_v$$
は、一方が $A_i$、他方が $B_i$ に属する頂点の組 $\{u,v\}$ のそれぞれについて $x_ux_v$ を 1 回ずつ足したものである。分解の条件から、相異なる 2 頂点の組はちょうど 1 つの $i$ で 1 回ずつ現れるので
$$\sum_{i=1}^rs_{A_i}(x)\,s_{B_i}(x)=\sum_{1\le u< v\le n}x_ux_v=\frac12\Bigl(\bigl(x_1+\dots+x_n\bigr)^2-\bigl(x_1^2+\dots+x_n^2\bigr)\Bigr)$$
である。この等式を (1) とよぶ。
$r< n-1$ と仮定する。$x$ についての $r+1$ 個の 1 次方程式
$$x_1+\dots+x_n=0,\qquad s_{A_1}(x)=0,\ \dots,\ s_{A_r}(x)=0$$
は、方程式の個数 $r+1$ が未知数の個数 $n$ より少ないので、$x\neq0$ の解を持つ。この $x$ では (1) の左辺は $0$、右辺は $-\frac12(x_1^2+\dots+x_n^2)<0$ となり、矛盾する。よって $r\ge n-1$ である。
$r=n-1$ の分解は、$i=1,\dots,n-1$ について $A_i:=\{i\}$、$B_i:=\{i+1,\dots,n\}$ とおけば得られる。実際、$u< v$ の組 $\{u,v\}$ は $i=u$ でだけ条件を満たす。$\square$