Graph/Wald/Ergänzung/Fakt/Beweis

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 ${}(W,F)$ liegt ganz in einer Zusammenhangskomponente von ${}G$. Nach Fakt gilt die Voraussetzung entsprechend in mindestens einer Zusammenhangskomponente von ${}G$, d.h. wir können annehmen, dass ${}G$ zusammenhängend ist. Es sei

${}(B,H)\subseteq (W,F)\,$

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

${}(B',H')=(B\cup \{v\},H\cup \{u,v\})\,$

nach Fakt ein größerer Baum, da ja ${}v$ ein Blatt von ${}B'$ ist. Bei ${}v\in W$ wird ${}B$ mit einem anderen Baum aus ${}W$ vereinigt, was wieder einen Baum ergibt.

Zur bewiesenen Aussage