ブロック(グラフ)

頂点が 1 個なら $K_1$、2 個なら連結な単純グラフは $K_2$ である。3 個以上なら、上で見たように各 $H-v$ は連結なので 2-連結である。後半の 3 つの場合を確かめる。

$H:=H_1\cup H_2$ とする。$H_1,H_2$ は連結で頂点を共有するので $H$ は連結である。$v\in V(H)$ をとる。$v\notin V(H_i)$ なら $H_i-v=H_i$ は連結であり、$v\in V(H_i)$ なら $H_i$ は 2 頂点以上をもつので、定義の直後の注意により $H_i-v$ は連結である。共有する 2 頂点のうち少なくとも一方 $w$ は $v$ と異なり、$w$ は $H_1-v$ と $H_2-v$ の両方に属する。$H-v=(H_1-v)\cup(H_2-v)$ なので $H-v$ は連結であり、$\omega(H-v)=1=\omega(H)$ となる。よって $v$ は $H$ の切断点でない。$\square$

2． ブロック $B_1,B_2$ が 2 個以上の頂点を共有すれば、lem-blk-union により $B_1\cup B_2$ は連結で切断点をもたず、$B_1$ と $B_2$ を含む。極大性により $B_1=B_1\cup B_2=B_2$ である。
1． そのような部分グラフ $H$ を含むブロックは、定義の後の注意により存在する。$H$ を含むブロックが 2 つあれば、それらは $H$ の 2 個以上の頂点を共有するので、2 により一致する。辺は $K_2$ として 2 頂点をもつので、ちょうど 1 つのブロックに含まれる。各頂点・各辺がブロックに含まれるので、$G$ はブロックの和である。
3． 閉路 $C$ は連結で、1 頂点を除くと道が残るので切断点をもたず、3 個以上の頂点をもつ。1 により $C$ はちょうど 1 つのブロックに含まれる。
4．（2 つ以上のブロック ⇒ 切断点） $v\in V(B_1)\cap V(B_2)$、$B_1\ne B_2$ とする。頂点 1 個のブロックは孤立点であり（prop-blk-shape）、孤立点を含むブロックはそれ 1 つだけなので、$B_1,B_2$ はどちらも 2 個以上の頂点をもつ。$B_i$ は連結なので、$v$ に $B_i$ の中で隣接する頂点 $x\in V(B_1)$、$y\in V(B_2)$ がある。2 により $V(B_1)\cap V(B_2)=\{v\}$ なので $x\ne y$ である。$G-v$ に $x$ と $y$ を結ぶ道 $P$ があると仮定すると、$v$、$x$、$P$、$y$、$v$ とたどる閉路 $C$ ができ、$C$ は辺 $vx$ と $vy$ を含む。3 により $C$ はある 1 つのブロック $B$ に含まれ、1 により辺 $vx$ を含むブロックは $B_1$ だけ、$vy$ を含むブロックは $B_2$ だけなので $B_1=B=B_2$ となり、矛盾する。よって $x,y$ は $G-v$ の異なる連結成分に属する。$G$ では $x,y$ は $v$ を通って同じ成分 $K$ に属するので、$K-v$ は 2 つ以上の成分をもち、$v$ は切断点である。
4．（切断点 ⇒ 2 つ以上のブロック） $v$ を切断点とし、$v$ を含む $G$ の連結成分を $K$ とする。$K-v$ は 2 つ以上の連結成分をもち、$K$ は連結なので、各成分は $v$ に隣接する頂点を含む。異なる成分から $v$ の隣接頂点 $x,y$ をとり、辺 $vx,vy$ を含むブロックを $B_x,B_y$ とする。$B_x=B_y=:B$ なら、$B$ は $v,x,y$ を含み連結で切断点をもたないので $B-v$ は連結であり、$G-v$ に $x$ と $y$ を結ぶ道がある。これは矛盾なので $B_x\ne B_y$ であり、どちらも $v$ を含む。
5． 4 の前半そのものである。$\square$

1． $e=uv$ とし、$u,v$ と異なる頂点 $w$ をとる（頂点は 3 個以上ある）。$H-u$ は連結なので、$u$ 以外の各頂点は $H-u$ の中で $w$ と道で結ばれ、その道は $u$ を通らないので $e$ を使わない。同様に $u$ は $H-v$ の中で $e$ を使わずに $w$ と結ばれる。よって $H-e$ のすべての頂点が $w$ と結ばれ、$H-e$ は連結である。
2． $u,v$ が隣接しないとき、$u,v$ 以外の全頂点を除けば $u$ と $v$ は切り離されるので、$u,v$ を切り離す頂点集合（$u,v$ を含まない）は存在し、$H$ は 1 頂点以下を除いても連結なので、そのような集合はどれも 2 個以上の頂点をもつ。連結度(グラフ) の定理「Mengerの定理（頂点版）」により、内部の頂点を共有しない $u$–$v$ 道が 2 本あり、つなぐと $u,v$ を通る閉路になる。$u,v$ が隣接するとき、1 により辺 $uv$ は橋でないので、閉路 の定理「閉路に含まれる辺と橋」により $uv$ を含む閉路があり、それは $u,v$ を通る。$\square$

$e,f$ をともに含む閉路 $C$ があれば、thm-blk-structure の 3 により $C$ はあるブロック $B$ に含まれ、$e,f$ は $B$ の辺である。
逆に $e=ab$、$f=cd$ が同じブロック $B$ の辺だとする。$B$ は 2 本の辺をもつので頂点が 3 個以上あり、prop-blk-shape により 2-連結である。$B$ の辺 $e$ を新しい頂点 $s$ で、$f$ を新しい頂点 $t$ で細分したグラフ $B'$ を考える（$e$ を道 $a,s,b$ に、$f$ を道 $c,t,d$ に置き換える）。$B'$ が 2-連結であることを確かめる。頂点は 5 個以上ある。$B'-s$ は $B-e$ の辺 $f$ を細分したものであり、lem-blk-two-connected の 1 により $B-e$ は連結なので、$B'-s$ も連結である。$B'-t$ も同様である。$B$ の頂点 $x$ を除くと、$B-x$ は連結である。$x\notin\{a,b\}$ なら、$B'-x$ では $B-x$ の辺 $e$ が道 $a,s,b$ に置き換わっているだけである。$x\in\{a,b\}$ なら、$e$ は $B-x$ になく、$s$ は $a,b$ のうち $x$ でない一方とだけ隣接して残る。$f$ と $t$ も同様なので、$B'-x$ は $B-x$ の残った辺 $e,f$ を細分し、端点を 1 つ失った細分点を 1 本の辺でつないだグラフであり、連結である。
lem-blk-two-connected の 2 により、$s$ と $t$ は $B'$ のある閉路 $C'$ にのる。$s$ の隣接頂点は $a,b$ だけなので $C'$ は $a,s,b$ と進み、同様に $c,t,d$ と進む。$C'$ の中の $a,s,b$ を辺 $ab$ に、$c,t,d$ を辺 $cd$ に戻すと、頂点の重複のない閉じた道ができる。その頂点は $a,b,c,d$（相異なる 2 辺の端点なので 3 個以上）を含むので、これは $e,f$ を含む $G$ の閉路である。
最後の主張は、thm-blk-structure の 1 により各辺がちょうど 1 つのブロックに含まれることと、前半の同値から従う。$\square$

連結であること． $G=K_1$ ならブロックは $G$ 自身だけで切断点はなく、$T$ は 1 頂点の木である。以下 $G$ は 2 頂点以上とすると、孤立点がないので、各ブロックは 2 頂点以上をもつ。各切断点 $a$ は、$a$ を含むブロックと $T$ で隣接するので、任意の 2 つのブロック $B,B'$ が $T$ の歩道で結ばれることを示せばよい。$x\in V(B)$、$y\in V(B')$ をとり、$G$ の道 $x=x_0,x_1,\dots,x_m=y$ をとる。辺 $x_{j-1}x_j$ を含むブロックを $C_j$ とし（$1\le j\le m$）、$C_0:=B$、$C_{m+1}:=B'$ とおく。$0\le j\le m$ について、$C_j$ と $C_{j+1}$ はともに $x_j$ を含む。$C_j\ne C_{j+1}$ なら、thm-blk-structure の 5 により $x_j$ は切断点で、$T$ の中で $C_j$ と $C_{j+1}$ の両方に隣接する。よって $C_0,C_1,\dots,C_{m+1}$ をこの順にたどる $T$ の歩道がある（$m=0$ のときも同じ議論である）。
閉路がないこと． $T$ は 2 部グラフなので、閉路があるとすれば、相異なるブロック $B_1,\dots,B_k$ と相異なる切断点 $a_1,\dots,a_k$（$k\ge2$）で、$a_i\in V(B_i)\cap V(B_{i+1})$（添字は $k$ を法として読む）となるものがある。$U:=B_1\cup\dots\cup B_k$ とおく。$B_i$ は相異なる 2 頂点 $a_{i-1},a_i$ を含む。$B_i$ と $B_{i+1}$ は $a_i$ を共有するので、$U$ は連結である。$U$ の頂点 $v$ をとる。各 $B_i-v$ は連結で空でない。$a_i\ne v$ である添字 $i$ では $B_i-v$ と $B_{i+1}-v$ は $a_i$ を共有し、$a_i=v$ となる $i$ は高々 1 つである。よって $B_1-v,\dots,B_k-v$ は、環状につながる $k$ 個の連結な部分から高々 1 か所のつながりを外した形でつながっており、$U-v$ は連結である。したがって $U$ は連結で切断点をもたない。$U$ は $B_1$ を含むので、極大性により $U=B_1$、とくに $B_2\subset B_1$ である。$B_2$ の極大性により $B_2=B_1$ となり、矛盾する。$\square$

