Stelling van Ore

De stelling van Ore is een stelling uit de grafentheorie, bewezen door Øystein Ore in 1960. De stelling geeft een voldoende voorwaarde opdat een graaf een hamiltoncircuit bevat. Een hamiltoncircuit is een gesloten pad in een graaf die elke knoop eenmaal aandoet.

De stelling zegt:

Gegeven een samenhangende enkelvoudige graaf ${\displaystyle G=(V_{G},E_{G})}$ met knopenverzameling ${\displaystyle V_{G}}$ en kantenverzameling ${\displaystyle E_{G}}$, en met ${\displaystyle n\geq 3}$ knopen.

Als voor elk tweetal knopen ${\displaystyle a,b\in V_{G}}$ met ${\displaystyle (a,b)\notin E_{G}}$ geldt dat ${\displaystyle \deg(a)+\deg(b)\geq n}$, bevat ${\displaystyle G}$ een hamiltoncircuit.

Hierin is ${\displaystyle \deg(x)}$ de graad van een knoop, dit is het aantal kanten dat in de knoop toekomt.

Anders gezegd: Als de som van de graden van elke twee niet-naburige knopen minstens gelijk is aan ${\displaystyle n}$, bevat de graaf een hamiltoncircuit.