オイラーグラフとハミルトングラフ ― 道を巡る二つの古典問題

ケーニヒスベルクの橋問題からオイラーの定理，有向オイラーグラフ，ハミルトン路，OreとDiracの定理，NP完全性を解説する．

Folio公式

2026年2月27日

1 ケーニヒスベルクの橋問題

1736年，Euler はケーニヒスベルクの7つの橋をすべてちょうど1回ずつ渡って元に戻れるかという問題を考察した．これがグラフ理論の起源とされる．

この問題を多重グラフとしてモデル化すると， $A$ の次数は $5$ ， $B, C, D$ の次数はそれぞれ $3$ である．すべての頂点が奇数次であるため，以下の定理よりオイラー閉路は存在しない．

2 オイラー閉路とオイラー路

定義 1 (オイラー閉路・オイラー路).

グラフ

G

のオイラー閉路（Eulerian circuit）とは，

G

のすべての辺をちょうど1回ずつ通る閉径路である．オイラー路（Eulerian trail）とは，すべての辺をちょうど1回ずつ通る径路である．オイラー閉路を持つグラフをオイラーグラフ（Eulerian graph）という．

定理 2 (Euler の定理).

連結グラフ

G

がオイラー閉路を持つための必要十分条件は，すべての頂点の次数が偶数であることである．

証明.

(\Rightarrow)

オイラー閉路が頂点

v

を通過するたびに，

v

の次数に

2

が加算される（入る辺と出る辺）．すべての辺がちょうど1回使われるので

de g (v)

は偶数．

(\Leftarrow)

すべての頂点の次数が偶数であることを仮定する．辺数

m

に関する帰納法で証明する．

m = 0

なら自明．

m \geq 1

とする．

すべての次数が

\geq 2

であるから

G

は閉路

C

を含む（次数

\geq 2

の頂点から出発し未訪問の辺を辿れば，有限性より同じ頂点に戻る）．

G^{'} = G - E (C)

を考える．

C

で各頂点の次数から偶数が引かれるので

G^{'}

の各頂点の次数も偶数である．

G^{'}

の各連結成分

G_{1}^{'}, \dots, G_{c}^{'}

にそれぞれ帰納法の仮定を適用すると，各成分にオイラー閉路が存在する．

C

を辿りながら各成分のオイラー閉路を挿入することで，

G

全体のオイラー閉路が構成される．

G

が連結であることから

C

はすべての成分の頂点を少なくとも1つ含み，挿入が可能である． □

定理 3 (オイラー路の存在条件).

連結グラフ

G

がオイラー路を持つための必要十分条件は，奇数次の頂点がちょうど

0

個または

2

個であることである．

0

個の場合はオイラー閉路，

2

個の場合はその2頂点を端点とするオイラー路が存在する．

証明.

奇数次の頂点が

u, v

の2つである場合，辺

{u, v}

を追加した

G + {u, v}

では全頂点が偶数次となりオイラー閉路が存在する．その閉路から追加した辺を除けば

u

v

オイラー路が得られる． □

3 有向オイラーグラフ

定理 4 (有向オイラーの定理).

連結有向グラフ

D

がオイラー閉路（すべての弧をちょうど1回通る有向閉径路）を持つための必要十分条件は，すべての頂点

v

で

de g^{+} (v) = de g^{-} (v)

（出次数

=

入次数）が成り立つことである．

証明.

無向版と同様の論法で示される．オイラー閉路が頂点を通過するたびに入る弧と出る弧が1つずつ使われ，

de g^{+} (v) = de g^{-} (v)

が必要．十分性は閉路を取り出して帰納法で閉路を併合する． □

4 ハミルトン閉路

定義 5 (ハミルトン閉路・ハミルトン路).

グラフ

G

のすべての頂点をちょうど1回ずつ通る閉路をハミルトン閉路（Hamiltonian cycle），すべての頂点をちょうど1回ずつ通る道をハミルトン路（Hamiltonian path）という．ハミルトン閉路を持つグラフをハミルトングラフという．

注意 6.

オイラー閉路はすべての辺を巡る問題，ハミルトン閉路はすべての頂点を巡る問題である．前者は多項式時間で判定できるのに対し，後者は著しく困難である．

定理 7 (Dirac の定理（1952）).

n \geq 3

頂点の単純グラフ

G

がすべての頂点

v

に対して

de g (v) \geq n /2

を満たすならば，

G

はハミルトングラフである．

証明.

G

が

n /2

以上の最小次数を持つ非ハミルトングラフのうち辺数最大のものと仮定して矛盾を導く．

G

はハミルトン路

v_{1}, v_{2}, \dots, v_{n}

を持つ（辺を1本追加するとハミルトン閉路が生じるので，ハミルトン路は存在する）．

v_{1} v_{n} \in / E (G)

である（そうでなければハミルトン閉路）．集合

S = {i ∣ v_{1} v_{i + 1} \in E (G), 1 \leq i \leq n - 1}

と

T = {i ∣ v_{i} v_{n} \in E (G), 1 \leq i \leq n - 1}

を考える．

∣ S ∣ = de g (v_{1}) \geq n /2

，

∣ T ∣ = de g (v_{n}) \geq n /2

であり，

S, T \subseteq {1, \dots, n - 1}

（

∣ S ∣ + ∣ T ∣ \geq n

）なので鳩ノ巣原理により

S \cap T \neq = \emptyset

．

k \in S \cap T

を取ると

v_{1} v_{k + 1} \in E

かつ

v_{k} v_{n} \in E

であるから

v_{1}, v_{2}, \dots, v_{k}, v_{n}, v_{n - 1}, \dots, v_{k + 1}, v_{1}

がハミルトン閉路となり矛盾． □

定理 8 (Ore の定理（1960）).

n \geq 3

頂点の単純グラフ

G

において，隣接しない任意の2頂点

u, v

が

de g (u) + de g (v) \geq n

を満たすならば，

G

はハミルトングラフである．

注意 9.

Dirac の定理は Ore の定理の系である．

δ (G) \geq n /2

ならば，隣接しない任意の

u, v

に対して

de g (u) + de g (v) \geq 2 \cdot n /2 = n

が成り立つ．

5 NP 完全性

注意 10.

ハミルトン閉路問題（与えられたグラフにハミルトン閉路が存在するか）は

NP

完全問題である．これは Karp（1972）が示した21の

NP

完全問題の1つであり，

P \neq = NP

が成り立つ限り多項式時間アルゴリズムは存在しない．対照的にオイラー閉路の存在判定は各頂点の次数を調べるだけで

O (n + m)

で可能である．この著しい計算量の差が「辺を巡る」問題と「頂点を巡る」問題の根本的な違いを浮き彫りにしている．

オイラーグラフとハミルトングラフ ― 道を巡る二つの古典問題

1 ケーニヒスベルクの橋問題

2 オイラー閉路とオイラー路

3 有向オイラーグラフ

4 ハミルトン閉路

5 NP 完全性

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

Share your expertise with the world

More from Folio公式

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

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

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

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