最小全域木

$(V,T\setminus\{f\})$ の 2 つの連結成分の頂点集合を $X,Y$ とする。
1 ⇔ 2：$(V,T\setminus\{f\})$ は閉路をもたない。全域木 の記事の補題「辺を加えても閉路ができない条件」により、$e$ を加えたものが閉路をもたないことと、$e$ の端点が $X$ と $Y$ に分かれること（$e\in D_T(f)$）は同値であり、そのとき 2 つの成分は 1 つにまとまるので、$(T\setminus\{f\})\cup\{e\}$ は連結で閉路をもたない、すなわち全域木である。$e$ の端点が同じ成分にあれば閉路ができるので全域木でない。
2 ⇔ 3：$e$ の端点を $x,y$ とし、$x$ と $y$ を結ぶ $T$ の道を $P$ とする。$f\notin P$ なら $P$ は $T\setminus\{f\}$ の道なので、$x,y$ は同じ成分にあり、$e\notin D_T(f)$ である。$f\in P$ なら、$x,y$ は異なる成分にある。同じ成分にあれば $T\setminus\{f\}$ の中に $x$ と $y$ を結ぶ道があり、それは $f$ を含まないので $P$ と異なる $T$ の道になり、木の道の一意性に反するからである。よって $f\in C_T(e)$（すなわち $f\in P$）と $e\in D_T(f)$ は同値である。$\square$

2 ⇔ 3：$e=f$ の組は両辺が等しい。$D_T(f)$ はループを含まず、$f$ 以外の元は $T$ に属さない。$C_T(e)$ の $e$ 以外の元は $T$ に属する。したがって 2 も 3 も「ループでない $e\notin T$ と $f\in T$ の組で $e\in D_T(f)$、すなわち（lem-mst-exchange により）$f\in C_T(e)$ となるものすべてについて $w(f)\le w(e)$」と同じ主張である。
1 ⇒ 2：ループでない $e\notin T$ と $f\in C_T(e)$ で $w(f)>w(e)$ となるものがあったとする。$f\neq e$ なので $f\in T$ であり、lem-mst-exchange により $T':=(T\setminus\{f\})\cup\{e\}$ は全域木で、$w(T')=w(T)-w(f)+w(e)< w(T)$ となる。これは 1 に反する。
3 ⇒ 1：最小全域木のうち、$T$ と共通の辺の本数 $|T\cap T^*|$ が最大のもの $T^*$ をとる。$T^*=T$ を示せばよい。$T^*\neq T$ とすると、どちらも辺は $n-1$ 本なので $f\in T\setminus T^*$ がある。$f$ の端点 $x,y$ は $(V,T\setminus\{f\})$ の異なる成分 $X\ni x$、$Y\ni y$ に属する。$T^*$ の中の $x$ から $y$ への道は $X$ から $Y$ へ移るので、一方の端点が $X$ に、他方が $Y$ にある辺 $e$ を含む。$e\in D_T(f)$ であり、$e\in T^*$、$f\notin T^*$ なので $e\neq f$、したがって $e\notin T$ である。
$f$ はループでなく $f\notin T^*$ で、$e$ は $T^*$ における $f$ の基本閉路 $C_{T^*}(f)$ に属する。lem-mst-exchange を $T^*$ に当てると、$T'':=(T^*\setminus\{e\})\cup\{f\}$ は全域木である。3 により $w(f)\le w(e)$ なので $w(T'')\le w(T^*)$ であり、$T''$ も最小全域木である。ところが $f\in T$、$e\notin T$ なので $|T\cap T''|=|T\cap T^*|+1$ となり、$T^*$ の選び方に反する。$\square$

1：$F\subset T_0$ となる最小全域木 $T_0$ をとる。$e\in T_0$ なら $T_0$ が求めるものである。$e\notin T_0$ とする。$e$ は $S$ を横切るのでループでなく、端点 $x\in S$、$y\notin S$ を結ぶ $T_0$ の道は、$S$ を横切る辺 $f$ を含む。$f\in C_{T_0}(e)$ で $f\neq e$ であり、$F$ の辺は $S$ を横切らないので $f\notin F$ である。lem-mst-exchange により $T_1:=(T_0\setminus\{f\})\cup\{e\}$ は全域木で、$e$ の最小性から $w(e)\le w(f)$ なので $w(T_1)\le w(T_0)$ であり、$T_1$ は $F\cup\{e\}$ を含む最小全域木である。
2：$e$ を含まない最小全域木 $T_0$ があったとして、1 と同じく $f$ をとると、$f\neq e$ は $S$ を横切るので $w(e)< w(f)$ であり、$w(T_1)< w(T_0)$ となって矛盾する。$\square$

$e$ がループなら、全域木はループを含まないので主張は正しい。$e$ がループでなく、ある最小全域木 $T$ が $e$ を含むとする。$e$ の端点は $(V,T\setminus\{e\})$ の異なる成分に属する。$Z$ から $e$ を除いた部分は一方の端点から他方の端点への歩道なので、2 つの成分を結ぶ辺 $f\neq e$ を含み、$f\in D_T(e)$ である。thm-mst-optimality の 3 により $w(e)\le w(f)$ となるが、これは $w(f)< w(e)$ に反する。$\square$

