2-2 全域木と切断・閉路の性質

spanning tree $T$ があれば、$T$ 内のpathは $G$ のpathでもあるため、$G$ は連結です。
逆に $G$ が連結とします。$G$ の辺をすべて残した状態から、cycleがある限りそのcycle上の辺を一本削除します。cycle上の辺 $e=uv$ を削除しても、cycleの残りが $u$ から $v$ への別のpathを与えるため、任意のwalkで $e$ を使う箇所をそのpathへ置き換えられます。従って連結性は保たれます。
辺数は有限なので操作は停止します。停止時の部分グラフは全頂点を含み、連結でcycleをもちません。従って木であり、$G$ のspanning treeです。□

1から2を示します。木の任意の辺はbridgeです。実際、辺 $uv$ を除いても $u,v$ 間のpathが残れば、そのpathと $uv$ がcycleを作ります。従ってどの辺を削除しても非連結です。
1から3を示します。木はcycleをもちません。$H$ にない $G$ の辺 $e=uv$ を加えると、木内の唯一の $u$--$v$ pathと $e$ がcycleを作ります。
2から1を示します。$H$ にcycleがあれば、その上の辺を一本削除しても連結性が保たれ、2に反します。従って $H$ は連結でcycleをもたない木です。
3から1を示します。もし $H$ が非連結なら、$G$ は連結なので異なる $H$-成分を結ぶ辺 $e\in E(G)\setminus E(H)$ があります。この辺を加えても異なる成分を一本で結ぶだけでcycleはできず、3に反します。従って $H$ は連結であり、cycleをもたないので木です。□

$T$ 自身はcycleをもたないため、$T+e$ のcycleは新しい辺 $e=uv$ を含まなければなりません。$e$ をcycleから除くと、残りは $T$ 内の $u$--$v$ pathです。木内のpathは一意なので、それは $C_T(e)$ を定義したpathに限られます。従ってcycleは一つだけです。□

$f\in C_T(e)$ とします。$T+e$ の唯一のcycleは $C_T(e)$ なので、その上の $f$ を除くとcycleがなくなります。またcycleから一本を除いた残りにより $f$ の両端は依然として結ばれているため、$T+e-f$ は連結です。全頂点を含む連結acyclic graphなのでspanning treeです。
逆に $f\notin C_T(e)$ とします。$T+e$ にある唯一のcycle $C_T(e)$ は $f$ を含まないため、$f$ を除いてもそのcycleが残ります。従って $T+e-f$ は木ではありません。□

$x,y$ が $T-f$ でも同じ成分にあれば、$f$ を使わない $x$--$y$ pathがあり、それと $f$ がcycleを作るので矛盾です。
任意の頂点 $v$ を取ります。$T$ 内の $v$--$x$ pathが $f$ を使わなければ $v$ は $x$ の成分に属します。使うなら、そのpathは $f=xy$ を一度通り、$v$ から $y$ までの部分は $f$ を使わないので $v$ は $y$ の成分に属します。従って全頂点はこの二成分のどちらかに入り、成分はちょうど二つです。□

$T-f$ の二成分を $A_f$ とその補集合とします。$e\in D_T(f)$ なら $e$ は二成分を結ぶので、$T-f+e$ は連結です。その辺数は $|V(T)|-1$ のままなので、木の特徴づけによりspanning treeです。
$e\notin D_T(f)$ なら $e$ の両端は同じ成分にあります。従って他方の成分との間に辺は加わらず、$T-f+e$ は非連結です。ゆえにspanning treeではありません。□

$f\in C_T(e)$ ならcycle交換条件により $T+e-f$ はspanning treeです。辺の加減は可換なので $T-f+e$ もspanning treeであり、cut交換条件から $e\in D_T(f)$ です。
逆に $e\in D_T(f)$ ならcut交換条件から $T-f+e$ はspanning treeです。従って $T+e-f$ もspanning treeで、cycle交換条件から $f\in C_T(e)$ です。□

$T_1-e$ の二成分の頂点集合を $A$ と $V\setminus A$ とします。$e$ の両端は異なる側にあります。
$T_2+e$ の基本cycle $C_{T_2}(e)$ を考えます。このcycleから $e$ を除いた $T_2$ 内のpathは、$e$ の一端から他端へ進むのでcut $\delta_G(A)$ を少なくとも一本横切ります。その横切る辺を $f$ とします。
$T_1$ では $e$ が二側を結ぶ唯一の木辺です。従って $f\ne e$ が $T_1$ にも属していれば、$T_1-e$ の二成分を $f$ が結んでしまい矛盾です。よって $f\in E(T_2)\setminus E(T_1)$ です。
$f$ は $T_1-e$ の二成分を結ぶので、cut交換条件から $T_1-e+f$ はspanning treeです。また $f$ は $C_{T_2}(e)$ 上にあるので、cycle交換条件から $T_2+e-f$ もspanning treeです。□

