Zusammenhängender Graph/Aufspannender Baum/Fakt/Beweis

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 ${}G=(V,E)$ ein zusammenhängender Graph mit ${}m$ Kanten. Wenn ${}G$ ein Baum ist, sind wir fertig. Es sei also ${}G$ kein Baum. Dann gibt es einen Kreis

$v_{1},v_{2},\ldots ,v_{r},v_{r+1}=v_{1}$

mit ${}r\geq 3$ in ${}G$. Wir betrachten den Graphen ${}G'$ mit der gleichen Knotenmenge ${}V$ und der neuen Kantenmenge

${}E'=E\setminus \{v_{1}v_{2}\}\,.$

Dieser Graph hat eine Kante weniger und er ist zusammenhängend, da der Zusammenhang zwischen ${}v_{1}$ und ${}v_{2}$ über das verbleibende „Kreissegment“ ${}v_{2},\ldots ,v_{r}=v_{1}$ gesichert ist. Nach Induktionsvoraussetzung gibt es einen aufspannenden Baum in ${}G'$, und dieser ist auch ein aufspannender Baum von ${}G$.

Zur bewiesenen Aussage