オーレの定理
任意の非ハミルトングラフ 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 もやはり条件 (∗) を満たさない。