Graph/Wald/Ergänzung/Fakt

Ergänzungssatz für Wälder

Es sei ${}G=(V,E)$ ein Graph mit ${}n$ Knotenpunkten und ${}c$ Zusammenhangskomponenten.

Dann lässt sich jeder Unterwald ${}(W,F)\subseteq (V,E)$ mit weniger als ${}n-c$ Kanten zu einem Unterwald mit ${}n-c$ Kanten ergänzen.

Zum Beweis, Alternativen Beweis erstellen