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 , dan bevat G 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 n, dan bevat de graaf een Hamiltonpad.