Graphentheorie: Artikulationspunkt, Hamiltonkreis, Zusammenhangskomponenten

Question

Aufgabe:

a) Ein Artikulationspunkt ist ein Knoten v, sodass der Graph G nach Entfernen dieses Knotens nicht mehr zusammenhängend ist. Zeigen Sie: Hat ein Graph einen Artikulationspunkt, so besitzt er keinen Hamiltonkreis.

b) Zeigen Sie allgemein: Zerfällt ein Graph nach Entfernen von k Knoten in mindestens k+1 Zusammenhangskomponenten, so enthält er keinen Hamiltonkreis.

Problem/Ansatz:

Könnte mir jemand bei dieser Aufgabe helfen?

Answer 1

Ein Artikulationspunkt ist ein Knoten v, sodass der Graph G nach Entfernen dieses Knotens nicht mehr zusammenhängend ist.

Okay... damit ist ja fast schon alles gesagt...
Ein Hamiltonkreis ist ein Kreis der jeden Knoten genau einmal besucht.

Jetzt beweißt du einfach, dass wenn ein Artikulationspunkt in einem Graphen existiert, dieser die einzige Verbindung zwischen den entstehenden Zusammenhangskomponenten ist und damit man alle Knoten in dem Graphen besucht mindestens zweimal über den Artikulationspunkt gehen muss.