全域木

$C$ を $u=c_0,e,c_1,f_2,c_2,\dots,f_\ell,c_\ell=u$（$e$ を最初の辺とし、$\partial(e)=\{c_0,c_1\}$）と書く。$\ell=1$（$e$ がループ）なら、歩道の中の「$c_0,e,c_0$」の部分を $c_0$ に置き換えればよい。$\ell\geq2$ なら、$c_1,f_2,c_2,\dots,f_\ell,c_0$ は $e$ を使わない $c_1$ から $c_0$ への歩道であり（閉路の辺は相異なる）、その逆順は $c_0$ から $c_1$ への歩道である。$G$ の歩道の中で $e$ を通る部分「$c_0,e,c_1$」または「$c_1,e,c_0$」をこれらの歩道に置き換えれば、同じ端点をもち $e$ を使わない歩道が得られる。

全域木 $(V,F)$ があれば、その中の歩道は $G$ の歩道でもあり、全域木は連結なので $G$ も連結である。
逆に $G$ が連結であるとする。$(V,F)$ が連結となる $F\subset E$ 全体は $F=E$ を含むので空でなく、有限なので、その中で元の個数が最小のもの $F_0$ をとる。$(V,F_0)$ が閉路をもてば、その閉路上の辺 $e$ を除いた $(V,F_0\setminus\{e\})$ は lem-spt-cycle-edge により連結であり、$F_0$ の最小性に反する。よって $(V,F_0)$ は閉路をもたない連結なグラフ、すなわち $G$ の全域木である。

木はループも平行辺ももたないので、Cayleyの公式 の記事の補題「葉の存在と葉の付け外し」が使える。$n$ についての帰納法で示す。$n=1$ なら辺はループになるので辺は $0$ 本である。$n\geq2$ なら、同補題の 1 により木 $T$ は葉（次数 $1$ の頂点）$\ell$ をもち、同補題の 2 により $\ell$ とそれに接続するただ 1 本の辺を除いた $T-\ell$ は $n-1$ 頂点の木である。帰納法の仮定により $T-\ell$ の辺は $n-2$ 本なので、$T$ の辺は $n-1$ 本である。
森の各連結成分は連結で閉路をもたないので木であり、どの辺も端点を含むただ 1 つの連結成分に属する。成分の頂点数を $n_1,\dots,n_c$ とすると、辺の本数は $\sum_i(n_i-1)=n-c$ である。

全域木は $n$ 頂点の木なので、prop-spt-tree-edges により辺は $n-1$ 本であり、除いた辺は $m-(n-1)$ 本である。

1 ならば 2 と 3 が成り立つことは prop-spt-tree-edges による。2 を仮定する。thm-spt-existence により $G$ は全域木 $(V,F)$ をもち、cor-spt-edge-count により $|F|=n-1=|E|$ なので $F=E$ であり、$G$ 自身が木である。3 を仮定する。$G$ は森なので、連結成分の個数を $c$ とすると prop-spt-tree-edges により辺は $n-c$ 本である。これが $n-1$ に等しいので $c=1$ であり、$G$ は連結、したがって木である。

$e$ がループなら、それ自身が閉路である。$\partial(e)=\{x,y\}$（$x\neq y$）とする。$x$ と $y$ が $(V,F)$ の同じ成分にあれば、$F$ の中の $x$ から $y$ への道 $P$ に $e$ を加えると、$e\notin F$ なので辺が相異なり、閉路になる。逆に $(V,F\cup\{e\})$ に閉路 $C$ があれば、$(V,F)$ は閉路をもたないので $C$ は $e$ を含み、$C$ から $e$ を除いた部分は $F$ の辺だけを使う $y$ から $x$ への歩道なので、$x,y$ は同じ成分に属する。後半は、$e$ を加えると $x$ の成分と $y$ の成分の頂点どうしが $e$ を経由して結ばれ、ほかの成分どうしの結ばれ方は変わらないことによる。

