オーレの定理
有向グラフ G が次の条件を満たすとする: 任意の2頂点 u と v に対し、u から v へ向かう辺が存在するか、もしくは u の出次数と v の入次数の和が G の頂点数以上である。
このとき G には有向ハミルトンサイクルが存在する(Woodallの定理)。オーレの定理は、与えられた無向グラフの全ての辺を両方向の2本の有向辺で置き換えれば、Woodallの定理から得ることができる。Meyniel (1973) による、これと深く関連した定理は以下の通りである:
n-頂点の強連結有向グラフで、任意の隣接しない2頂点 u, v に対し、u と v の少なくとも一方に接続する辺の本数が 2n − 1 以上であるものは、ハミルトングラフである。
次数に関する条件から、オーレの定理の結論は、ハミルトン性よりも強くすることができる。特に、オーレの定理の条件を満たすグラフは正則な完全2部グラフか、パンサイクリックグラフ(英語版)かのいずれかである (Bondy 1971)。