Graph/Wald/Ergänzung/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Wir zeigen, dass wir den Wald unter der vorgegebenen Bedingung um eine Kante (eventuell unter Hinzunahme von weiteren Knotenpunkten) zu einem größeren Wald ergänzen können. Jede Zusammenhangskomponente des Waldes liegt ganz in einer Zusammenhangskomponente von . Nach Fakt gilt die Voraussetzung entsprechend in mindestens einer Zusammenhangskomponente von , d.h. wir können annehmen, dass zusammenhängend ist. Es sei

ein Baum von (wenn leer ist, so können wir direkt zu einem einpunktigen Baum übergehen). Dieser besitzt weniger als Elemente. Sei ein Punkt, der nicht in vorkommt. Es gibt einen Weg in mit . Dabei findet irgendwo längs des Weges der Übergang von zu nicht statt, d.h. man kann davon ausgehen, dass ist. Wir nehmen die Kante (und eventuell den Punkt ) zu hinzu und müssen begründen, dass dies nach wie vor ein Wald ist. Bei ist

nach Fakt ein größerer Baum, da ja ein Blatt von ist. Bei wird mit einem anderen Baum aus vereinigt, was wieder einen Baum ergibt.