ハミルトングラフ - グラフ理論入門5

すべての点を1度だけ通ってもとに戻る閉じた小道が存在するなら、その閉路をハミルトングラフという。すべての点を通る道がある場合は半ハミルトングラフ。知られている定理の多くは「Gに十分の多くな辺があれば、Gはハミルトンである」という形をしており、この中で有名なものはDiracの定理として知られる。それよりもより一般的なものはO.Oreによるもの。

定理: 単純グラフGにはn(≧3)個の点があるとする。隣接していない任意の2点vとwについて、 $deg(v) + deg(w) \geq n$ が成立するならGはハミルトングラフ。

証明: 定理が偽とする。Gはハミルトングラフではないが、n個の点を持ち、点次数に関する上の条件を満足しているとする。もう1本どんな辺を付け加えてもハミルトングラフになると仮定してもよい。したがってGにはすべての点を含む道 $v_1,...,v_n$ がある。しかし、Gはハミルトングラフではないので、道の始点 $v_1$ と終点 $v_n$ は隣接しない。よって $deg(v_1)+deg(v_n) \geq n$ である。したがって、点 $v_i$ は $v_1$ に隣接し、 $v_{i-1}$ は $v_n$ に隣接するような2つの点 $v_i$ と $v_{i-1}$ が存在する。このときGは $v_1,v_2,...,v_{i-1},v_n,v_{n-1},...,v_{i+1} ,v_i ,v_1$ となるハミルトン閉路があることになり矛盾。□