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

Die Aussage sollte strukturell an die Aussage der linearen Algebra errinnern: Eine Familie von Vektoren ist genau dann eine Basis, wenn sie eine maximal linear unabhängig ist genau dann, wenn sie ein minimales Erzeugendensystem ist, siehe Fakt. Die Analogie zwischen (aufspannenden) Bäumen bzw. Wälder zu (maximal) linear unabhängigen Vektorfamilien wird ja bereits durch den Matroidbegriff präzise gemacht. (1) und (2) sind trivialerweise äquivalent, da ja ein aufspannender Baum einfach ein Baum mit der vollen Knotenmenge ist, was vorausgesetzt wird. Von (2) nach (3). Es werde die Kante ${}\{u,v\}$ hinzugenommen. Es gibt aber bereits in ${}H$ einen verbindenden Weg von ${}u$ nach ${}v$ und durch die Hinzunahme entsteht ein mehrfacher Weg und ein Kreis. Dieses Argument wurde schon im Beweis zu Fakt verwendet.

Von (3) nach (1). Es ist zu zeigen, dass unter der angegebenen Bedingung ${}H$ zusammenhängend ist. Wenn ${}H$ nicht zusammenhängend ist, so gebe es keinen Weg in ${}H$ von ${}u$ nach ${}v$. Es gibt in ${}G$ nach der Obervoraussetzung einen Weg von ${}u$ nach ${}v$. Zumindest eine Kante davon gehört nicht zu ${}H$, nach Umbenennung sei das die Kante ${}\{u,v\}$. Wenn man aber diese Kante zu ${}H$ hinzunimmt, entsteht ein größerer kreisfreier Untergraph.

Von (1) nach (4) folgt aus Fakt, wenn man die Kante ${}\{u,v\}$ herausnimmt, so zerstört man den eindeutigen wiederholungsfreien Verbindungsweg von ${}u$ nach ${}v$.

Von (4) nach (1) folgt ebenfalls aus

Fakt.

Zur kommentierten Aufgabe