オーレの定理

オーレの定理（オーレのていり、）は、ノルウェーの数学者 によって1960年に証明されたグラフ理論の定理である。オアの定理とも表記される。これはグラフがハミルトングラフであるための十分条件を与えるもので、実質的に、グラフに十分多くの辺が存在していればハミルトン閉路を含んでいなければならないと述べている。特に、この定理ではグラフの隣接しない2頂点の次数の和について考える。もしこのような和が常にグラフの頂点数以上であれば、グラフはハミルトングラフである。

正式なステートメント が有限単純グラフで、頂点数 とする。 の頂点 の次数（その頂点に接続する辺の数）を と書く。このとき、

であるなら、 はハミルトングラフである。

逆に、ハミルトングラフならば条件を満たすわけではない。(十分条件)

ハミルトングラフの集合の中に、上記の条件を満たす特殊なハミルトングラフの集合が存在する。

証明

任意の非ハミルトングラフ が条件 (∗) を満たさないことを言えばよい。

(全てのハミルトングラフでないGが条件を満たさない→条件を満たすグラフGの集合は、ハミルトングラフの集合に必ず含まれる。)

そこで、 を頂点数 の非ハミルトングラフとし、これに辺を1本ずつ足していって、それ以上どのように辺を追加してもハミルトン閉路ができてしまうようなグラフを とする。

と を における任意の隣接しない2頂点とする。このとき をグラフ に追加すると、1個以上のハミルトン閉路が生じる。この閉路から辺 を除いたものは のハミルトンパス （ここで , ）である。

任意の添字 ()に対し、 から への辺と から への辺の存在について考えると、これらのうち存在するのは高々1本である。なぜなら、さもないと で がハミルトン閉路になってしまうからである。

よって、頂点 または に接続する辺の総数は最大でも添字 の選び方の数、 である。よって が 以上でないため、 は条件 (∗) を満たさない。

グラフ の頂点の次数は での次数以下だから、 もやはり条件 (∗) を満たさない。

アルゴリズム は、オーレの条件の条件を満たすグラフにおいてハミルトン閉路を構成する以下のようなシンプルなアルゴリズムを記述した。

隣接性を無視し、グラフの頂点を閉路となるよう並べる。 この閉路で連続する2頂点 vi, vi + 1 が元のグラフで隣接していなかったら、以下の2つのステップを実行する。： 4個の頂点 vi, vi + 1, vj, vj + 1 が相異なり、かつ、元のグラフで vi と vj、vj + 1 と vi + 1 がそれぞれ隣接しているような添字 j を探す。 閉路内の vi + 1 から vj までの全ての頂点（両端も含む）を逆向きに並べる。

各ステップで、元のグラフで隣接しているような閉路内の連続する頂点対の数は、1または2だけ増加する（vj と vj + 1 が既に隣接している頂点対かどうかに依る）。そのため、アルゴリズムが停止するまでの閉路の拡張の回数は高々グラフの頂点数 n である。定理の証明で行ったものと同様の議論で、このような所望の添字 j は必ず存在する（さもなければ、隣接しない2頂点 vi, vi + 1 の次数の和は仮定の不等式を満たさない）。i と j の発見、閉路の一部の逆順並べ替えはいずれも計算時間 O(n) で行えるから、アルゴリズム全体の計算時間は O(n2) であり、これは入力するグラフの辺の数と同じオーダーである。

関連する結果 オーレの定理は（ハミルトン路に関する）： どの頂点の次数も 以上であるようなグラフは、ハミルトングラフである。

を一般化したものである。ディラックの定理の条件が満たされていれば、明らかにどの2頂点の次数の和も 以上になる。

一方、オーレの定理は へと一般化される。グラフの閉包（closure）を、次数の和がグラフの頂点数 以上である任意の隣接しない2頂点間に1本の辺を追加する操作、と定義する。このとき Bondy–Chvátalの定理は グラフがハミルトングラフであるための必要十分条件は、その閉包がハミルトングラフであることである。

という主張である。グラフがオーレの定理の条件を満たしていれば、その閉包は完全グラフであり、完全グラフはハミルトングラフであるから、オーレの定理は Bondy–Chvátalの定理よりただちに従う。

は、オーレの定理の有向グラフに適用できるバージョンを発見した。有向グラフ G が次の条件を満たすとする： 任意の2頂点 u と v に対し、u から v へ向かう辺が存在するか、もしくは u の出次数と v の入次数の和が G の頂点数以上である。

このとき G には有向ハミルトンサイクルが存在する（Woodallの定理）。オーレの定理は、与えられた無向グラフの全ての辺を両方向の2本の有向辺で置き換えれば、Woodallの定理から得ることができる。 による、これと深く関連した定理は以下の通りである： n-頂点の強連結有向グラフで、任意の隣接しない2頂点 u, v に対し、u と v の少なくとも一方に接続する辺の本数が 2n − 1 以上であるものは、ハミルトングラフである。

次数に関する条件から、オーレの定理の結論は、ハミルトン性よりも強くすることができる。特に、オーレの定理の条件を満たすグラフは正則な完全2部グラフか、かのいずれかである 。

参考文献 . . . . .