Graph/Wälder/Matroid/Fakt/Beweis

Beweis

Wir gehen die Axiome für ein Matroid durch. Die Menge ${}(V,\emptyset )$ ist ein Wald, bestehend aus den einpunktigen Bäumen. Ein Untergraph eines Waldes ist wieder ein Wald. Es seien nun ${}W$ und ${}Z$ Wälder von ${}G$ und ${}Z$ enthalte eine Kante mehr als ${}W$. Es ist zu zeigen, dass man ${}W$ durch eine Kante aus ${}E$ zu einem größeren Wald ergänzen kann. Da aber die Anzahl der Kanten von ${}Z$ durch die Zahl aus Fakt beschränkt ist, folgt aus dieser Aussage, dass man ${}W$ vergrößern kann.

Zur bewiesenen Aussage