Multigraph/Aufspannender Baum/Rekursionsformel/Fakt/Beweis

Beweis

Sei ${}e=\{u,v\}$. Ein Spannbaum in ${}G$ enthält entweder diese Kante oder nicht. Wir zeigen, dass es im ersten Fall eine Bijektion zu den Spannbäumen der Kontraktion ${}G/(e)$ und im zweiten Fall eine Bijektion zu den Spannbäumen von ${}G\setminus \{e\}$ gibt. Dies ist im zweiten Fall unmittelbar klar. Betrachten wir also die Spannbäume in ${}G$, in denen ${}e$ vorkommt. Wenn man diese Kante herausnimmt, so erhält man einen Spannbaum von ${}G/(e)$, da ja die Endpunkte von ${}e$ miteinander identifiziert werden. Es sei umgekehrt ein Spannbaum von ${}G/(e)$ gegeben. Dieser durchläuft jeden Punkt von ${}G/(e)$, also auch den Kontraktionspunkt ${}[u]=[v]$. Indem man die Kante ${}e$ an dieser Stelle einbaut, erhält man einen Spannbaum von ${}G$.

Zur bewiesenen Aussage