Graph/Blätter/Spannbäume/Aufgabe/Kommentar

Da man die Blätter sukzessive entfernen kann, muss man lediglich zeigen, dass die Anzahl der aufspannenden Bäume gleich bliebt, wenn man ein Blatt zusammen mit der anliegenden Kanten entfernt. Sei also ${}b$ ein Blatt mit zugehöriger Kante ${}e=\{b,u\}$.

Jeder aufspannende Baum muss das Blatt ${}b$ enthalten, und die einzige Möglichkeit ist über die einzige Kante ${}\{b,u\}$. Wenn man das Blatt und diese Kante entfernt, so erhält man nach Fakt wieder einen (Spann)-Baum. Wenn umgekehrt ein aufspannender Baum von des reduzierten Graphen vorliegt, so wird dieser durch Hinzunahme des Blattes und der Kante zu einem Spannbaum des Ausgangsgraphen. Es gibt also eine natürliche Bijektion zwischen den aufspannenden Bäumen des Graphen mit oder ohne dem Blatt.

Mit Fakt geht das Argument so: Der Graph ${}G\setminus \{e\}$ (also mit dem Knoten ${}b$, aber ohne die verbindende Kante)

ist nicht zusammenhängend und hat daher keinen Spannbaum. Damit stimmt die Anzahl der Spannbäume von ${}G$ mit der Anzahl der Spannbäume von ${}G/e$ überein. Das Argument von oben ist aber andererseits auch der wesentliche Punkt im Beweis des Lemmas.

Zur kommentierten Aufgabe