グラフ理論には，一見よく似ているのに計算の難しさが天と地ほど違う2つの問題があります．オイラー回路（すべての辺をちょうど1回通る閉路）とハミルトン閉路（すべての頂点をちょうど1回通る閉路）です．

前者は多項式時間で判定できますが，後者は NP 完全 ― 現在知られている限り指数時間のアルゴリズムしかありません．「全辺」と「全頂点」，たった1語の違いでなぜこれほどの断絶が生じるのでしょうか？

1 オイラー回路 ― 次数を数えるだけ

この判定条件は驚くほどシンプルです．各頂点の次数を調べるだけなので，$O(|V|+|E|)$で判定できます．

2 ハミルトン閉路 ― 判定すら難しい

オイラー回路には「次数がすべて偶数」という美しい判定条件がありました．ハミルトン閉路にも同じような簡潔な条件があるでしょうか？

答えは，おそらくノーです．

十分条件はいくつか知られています：

しかし，これらは十分条件であって必要十分条件ではありません．条件を満たさなくてもハミルトン閉路をもつグラフはたくさんあります．

3 なぜこんなに違うのか ― 局所性 vs 大域性

この劇的な違いの本質はどこにあるのでしょうか．

もう少し具体的に考えてみましょう．

オイラー回路では，「辺を使い切る」ことが各頂点で局所的に（次数の偶奇で）保証されるため，行き詰まっても修正が効きます（Hierholzer のアルゴリズム）．しかしハミルトン閉路では，序盤の頂点選択が終盤に影響し，局所的な修正では対処できません．

4 計算量クラスの視点

この差は計算量理論の言葉で正確に表現できます．

5 巡回セールスマン問題

ハミルトン閉路の最適化版が，有名な巡回セールスマン問題（TSP）です．

TSP は NP 困難であり，正確な解を求めるにはビット DP で$O(2^n\cdot n^2)$，近似アルゴリズムや発見的手法に頼るのが実用的です．

6 まとめ ― 一語の違いが世界を変える

• オイラー回路：「全辺を1回」→ 局所条件（次数偶数）で判定 → $\mathbf{P}$

• ハミルトン閉路：「全頂点を1回」→ 大域的制約 → $\mathbf{NP}$完全

「辺」と「頂点」のこの断絶は，グラフ理論に限らず計算量理論全体に通じる教訓を含んでいます：局所条件だけで特徴づけられる問題は効率的に解けるが，大域的な整合性が必要な問題は爆発的に難しくなるのです．

次の記事では，グラフ理論のもう一つの美しい双対性 ― 最大フロー最小カット定理について考えます．