1-3 切断点・橋・ブロック

まず1から3を示します。$e$ がbridgeなのに、$e$ を使わない $u$–$v$ path $P$ があると仮定します。$G-e$ でも $u,v$ は $P$ で結ばれます。
$G$ の任意のpathが $e$ を使う場合、その $e$ の部分を $P$ へ置き換えれば、$G-e$ のwalkになります。閉じた部分を削れば同じ両端を結ぶpathが得られます。従って $G$ で同じ成分にあった任意の二頂点は $G-e$ でも同じ成分にあり、成分数は増えません。これはbridgeに矛盾します。ゆえに $e$ を使わない $u$–$v$ pathはありません。
3から2を示します。$e$ を含むcycleがあれば、そのcycleから $e$ を除いた残りは $e$ を使わない $u$–$v$ pathです。3に矛盾します。
2から1を示します。$e$ がbridgeでないと仮定すると、$G-e$ でも $u,v$ は同じ成分に属します。従って $G-e$ に $u$–$v$ path $P$ があります。$P$ に辺 $e$ を加えるとcycleが得られ、$e$ がcycleに属さないという2に矛盾します。□

木はcycleをもたないので、bridgeとcycleの同値条件からすべての辺がbridgeです。
逆にすべての辺がbridgeなら、どの辺もcycleに属しません。cycleが一つでもあれば、そのcycle上の辺はbridgeでなくなるので矛盾します。連結でcycleをもたないため $T$ は木です。□

$v$ がcut vertexなら、$G-v$ は少なくとも二つの成分をもちます。異なる成分から $x,y$ を一つずつ取ります。$G$ の $x$–$y$ pathが $v$ を通らなければ、そのpathは $G-v$ にも残り、$x,y$ が同じ成分に属してしまいます。従ってすべてのpathが $v$ を通ります。
逆に、すべての $x$–$y$ pathが $v$ を通るとします。$G-v$ に $x$–$y$ pathがあれば、それは $G$ で $v$ を通らないpathなので矛盾します。従って $x,y$ は $G-v$ の異なる成分に属し、成分数が増えます。ゆえに $v$ はcut vertexです。□

葉 $\ell$ を削除しても、残る任意の二頂点間の一意なpathは $\ell$ を内部に含まないため残ります。従って $T-\ell$ は連結で、葉はcut vertexではありません。
葉でない頂点 $v$ は少なくとも二つの隣接頂点 $x,y$ をもちます。木で $x$ から $y$ への一意なpathは $x-v-y$ を含みます。従ってすべての $x$–$y$ pathが $v$ を通り、path特徴づけから $v$ はcut vertexです。□

辺 $e=uv$ がcycleに属さないと仮定します。bridgeとcycleの同値条件から $e$ はbridgeです。$G-e$ の $u$ を含む成分を $A$、$v$ を含む成分を $B$ とします。
$G$ は3頂点以上なので、$A-\{u\}$ または $B-\{v\}$ の少なくとも一方が空でありません。
$A-\{u\}\ne\varnothing$ なら、$u$ を削除すると $A-\{u\}$ の頂点は $B$ の頂点から切り離されるため $u$ はcut vertexです。$A=\{u\}$ なら $B-\{v\}\ne\varnothing$ であり、$v$ を削除すると $u$ は $B-\{v\}$ から切り離されるため $v$ がcut vertexです。いずれも2-connectedに矛盾します。従って $e$ はcycleに属します。□

二つは頂点を共有するので合併は連結です。
任意の頂点 $v$ を削除します。$H_1,H_2$ は相異なる共有頂点を二つ以上もつため、$v$ を削除しても共有頂点が少なくとも一つ残ります。$H_i$ はcut vertexをもたないので、$H_i-v$ は空でない限り連結です。二つの残存graphは残った共有頂点で交わるため、その合併
$$ (H_1\cup H_2)-v $$
も連結です。従って合併にcut vertexはありません。□

一辺とその両端からなるgraphは連結でcut vertexをもちません。$G$ は有限なので、この部分graphを包含するものの中から極大なものを取れます。従って各辺は少なくとも一つのblockに属します。
一辺が二block $B_1,B_2$ に属すれば、その両端という相異なる二頂点を共有します。合併補題により $B_1\cup B_2$ は連結でcut vertexをもちません。各blockの極大性から $B_1=B_2$ です。よって各辺が属するblockは一意です。同じ合併補題により、相異なるblockが二頂点以上を共有できないことも従います。
最後に、相異なるblock $B_1,B_2$ が $v$ を共有し、$v$ が $G$ のcut vertexでないと仮定します。$B_1-v$ の頂点 $x$ と $B_2-v$ の頂点 $y$ を取れます。$G-v$ は連結なので $x$–$y$ pathがあります。そのうち、$B_1$ を最後に出た点から $B_2$ へ最初に入る点までの部分pathを $P$ と取れば、$P$ の内部は $B_1\cup B_2$ と交わりません。
$H=B_1\cup P\cup B_2$ を考えます。$v$ を削除しても $P$ が $B_1-v$ と $B_2-v$ を結びます。$P$ の内部頂点を一つ削除しても、切れた二側は $B_1$、共有頂点 $v$、$B_2$ を通る別経路で結ばれます。$B_1$ または $B_2$ の頂点を削除しても、各blockからその頂点を除いた部分は連結であり、残りは $v$ と $P$ を介してつながります。従って $H$ はcut vertexをもちません。
$H$ は二blockを真に含む連結部分graphなので、blockの極大性に矛盾します。よって $v$ は $G$ のcut vertexです。□

