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 hamiltonpad bevat. Een hamiltonpad is een gesloten pad in een graaf die elke knoop eenmaal aandoet.

De stelling zegt:

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

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

Hierin is $\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 $n$, bevat de graaf een hamiltonpad.

Bronnen, noten en/of referenties