Stelling van Ore
De stelling van Ore is een stelling uit de grafentheorie, bewezen door Øystein Ore in 1960.[1] 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 met knopenverzameling en kantenverzameling , en met knopen.
Als voor elk tweetal knopen met geldt dat , bevat een hamiltonpad.
Hierin is 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 , bevat de graaf een hamiltonpad.
Bronnen, noten en/of referenties