$T:=F_m$ とおく。
（全域木であること）作り方から、どの $F_k$ も閉路をもたない。$(V,T)$ が連結でないとして矛盾を導く。$(V,T)$ の連結成分 $C$ で $C\neq V$ となるものをとる。$G$ は連結なので、$C$ の頂点から $C$ の外の頂点への $G$ の道があり、その上に一方の端点が $C$ に、他方が $C$ の外にある辺 $e_k$ がある。$e_k$ の端点は $(V,T)$ の異なる成分に属し、$F_{k-1}\subset T$ なので $(V,F_{k-1})$ でも異なる成分に属する。lem-spt-add-edge により $(V,F_{k-1}\cup\{e_k\})$ は閉路をもたないので $e_k\in F_k\subset T$ となり、$e_k$ の両端点が $(V,T)$ の同じ成分に属することに反する。よって $(V,T)$ は全域木である。
（最小であること）最小全域木のうち、$T$ と共通の辺の本数 $|T\cap T^*|$ が最大のもの $T^*$ をとる。$T^*=T$ なら証明は終わる。$T^*\neq T$ とすると、どちらも $n-1$ 本の辺をもつ（cor-spt-edge-count）ので $T\not\subset T^*$ であり、$T\setminus T^*$ の辺のうち添字が最小のものを $e_k$ とする。$e_k$ の端点を $x,y$ とする（$e_k$ はループでない。ループは閉路なので採用されない）。$T^*$ は連結なので、$T^*$ の中の $x$ から $y$ への道 $P$ があり、$e_k\notin T^*$ なので、$P$ に $e_k$ を加えたものは $T^*\cup\{e_k\}$ の閉路である。$P$ の辺がすべて $T$ に属するなら、この閉路は $T$ の閉路になって矛盾するので、$P$ には $T$ に属さない辺 $f=e_j$ がある。
$j< k$ と仮定する。$f\notin T$ なので、第 $j$ 段で $(V,F_{j-1}\cup\{f\})$ は閉路をもっていた。$F_{j-1}$ の辺は添字が $j$ 未満の $T$ の辺であり、$j< k$ と $k$ の最小性から $T^*$ に属する。よって $F_{j-1}\cup\{f\}\subset T^*$ であり、$T^*$ が閉路をもつことになって矛盾する。したがって $j>k$ であり、並べ方から $w(f)\geq w(e_k)$ である。
$T':=(T^*\setminus\{f\})\cup\{e_k\}$ とおく。$(V,T^*\cup\{e_k\})$ は連結で、$f$ はその閉路（$P$ と $e_k$）の上にあるので、lem-spt-cycle-edge により $(V,T')$ は連結である。$|T'|=n-1$ なので、prop-spt-tree-criterion により $T'$ は全域木である。$w(T')=w(T^*)-w(f)+w(e_k)\leq w(T^*)$ なので $T'$ も最小全域木であり、$f\notin T$、$e_k\in T$ から $|T\cap T'|=|T\cap T^*|+1$ となって $T^*$ の選び方に反する。よって $T^*=T$ であり、$T$ は最小全域木である。

重みが相異なれば、辺の並べ方は一意なので Kruskal 法の出力 $T$ は一意である。$T^*$ を任意の最小全域木とし、$T^*\neq T$ とする。thm-spt-kruskal の証明の後半と同じく $e_k$、$f=e_j$（$j>k$）、$T'$ をとると、重みが相異なるので $w(f)>w(e_k)$ であり、$w(T')< w(T^*)$ となって $T^*$ の最小性に反する。よって $T^*=T$ である。

$\partial(e)=\{u,v\}$ とし、$G$ の全域木を、$e$ を含まないものと含むものに分ける。
（$e$ を含まない全域木）$F\subset E\setminus\{e\}$ について、$(V,F)$ が $G$ の全域木であることと $G-e$ の全域木であることは同じことである（頂点集合も端点も同じ）。よってその個数は $\tau(G-e)$ である。
（$e$ を含む全域木）$G/e$ の頂点集合を $V'$ とし（$|V'|=n-1$）、$e$ を含む $G$ の全域木 $F$ に $F\setminus\{e\}$ を対応させる。これが $G/e$ の全域木の全体への全単射であることを示す。
$F$ を $e$ を含む $G$ の全域木とする。$F$ は $e$ 以外に $u,v$ を結ぶ辺を含まない（含めば $e$ と長さ $2$ の閉路を作る）ので、$F\setminus\{e\}$ は $G/e$ でループを含まない。$(V,F)$ の歩道で頂点 $u,v$ を $z$ に置き換え、辺 $e$ を通る部分「$u,e,v$」「$v,e,u$」を $z$ に縮めると、$(V',F\setminus\{e\})$ の歩道になるので、$(V',F\setminus\{e\})$ は連結である。辺の本数は $(n-1)-1=n-2=|V'|-1$ なので、prop-spt-tree-criterion により $G/e$ の全域木である。
逆に $S\subset E\setminus\{e\}$ を $G/e$ の全域木とする。木はループを含まないので、$S$ は $G$ で $u,v$ を結ぶ辺を含まない。$(V,S\cup\{e\})$ が連結であることを示す。$(V',S)$ の歩道 $x_0,f_1,x_1,\dots,f_\ell,x_\ell$ をとり、各辺 $f_i$ の $G$ での端点を使って、$x_i=z$ である頂点を $u$ か $v$ に戻す。すると隣り合う辺 $f_i$、$f_{i+1}$ が $z$ で接続していた箇所では、$f_i$ の端点と $f_{i+1}$ の端点が $u$ と $v$ に分かれることがあるが、その間に辺 $e$ をはさめば $G$ の歩道になる。$G$ の 2 頂点 $x,y$ をとり、$u,v$ なら $z$ に置き換えた $V'$ の頂点を結ぶ $(V',S)$ の歩道をこのように戻すと、両端は $x$ か（$x\in\{u,v\}$ のとき）$u,v$ のどちらかになり、$y$ についても同様である。端が目的の頂点でなければ、さらに $e$ を 1 回通って $u$ と $v$ を行き来すればよい。よって $(V,S\cup\{e\})$ は連結である。辺の本数は $(n-2)+1=n-1$ なので、prop-spt-tree-criterion により $G$ の全域木である。
2 つの対応 $F\mapsto F\setminus\{e\}$ と $S\mapsto S\cup\{e\}$ は互いに逆なので、$e$ を含む全域木の個数は $\tau(G/e)$ である。2 つの場合を合わせて主張を得る。