$e$ がbridgeなら $K_2$ 自身はcut vertexをもちません。もしそれを真に含むblock $B$ があれば、$B$ は3頂点以上でcut vertexをもちません。従って2-connectedで、先の命題により $e$ は $B$ のcycleに属します。これは $e$ が $G$ のbridgeであることに矛盾します。ゆえに $K_2$ は極大でblockです。
逆に $e$ がbridgeでないなら、$e$ はあるcycle $C$ に属します。cycleは連結でcut vertexをもたず、$e$ だけの $K_2$ を真に含みます。従って $K_2$ は極大でなく、blockではありません。□

まず連結性を示します。二つのblock $B,B'$ を取ります。それぞれの辺または頂点を結ぶ $G$ のpathを一つ取ります。そのpathの各辺は一意なblockに属します。pathに沿ってblockが変わる箇所では、連続する二辺の共有頂点が二つの異なるblockに属します。blockの基本性質により、その共有頂点はcut vertexです。従ってpath上のblock列とcut vertex列が $BC(G)$ で $B$ から $B'$ へのwalkを与えます。cut vertex nodeもそれを含むblock nodeに隣接するので、$BC(G)$ は連結です。
次にcycleがないことを示します。cycleがあると仮定し
$$ B_1-v_1-B_2-v_2-\cdots-B_k-v_k-B_1 $$
と書きます。ここで $B_i$ は相異なるblock、$v_i$ は相異なるcut vertexです。合併
$$ H=B_1\cup\cdots\cup B_k $$
を考えます。
任意の頂点 $x$ を削除します。各 $B_i-x$ は空でない限り連結です。cycle上で一つの接続点 $x=v_i$ が失われても、$B_i$ と $B_{i+1}$ は反対向きに残りのblockと接続点をたどって結ばれます。$x$ が一つのblock内部の頂点なら、そのblockを削除後も連結なまま、cycle上の両隣との接続が保たれます。従って $H-x$ は連結で、$H$ はcut vertexをもちません。
$H$ は各 $B_i$ を真に含む連結部分graphです。これはblockの極大性に矛盾します。ゆえに $BC(G)$ はcycleをもちません。連結でcycleをもたないので木です。□

$x$ と $C_5$ の頂点 $v$ を結ぶ新しい辺 $xv$ はどのcycleにも属しません。従ってbridgeです。$C_5$ の五辺はcycle上にあるのでbridgeではありません。
$v$ を削除すると $x$ が孤立し、cycleの残りはpathとして連結なので成分が二つになります。従って $v$ はcut vertexです。
$x$ を削除しても $C_5$ が残り連結です。$v$ 以外のcycle頂点を一つ削除しても、残るcycle部分はpathであり $v$ を通じて $x$ と結ばれます。従って他にcut vertexはありません。□

辺 $uv$ を削除すると $G_1,G_2$ の間に辺がなくなり、$G$ は二成分へ分かれます。従って定義から $uv$ はbridgeです。
また $uv$ を含むcycleがあるとすれば、cycleから $uv$ を除いた残りが $u$–$v$ pathになります。しかし $G_1,G_2$ を結ぶ辺は $uv$ だけなので、そのようなpathは存在しません。bridgeとcycleの同値条件からもbridgeです。□

中心頂点を $c$、葉を $\ell_1,\ldots,\ell_6$ とします。木の非葉頂点はcut vertexなので、cut vertexは $c$ だけです。木の全辺はbridgeなので、六辺 $c\ell_i$ がすべてbridgeです。
各bridgeは一辺blockなので、blockは
$$ B_i=K_2[\{c,\ell_i\}] \qquad(1\le i\le6) $$
の六つです。
block–cut treeは中心にcut vertex node $c$ を置き、その周囲に六つのblock node $B_i$ を結んだstar $K_{1,6}$ です。元の葉はblock–cut treeのnodeにはならないことに注意します。□

$v$ を削除すると、各三角形の残りの一辺が別々の成分になるので $v$ はcut vertexです。他の頂点を削除しても二つの三角形は $v$ を通じてつながるため、他にcut vertexはありません。
すべての辺はどちらかの三角形cycle上にあるためbridgeはありません。二つの三角形がそれぞれblockです。両者を合わせると $v$ がcut vertexになるので一つのblockにはなりません。
block–cut treeは
$$ B_1-v-B_2 $$
という3頂点pathです。□

$G$ は連結なので孤立頂点はなく、各頂点次数は少なくとも1です。
次数1の頂点 $u$ があり、その唯一の隣接頂点を $v$ とします。$G$ は3頂点以上なので $u,v$ 以外の頂点が存在します。$v$ を削除すると $u$ は孤立し、他の頂点から切り離されます。従って $v$ はcut vertexとなり、2-connectedに矛盾します。
よって次数0または1の頂点はなく、$\delta(G)\ge2$ です。□

block–cut tree $BC(G)$ で、cut vertex node $v$ の次数は、$v$ を含むblock数 $r$ です。木から次数 $r$ の頂点 $v$ を削除すると、$r$ 個の連結成分に分かれます。
各成分側に属するblockの頂点は、元のgraph $G-v$ でもblockの内部と共有cut vertexを通じて互いに結ばれます。異なる側の頂点を結ぶ $G-v$ のpathがあれば、そのpathに沿うblock列が $BC(G)-v$ の異なる成分を結ぶことになり矛盾します。
従って $BC(G)-v$ の $r$ 成分と $G-v$ の連結成分が一対一に対応し
$$ c(G-v)=r. $$
□