二つのspanning tree $T,T'$ を取ります。$T=T'$ なら何もする必要はありません。異なるなら $e\in E(T)\setminus E(T')$ を一つ選びます。対称交換定理により、ある $f\in E(T')\setminus E(T)$ と交換して
$$ T_1=T-e+f $$
をspanning treeにできます。この交換で $T'$ と共通する辺が一本増えます。
異なる辺は有限本なので、この操作を繰り返すと有限回で $T'$ に到達します。各一歩が一辺交換なので、交換グラフ内のpathが得られます。□

三角形 $1,2,3,1$ から辺13を削除します。残る辺は $12,14,23,24,34$ で、例えば1から2を経て3へ行け、4へは14で行けるので連結です。
残るcycle $1,2,4,1$ から24を削除します。辺は $12,14,23,34$ で、path $2,1,4,3,2$ が全頂点を結ぶので連結です。
この四辺にはcycle $1,2,3,4,1$ があるので34を削除します。残る
$$ \{12,14,23\} $$
は全4頂点を含み、1を中心に2,4へ、2を経て3へ到達できる連結グラフです。3辺しかなくcycleをもたないのでspanning treeです。□

無向辺41は14と同じで既に $T'$ に入っています。従って非木辺は23と34だけです。
23の両端を結ぶ $T'$ 内pathは $2,1,3$ なので
$$ C_{T'}(23)=\{23,12,13\}. $$
34の両端を結ぶpathは $3,1,4$ なので
$$ C_{T'}(34)=\{34,13,14\}. $$
入力の辺を無向か有向か確認し、同じ辺を二重に数えないことが重要です。□

12を除くと $\{2\}$ と $\{1,3,4\}$ に分かれます。元のグラフで2から外へ出る辺は12,23なので
$$ D_{T'}(12)=\{12,23\}. $$
同様に13を除くと $\{3\}$ が分かれ、3に接続する元の辺は13,23,34なので
$$ D_{T'}(13)=\{13,23,34\}. $$
14を除くと $\{4\}$ が分かれ、接続辺は14,34なので
$$ D_{T'}(14)=\{14,34\}. $$
例えば $13\in C_{T'}(23)$ と $23\in D_{T'}(13)$ が対応しています。□

cycle側では
$$ C_T(13)=\{13,12,23\} $$
であり34を含みません。従って13を加えて34を除いてもcycle $1,2,3,1$ が残ります。
cut側では、$T-34$ の成分は $\{1,2,3\}$ と $\{4\}$ です。辺13の両端はともに前者にあるため、このcutを横切りません。従って13を加えても頂点4は切り離されたままです。実際、得られるグラフは一方にcycleをもちながら非連結です。□

$T_1-23$ の成分は $\{1,2\}$ と $\{3,4\}$ です。$T_2$ で23の両端2,3を結ぶpathは
$$ 2,1,4,3 $$
なので、$T_2+23$ の基本cycleは $23,12,14,34$ です。このpathで二成分を横切る辺として $f=14$ を選べます。
交換後は
$$ T_1-23+14=\{12,14,34\}, $$
$$ T_2-14+23=\{12,23,34\}. $$
この例では二つの木がそのまま入れ替わります。どちらも連結な3辺グラフなのでspanning treeです。□

1から2。$e$ を含まないspanning treeがあれば、その木内で $e$ の両端を結ぶpathがあり、$G-e$ でも両端がつながります。spanning treeは全頂点を結ぶので $G-e$ も連結となり、$e$ がbridgeであることに反します。
2から3。spanning tree $T$ を一つ取ると2により $e\in T$ です。$D_T(e)$ に別の辺 $f$ があれば、cut交換条件により $T-e+f$ は $e$ を含まないspanning treeとなり2に反します。従って $D_T(e)=\{e\}$ です。
3から1。$T-e$ の二成分間を結ぶ $G$ の辺は $D_T(e)$ の辺そのものです。それが $e$ だけなら、$G-e$ では二成分を結ぶ辺がなく非連結です。従って $e$ はbridgeです。□