$T\neq T'$ を最小全域木とし、$g\in T\setminus T'$ をとる。thm-mst-optimality の 3 ⇒ 1 の証明と同じく、$g$ の端点を結ぶ $T'$ の道の上に、$g\neq e\in D_T(g)\cap T'$ となる辺 $e$ がある。$T$ の切断の条件から $w(g)\le w(e)$ である。一方、$g\notin T'$ はループでなく、$e\in C_{T'}(g)$ なので、$T'$ の閉路の条件から $w(e)\le w(g)$ である。よって $w(e)=w(g)$ となり、重みが相異なることに反する。$\square$

「$F_k$ はある最小全域木に含まれる」を $k$ についての帰納法で示す。$k=0$ は正しい。$F_k=F_{k-1}$ なら明らかなので、$e_k$ を採用した場合を考える。$e_k$ の端点の一方を含む $(V,F_{k-1})$ の連結成分の頂点集合を $S$ とすると、$e_k$ は $S$ を横切り、$F_{k-1}$ の辺は $S$ を横切らない。
$S$ を横切る辺はすべて添字が $k$ 以上であることを示す。$j< k$ とする。$e_j$ を採用したなら $e_j\in F_{k-1}$ なので $S$ を横切らない。$e_j$ を捨てたなら、$e_j$ はループであるか、端点が $(V,F_{j-1})$ の同じ連結成分にあった。$F_{j-1}\subset F_{k-1}$ なので端点は $(V,F_{k-1})$ でも同じ成分にあり、いずれにせよ $S$ を横切らない。辺は重みの小さい順に並んでいるので、$e_k$ は $S$ を横切る辺のうち重みが最小である。cor-mst-cut の 1 により $F_k=F_{k-1}\cup\{e_k\}$ はある最小全域木に含まれる。
最後に $F_m$ が全域木であることを示す。$F_m$ は閉路をもたない。$(V,F_m)$ が連結でないとし、その連結成分の頂点集合 $S\neq V$ をとる。$G$ は連結なので $S$ を横切る辺があり、そのうち添字最小のものを $e_k$ とする。$e_k$ の端点は $(V,F_m)$ の異なる成分にあり、$F_{k-1}\subset F_m$ なので $(V,F_{k-1})$ でも異なる成分にある。よって $e_k$ は採用されて $e_k\in F_m$ となり、$S$ が $(V,F_m)$ の連結成分であることに反する。したがって $F_m$ は全域木である。$F_m$ はある最小全域木 $T_0$ に含まれ、どちらも辺は $n-1$ 本なので $F_m=T_0$ である。$\square$

「$(W_k,T_k)$ は木であり、$T_k$ はある最小全域木に含まれる」を $k$ についての帰納法で示す。$k=0$ では $(\{r\},\emptyset)$ は木で、$\emptyset$ はどの最小全域木にも含まれる。$k$ で成り立つとする。$T_k$ の辺は両端点が $W_k$ にあるので $W_k$ を横切らず、$e$ は $W_k$ を横切る辺のうち重みが最小なので、cor-mst-cut の 1 により $T_{k+1}=T_k\cup\{e\}$ はある最小全域木に含まれる。$(W_k,T_k)$ に新しい頂点 $v$ と、$v$ と $W_k$ を結ぶ辺 $e$ を加えたものは、連結で閉路をもたないので木である。
$k=n-1$ で $W_{n-1}=V$ なので、$T_{n-1}$ は全域木で、ある最小全域木 $T_0'$ に含まれる。どちらも辺は $n-1$ 本なので $T_{n-1}=T_0'$ である。$\square$

1 ⇒ 2：$u\neq v$ としてよい（$u=v$ なら $P_T(u,v)$ は長さ $0$ で、左辺は $-\infty$）。$P_T(u,v)$ の辺のうち重みが最大のもの $f$ をとる。$f$ は $u$ と $v$ を結ぶ $T$ の道の上にあるので、lem-mst-exchange の証明と同じく、$u$ と $v$ は $(V,T\setminus\{f\})$ の異なる成分にある。$Q$ は $u$ から $v$ へ進むので、2 つの成分を結ぶ辺 $e$、すなわち $e\in D_T(f)$ を通る。thm-mst-optimality の 3 により $\beta(P_T(u,v))=w(f)\le w(e)\le\beta(Q)$ である。
2 ⇒ 1：ループでない $e\notin T$ の端点を $x,y$ とし、$Q$ を $e$ 1 本だけの歩道 $x,e,y$ とすると、2 から $\beta(P_T(x,y))\le w(e)$ である。$C_T(e)$ の $e$ 以外の辺は $P_T(x,y)$ の辺なので、thm-mst-optimality の 2 が成り立ち、$T$ は最小全域木である。$\square$