オーレの定理
From Wikipedia, the free encyclopedia
オーレの定理（オーレのていり、英: Ore's theorem）は、ノルウェーの数学者 Øystein Ore によって1960年に証明されたグラフ理論の定理である。オアの定理とも表記される。これはグラフがハミルトングラフであるための十分条件を与えるもので、実質的に、グラフに十分多くの辺が存在していればハミルトン閉路を含んでいなければならないと述べている。特に、この定理ではグラフの隣接しない2頂点の次数の和について考える。もしこのような和が常にグラフの頂点数以上であれば、グラフはハミルトングラフである。
G が有限単純グラフで、頂点数 n ≥ 3 とする。G の頂点 v の次数（その頂点に接続する辺の数）を deg v と書く。このとき、
であるなら、G はハミルトングラフである。
逆に、ハミルトングラフならば条件を満たすわけではない。(十分条件)
ハミルトングラフの集合の中に、上記の条件を満たす特殊なハミルトングラフの集合が存在する。
証明
任意の非ハミルトングラフ G が条件 (∗) を満たさないことを言えばよい。
(全てのハミルトングラフでないGが条件を満たさない→条件を満たすグラフGの集合は、ハミルトングラフの集合に必ず含まれる。)
そこで、G を頂点数 n ≥ 3 の非ハミルトングラフとし、これに辺を1本ずつ足していって、それ以上どのように辺を追加してもハミルトン閉路ができてしまうようなグラフを H とする。
x と y を H における任意の隣接しない2頂点とする。このとき xy をグラフ H に追加すると、1個以上のハミルトン閉路が生じる。この閉路から辺 xy を除いたものは H のハミルトンパス v1v2...vn （ここで x = v1, y = vn ）である。
任意の添字 i (2 ≤ i ≤ n)に対し、v1 から vi への辺と vi − 1 から vn への辺の存在について考えると、これらのうち存在するのは高々1本である。なぜなら、さもないと H で v1v2...vi − 1vnvn − 1...vi がハミルトン閉路になってしまうからである。
よって、頂点 v1 または vn に接続する辺の総数は最大でも添字 i の選び方の数、n − 1 である。よって deg v1 + deg vn が n 以上でないため、 H は条件 (∗) を満たさない。
グラフ G の頂点の次数は H での次数以下だから、G もやはり条件 (∗) を満たさない。