Zusammenhängender Graph/Aufspannender Baum/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Wir führen Induktion über die Anzahl der Kanten. Der Induktionsanfang ist klar, da ein kantenfreier Graph nur im einpunktigen Fall zusammenhängend ist, und dies ein Baum ist. Sei ein zusammenhängender Graph mit Kanten. Wenn ein Baum ist, sind wir fertig. Sei also kein Baum. Dann gibt es einen Kreis

mit in . Wir betrachten den Graphen mit der gleichen Knotenmenge und der neuen Kantenmenge

Dieser Graph hat eine Kante weniger und er ist zusammenhängend, da der Zusammenhang zwischen und über das verbleibende „Kreissegment“ gesichert ist. Nach Induktionsvoraussetzung gibt es einen aufspannenden Baum in , und dieser ist auch ein aufspannender Baum von .