Zeige: Jeder zusammenhängende Graph H enthält einen Knoten v, sodass H nach Entfernen von v zusammenhängend ist.

Question

Aufgabe:

Zeige: Jeder zusammenhängende Graph H enthält einen Knoten v, sodass H nach Entfernen von v zusammenhängend ist.

Problem/Ansatz:

Ich haben leider keine Ahnung wie ich das zeigen soll. Eine Lösung wäre sehr hilfreich.

Comments

Habt Ihr schon den Begriff des aufspannenden Baums oder auch Gerüst gehabt?

---

Ja, ein aufspannender Baum ist ein Baum, der alle Knoten verbindet.

Ein Baum ist dabei eine Zusammenhangskomponente, also ein kreisfreier zusammenhängender Graph

Answer 1

Sei also G=(V,E) ein zusammenhängender Graph, T=(V,F) ein aufspannender Baum. Betrachte in T einen längsten Weg \((v_0,v_1, \ldots,v_n)\). Dann hat \(v_0\) in T den Grad 1 (Sonst könnten wir den Weg verlängern und \(v_0=v_n\) würde bedeuten, dass der Weg geschlossen wäre.)

Dann ist \(\left(T\setminus\{v_0\},F \setminus\{\{v_0,v_1\}\}\right)\) ein Baum.

Das bedeute: Wenn wir aus G \(v_0\) und alle seine Kanten herausnehmen, bleibt ein zusammenhängender Graph übrig.