道と連結性 ― グラフの「つながり」を定式化する

道・径路・閉路の定義，連結成分，連結度$\kappa(G)$，切断点と橋，二部グラフ判定定理，Mengerの定理を証明する．

2026年2月27日

1 歩道・道・閉路

定義 1 (歩道・道・閉路).

グラフ

G

における頂点の列

v_{0}, v_{1}, \dots, v_{k}

（各

{v_{i - 1}, v_{i}} \in E (G)

）を歩道（walk）という．

k

をその長さという．

辺がすべて相異なる歩道を径路（trail）という．
頂点がすべて相異なる歩道を道（path）という．
$v_{0} = v_{k}$ かつ $k \geq 1$ である径路を閉径路（closed trail）という．
$v_{0} = v_{k}$ かつ $v_{0}, v_{1}, \dots, v_{k - 1}$ がすべて相異なり， $k \geq 3$ である歩道を閉路（cycle）という．

長さ

k

の道・閉路をそれぞれ

P_{k}

，

C_{k}

とも書く．

道 $P_{4}$ （左）と閉路 $C_{4}$ （右）の例：

注意 2.

道の定義に注意が必要である．道では頂点が相異なるので辺も自動的に相異なる．また閉路の条件

k \geq 3

は，単純グラフにおいて

C_{1}

，

C_{2}

が存在しないことに対応する．

補題 3.

グラフ

G

において頂点

u

から

v

への歩道が存在するならば，

u

から

v

への道が存在する．

証明.

u

から

v

への歩道のうち長さが最小のものを

W = v_{0}, v_{1}, \dots, v_{k}

（

v_{0} = u

，

v_{k} = v

）とする．

W

に頂点の重複

v_{i} = v_{j}

（

i < j

）があれば，

v_{0}, \dots, v_{i}, v_{j + 1}, \dots, v_{k}

はより短い歩道であり矛盾．よって

W

は道である． □

2 連結性と連結成分

定義 4 (連結).

グラフ

G

が連結（connected）であるとは，任意の2頂点

u, v \in V (G)

に対して

u

から

v

への道が存在することをいう．

頂点 $u$ と $v$ の間に道が存在するという関係は同値関係である．この同値類によって誘導される部分グラフを連結成分（connected component）という．

定義 5 (距離).

連結グラフ

G

の2頂点

u, v

間の距離

d (u, v)

とは，

u

から

v

への最短の道の長さである．

G

の直径を

diam (G) = max_{u, v \in V} d (u, v)

で定める．

3 切断点・橋・連結度

定義 6 (切断点と橋).

連結グラフ

G

の頂点

v

を除去（

v

とそれに接続する辺をすべて除く）して得られるグラフ

G - v

が非連結になるとき，

v

を切断点（cut vertex）という．同様に辺

e

を除去して

G - e

が非連結になるとき，

e

を橋（bridge）という．

以下のグラフで $v$ は切断点であり，辺 ${v, d}$ は橋である：

定理 7.

辺

e

がグラフ

G

の橋であるための必要十分条件は，

e

がどの閉路にも含まれないことである．

証明.

(\Rightarrow)

対偶を示す．

e = {u, v}

がある閉路

C

に含まれるとする．

G - e

において

u

から

v

への道は

C

の

e

を除いた部分として存在する．

G

の任意の2頂点

x, y

間の道は，

e

を通るとしても

u

と

v

を

C

の残りで迂回できるので

G - e

でも連結．よって

e

は橋でない．

(\Leftarrow)

e = {u, v}

がどの閉路にも含まれないとする．

G - e

で

u

から

v

への道

P

が存在すれば，

P

に

e

を加えて閉路が得られ矛盾．よって

G - e

で

u

と

v

は非連結，すなわち

e

は橋である． □

定義 8 (頂点連結度・辺連結度).

連結グラフ

G

の頂点連結度

κ (G)

は，

G

を非連結にするために除去すべき頂点の最小個数とする（

G = K_{n}

のときは

