Beweis
Wir argumentieren bei einer fixierten Knotenmenge absteigend über die Kantenmenge. Für einen
vollständigen Graphen
ist die Aussage richtig. Wir müssen zeigen, dass die Aussage richtig bleibt, wenn man aus einem Graphen, für den die Aussage gilt, eine Kante herausnimmt. Es sei also ein Graph, für den es einen Hamiltonkreis gibt, und es sei
die Kante, die wir herausnehmen. Es sei der verkleinerte Graph. Wenn es in einen Hamiltonkreis gibt, in dem nicht vorkommt, so ist dies direkt ein Hamiltonkreis für . Es sei also
(alle beziehen sich auf )
-
mit
ein Hamiltonkreis von . Wir betrachten die Mengen
-
und
-
Dabei ist
(in der Definition von )
als zu interpretieren und die Nachbarschaften beziehen sich auf . Aufgrund der Voraussetzung über die Grade
( und sind nicht adjazent und ist so groß wie )
ist
-
Das Element gehört nicht zur Vereinigung , da ein Knotenpunkt nicht mit sich selbst benachbart ist. Daher gibt es
nach der Siebformel
ein Element
-
Es gibt also die Verbindungskanten
und
und somit den Hamiltonkreis
-
der ohne die Kante auskommt und daher ein Hamiltonkreis in ist.