Zusammenhängender Graph/Aufspannender Baum/Minimal zusammenhängend/Aufgabe

Es sei ${}G$ ein zusammenhängender Graph. Zeige, dass für einen Untergraphen ${}H=(V,F)\subseteq G$ (also mit voller Vertexmenge) die folgenden Aussagen äquivalent sind.

1. ${}H$ ist ein Baum.
2. ${}H$ ist ein aufspannender Baum.
3. ${}H$ ist maximal kreisfrei, d. h. sobald man eine Kante aus ${}G$ zu ${}H$ hinzutut, entsteht ein Kreis.
4. ${}H$ ist minimal zusammenhängend, d. h. sobald man eine Kante herausnimmt, wird der Graph unzusammenhängend.

Eine Lösung erstellen