κ (K_{n}) = n - 1

と定める）．辺連結度

λ (G)

は非連結にするために除去すべき辺の最小本数とする．

定理 9 (Whitney の不等式).

任意の連結グラフ

G

に対して

κ (G) \leq λ (G) \leq δ (G)

が成り立つ．ここで

δ (G)

は

G

の最小次数である．

証明.

λ (G) \leq δ (G)

：最小次数の頂点

v

に接続するすべての辺を除去すれば

v

が孤立するので，

λ (G) \leq de g (v) = δ (G)

．

κ (G) \leq λ (G)

：

λ (G) = k

を達成する辺カット

F = {e_{1}, \dots, e_{k}}

を取る．

G - F

は2つの連結成分

G_{1}, G_{2}

に分かれる（最小カットなので2成分）．各

e_{i} = {u_{i}, v_{i}}

（

u_{i} \in V (G_{1})

，

v_{i} \in V (G_{2})

）に対して

v_{i}

を除去候補とする．

∣ V (G_{2}) ∣ > k

であれば

v_{1}, \dots, v_{k}

のうち相異なるもの（高々

k

個）を除去すれば

G_{1}

と

G_{2}

の残りが分断されるので

κ (G) \leq k

．

∣ V (G_{2}) ∣ \leq k

の場合，

V (G_{2})

全体を除去しても高々

k

頂点なので

κ (G) \leq k

． □

4 二部グラフの判定

定理 10 (二部グラフの特徴づけ).

グラフ

G

が二部グラフであるための必要十分条件は，

G

が奇数長の閉路を含まないことである．

証明.

(\Rightarrow)

G

が二部グラフで

V = X ⊔ Y

とする．閉路

v_{0}, v_{1}, \dots, v_{k} = v_{0}

を考える．辺は必ず

X

と

Y

を行き来するので，

v_{0} \in X

ならば

v_{i} \in X ⟺ i

は偶数．

v_{k} = v_{0} \in X

より

k

は偶数．

(\Leftarrow)

G

が連結と仮定して示す（各成分に適用すればよい）．頂点

s

を固定し，

d (s, v)

を

s

から

v

への距離とする．

X = {v ∣ d (s, v) は偶数}

，

Y = {v ∣ d (s, v) は奇数}

とおく．辺

{u, v} \in E

に対して

u, v

が同じ集合に属すると仮定すると，

s

から

u

への最短道と

s

から

v

への最短道を合わせて奇数長の閉歩道が得られ，奇数長の閉路の存在が従い矛盾．よって

G

は二部グラフである． □

5 Menger の定理

定義 11 (独立な道).

2頂点

s, t

間の道の集合が頂点独立（internally vertex-disjoint）であるとは，どの2本の道も内部頂点（

s, t

以外の頂点）を共有しないことをいう．

定理 12 (Menger の定理（頂点版）).

隣接しない2頂点

s, t

を持つグラフ

G

において，

s

と

t

を分離する頂点カットの最小サイズは，

s

t

間の頂点独立な道の最大本数に等しい．

証明.

k

本の頂点独立な道が存在するならば，各道から少なくとも1つの内部頂点を除去しなければ

s

t

を分離できないので，最小カットは

\geq k

である（これは容易）．逆の不等式（最小カット

\leq k

ならば

k

本の独立な道が存在する）は辺数に関する帰納法で証明できる．基本的なアイデアは最大フロー・最小カット定理と同様であり，フロー理論を用いた証明が最も簡潔である（ネットワークフローの回で改めて扱う）． □

注意 13.

Menger の定理には辺版もある：

s

t

間の辺独立な道の最大本数は

s

t

辺カットの最小サイズに等しい．Whitney の不等式

κ (G) \leq λ (G)

は Menger の定理の系として理解できる．

道と連結性 ― グラフの「つながり」を定式化する

1 歩道・道・閉路

2 連結性と連結成分

3 切断点・橋・連結度

4 二部グラフの判定

5 Menger の定理

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