連結グラフ$G$に対して、頂点集合が$G$と一致し閉路を含まない連結部分グラフを、 $G$の全域木(spanning tree)と呼ぶ。
$G$が閉路を含むとき、 その閉路の1本の辺を除去しても残ったグラフは連結である。 この手続きを閉路が無くなるまで繰り返すことにより、$G$の全域木を得る。 つまり$G$は必ず全域木をもつ。
$G$が連結とは限らない一般のグラフの場合、$G$の各成分の全域木の和として 表わされる部分グラフを、$G$の全域林(spanning forest)と呼ぶ。 全域林の辺の本数を、 $G$のカットセット階数(cutset rank)と呼ぶ。
全域林の全体は、 閉路を含まない部分グラフの中で極大なもの全体と一致する。
ここで全域林の2つの性質をあげておく。 ただし定理において全域林$T$の補グラフとは、 グラフ$G$から$T$の辺を除去して得られるグラフのことである。
{\rm (i)} $G$ のすべてのカットセットは$T$と共通な辺をもつ。
{\rm (ii)} $G$のすべての閉路は$T$の補グラフと共通な辺をもつ。
証明
(i) $C^*$を$G$のカットセットとする。 $C^*$を$G$から除去すると、 $G$のある成分が2つの部分グラフに分離する。 それらを$H$と$K$とする。
$T$は全域林だから、 $H$の頂点と$K$の頂点を結ぶ辺が$T$に含まれている。 その辺が$T$との共通辺になる。
(ii) $C$は$G$の閉路とし、$T$の補グラフと共通な辺をもたないと仮定する。 このとき、$C$は$T$に含まれてしまい、$T$が閉路を含むことになる。 これは$T$が全域林という仮定と矛盾する。
よって$G$のすべての閉路は$T$の補グラフと共通な辺をもつ。
\hfill(証明終了)