1． $T$ は 2 頂点以上の木なので、木(グラフ) の命題「木の三つの基本性質」により葉を 2 つ以上もつ。切断点 $a$ の $T$ での次数は $b(a)$ で、thm-blk-structure の 4 により $b(a)\ge2$ なので、葉はブロックである。葉のブロックは $T$ でちょうど 1 つの切断点と隣接する。
2． ブロックは連結なので、$G$ のある連結成分に含まれる。連結成分 $K$ を 1 つとると、$G$ のブロックで $K$ に含まれるものは $K$ のブロックであり、その逆も成り立ち、$K$ の頂点が $G$ の切断点であることと $K$ の切断点であることは同値である（どちらも定義が $K$ の中で決まる）。$K$ の切断点の集合を $A_K$、ブロックの集合を $\mathcal{B}_K$ とすると、$K$ のブロック・切断点木は $|A_K|+|\mathcal{B}_K|$ 個の頂点と $\sum_{a\in A_K}b(a)$ 本の辺をもつ。木の辺数は頂点数より 1 少ないので（同じ命題の 3）、
$$ |\mathcal{B}_K|=1+\sum_{a\in A_K}\bigl(b(a)-1\bigr) $$
である。切断点でない頂点では、thm-blk-structure の 1 と 4 により $b(v)=1$ なので、和を $K$ のすべての頂点にわたってとってよい。成分について足し合わせると主張を得る。$\square$

ブロックは部分グラフなので、彩色数 の命題「部分グラフと連結成分」の 1 により $\chi(G)\ge\max_B\chi(B)=:k$ である。同じ命題の 2 により、各連結成分を $k$ 色で彩色できれば十分なので、$G$ は連結としてよい。ブロック・切断点木 $T$（thm-blk-tree）のブロック $B_0$ を 1 つ選び、各ブロックを $T$ での $B_0$ からの距離の小さい順に並べる（同じ距離のものの順は任意）。$B\ne B_0$ について、$T$ の $B$ から $B_0$ への道で $B$ の次の頂点（切断点）を $a_B$、その次の頂点（ブロック）を $B$ の親とよぶ。親は $B$ より $B_0$ に近いので $B$ より前に並ぶ。
$B$ より前に並ぶブロック $B'$ が $B$ と頂点 $c$ を共有すれば $c=a_B$ であることを示す。$c$ は thm-blk-structure の 5 により切断点で、$T$ において $B$ と $B'$ の両方に隣接する。$B$ の隣接頂点のうち $B_0$ に近いのは $a_B$ だけなので、$c\ne a_B$ なら $c$ は $B$ より $B_0$ から 1 だけ遠く、$c$ の隣接頂点で $B_0$ に近いのは $B$ だけなので、$B'$ は $c$ よりさらに遠い。これは $B'$ が $B$ より前に並ぶことに反する。
並べた順に、各ブロック $B$ を $k$ 色で彩色する。$B_0$ は $\chi(B_0)\le k$ 色で塗る。$B\ne B_0$ では、$\chi(B)\le k$ 色の彩色を 1 つとり、色の名前を入れ替えて、$a_B$ に既に付いている色と一致させる。上で示したことにより、$B$ の頂点のうち既に色が付いているのは $a_B$ だけなので、矛盾なく色が決まる。こうしてすべての頂点に色が付き、各辺はある 1 つのブロックの辺なので（thm-blk-structure の 1）、両端の色は異なる。よって $\chi(G)\le k$ である。$\square$