Graph/Wälder/Matroid/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

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