Graph/Gradbedingung/Ore/Hamiltonkreis/Fakt

Satz von Ore

Es sei ${}G=(V,E)$ ein Graph mit mindestens drei Elementen, der die Bedingung

${}d(u)+d(v)\geq {\#\left(V\right)}\,$

für je zwei nicht adjazente Knoten ${}u,v$ erfüllt.

Dann ist ${}G$ hamiltonsch.

Zum Beweis, Alternativen Beweis erstellen