8 Hamiltonkreise

Example: Every complete graph \(K_n, n 2\) is Hamiltonian.

Bemerkung: Klar, dass \(c(\pi) \leq \pi(G)\).

Notwendige Bedingungen für Hamiltonkreise

Sei in diesem Abschnitt \(\kappa := c\) die Zusammenhangszahl.

Hinreichende Bedingungen für Hamiltonkreise

Satz 8.6

(Drückfehler: a,b in V(G) und nicht E(G))

Beweis1 Beweis2

Korollar 8.7

Durch Hinzufügen der neuen Kanten bleibt Hamilton-Kreis gültig und vollständiger Graph ist natürlich hamiltonisch.

Satz 8.8