散歩道の始点と終点が一致しているとき、 その散歩道は閉じている(closed)という。 1本以上の辺をもつ閉じた道を、閉路(circuit)と呼ぶ。 特にループや2本の多重辺は、それだけで閉路をなすことに注意する。
グラフ$G$の非連結化集合(disconnected set)とは、 それに含まれる辺をすべて除去すると、 $G$の成分の個数が増えるような辺の集合である。 どんな真部分集合も非連結化集合でないような非連結化集合を、 カットセット(cutset)と呼ぶ。
証明
$C_1$の辺に、$C_1$を巡回するように$e_1(=e),e_2,\ldots,e_{n'}$ と番号を付け、 この順序に従う向きを各辺に付ける。 また$C_2$の辺にも同様に $e'_1(=e),e'_2,\ldots,e'_{n}$ と番号を付け、 この順序に従う向きを各辺に考える。 ただし$e_1=e'_1(=e)$の向きは一致するようにする。
$e_1=e'_1(=e)$であり、 しかも$C_1$と$C_2$が異なる閉路であることから、
\[ e_{i}=e'_i\ (1\le \forall i < k)\,,\ e_{k}\ne e'_k \]
なる番号$k$ が存在する。
この$k$ に対して、$i > k$ かつ $e_i$ の上で定めた向きの 下での終点が$C_2$の頂点であるような番号$i$のうち、 最小のものを$m$とする。 $e_n$の終点が$e'_1$の始点、従って$C_2$の頂点であることから、 $m$は必ず存在する。
$e_m$の終点を終点とする$C_2$の辺を$e'_{m'}$とすると、
\[ e_k,\ldots,e_m,\,e'_{m'},\ldots,e'_k \]
が求める閉路になる。
\hfill(証明終了)
証明
辺$e$を含む成分に制限して考えれば、 始めから$G$は連結であるとしても一般性を失わない。
$(C_1\union C_2)\setminus\{e\}$が、 非連結化集合であることを示せば十分である。 背理法を用いる。 つまり
\[ G'=G\setminus ((C_1\union C_2)\setminus\{e\}) \]
が連結であると仮定して矛盾を導く。
仮定により$f\in C_1\setminus C_2$なる辺$f$ が存在する。 $G'$は連結なので、 $f$ に接続する2頂点$u$と$v$を結ぶ$G'$の道 $\alpha$ が存在する。 同様にして、 辺$g\in C_2\setminus C_1$と$g$に接続する2頂点を結ぶ $G'$の道 $\beta$ の存在がわかる。 明かに、$\alpha,\,\beta$は共に辺$e$を含む。
$\beta$ と$g$ によってできる閉路から辺$e$を取り除いて得られる、 $e$に接続する2頂点を結ぶ道を $\gamma$ とし、 $\alpha$ の中の$e$を $\gamma$ に置き換えて得られる散歩道を$\delta$ とする。 $\delta$ は、$G\setminus C_1$の散歩道になる。
カットセットの極小性により $C_1\setminus\{f\}$は非連結化集合ではないから、 $G'':=G\setminus (C_1\setminus\{f\})$は連結である。
$u,\,v$を非連結グラフ$G''':=G\setminus C_1$の異なる成分に属する2頂点とし、 $\epsilon$ を$u,\,v$を結ぶ$G''$の道とする。 明かに$\epsilon$ は$f$を含む。
$\epsilon$ の中の$f$を上の$\delta$で置き換えると、 頂点$u$と$v$を結ぶ$G'''$の中の散歩道が得られ、$u,v$の取り方と矛盾する。
\hfill(証明終了)
証明
$G\setminus C^*$の成分を$H_1,\,H_2$とする。
$C$が$H_1$または$H_2$だけに含まれるならば、 $C^*$と共通な辺は$0$本になり、主張が成り立つ。
$C$が$H_1$および$H_2$の両方の頂点を含む場合、 $C$の各辺に、$C$を巡回するような向きを与える。 $C\intersection C^*$は、$C$の辺で上の向きの下での始点が$H_1$の頂点、 終点が$H_2$の頂点であるもの全体$C_1$と、始点が$H_2$の頂点、 終点が$H_1$の頂点である辺全体$C_2$の、互いに素な部分集合の和になる。 $C$が閉路なので、$C_1$と$C_2$の辺数は一致しなければならない。
よって、$C\intersection C^*$の辺数は$2|C_1|$となり、偶数になる。
\hfill(証明終了)
証明
$|S|$に関する帰納法による。
$|S|=0$ つまり $S=\emptyset$のときは、 主張は明か。
$|S| > 0$のとき、もし$S$が閉路$C$を含むなら、 任意のカットセット$C^*$に対して、 上の定理により$|C^*\intersection C|$は偶数である。 従って、$|(S\setminus C)\intersection C^*|$も偶数である。
$|S\setminus C| < |S|$なので帰納法の仮定が適用できて、 $S\setminus C$は互いに素な閉路の和に分割できる。 従って$S$も互いに素な閉路の和になる。
$S$が全く閉路をもたないと仮定する。 $e$を$S$の任意の辺とし、$e$に接続する2頂点を$v_1,\,v_2$とする。 $G$の頂点で$S$に含まれ、 かつ辺$e$を含まない道で$v_1$と結ぶことのできるものの全体を$V_1$、 それ以外の頂点の全体を$V_2$とすると、 $V_1\intersection V_2=\emptyset$であり、さらに、 $S$が閉路を含まないから、$v_1\in V_1,\;v_2\in V_2$である。
そこで$V_1,\,V_2$の両方の頂点に接続する$G$の辺の全体を$K$とすると、 $K$は辺$e$を含む非連結化集合になる。 $V_1,\,V_2$の定義により、 $e\in C^*\subset K$なるカットセット$C^*$が存在する。 明かに$C^*\intersection S=\{e\}$、 つまり$|C^*\intersection S|$が奇数である$1$になり、仮定に矛盾する。
よって共通な辺を偶数本もつならば、$S$は互いに素な閉路に分割できる。
\hfill(証明終了)