Stelling van Ore

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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.