Zum Inhalt springen

Graph/Gradbedingung/Ore/Hamiltonkreis/Fakt/Beweis

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 G ein Graph, für den es einen Hamiltonkreis gibt, und es sei  e={x,y}  die Kante, die wir herausnehmen. Es sei H der verkleinerte Graph. Wenn es in G einen Hamiltonkreis gibt, in dem e nicht vorkommt, so ist dies direkt ein Hamiltonkreis für H. Es sei also (alle ∼ beziehen sich auf G)

x=v1∼v2∼…∼vn−1∼vn=y

mit  n=#(V)  ein Hamiltonkreis von G. Wir betrachten die Mengen

A={vi∣x und vi+1 sind benachbart}

und

B={vi∣y und vi sind benachbart}.

Dabei ist (in der Definition von A) vn+1 als v1 zu interpretieren und die Nachbarschaften beziehen sich auf H. Aufgrund der Voraussetzung über die Grade (x und y sind nicht adjazent in H und A ist so groß wie N(x)) ist

#(A)+#(B)≥n.

Das Element y gehört nicht zur Vereinigung A∪B, da ein Knotenpunkt nicht mit sich selbst benachbart ist. Daher gibt es nach der Siebformel ein Element

vk∈A∩B.

Es gibt also die Verbindungskanten {x,vk+1} und {y,vk} und somit den Hamiltonkreis

x∼v2∼…∼vk−1∼vk∼y∼vn−1∼…∼vk+1,

der ohne die Kante e auskommt und daher ein Hamiltonkreis in H ist.