Aufgabe: Sei H = (V,E) ein zusammenhangender Graph und TH(w) der Tiefensuchebaum von H, der entsteht, wenn Tiefensuche mit Startknoten w ∈ V ausgeführt wird. Wir nennen einen Knoten v ∈ V Artikulation, wenn H ohne v unzusammenhangend ist.
Zeige: Gilt δ(w) ≥ 2 in TH (w), dann ist w eine Artikulation.
…
Problem/Ansatz:
