Multigraph/Aufspannender Baum/Rekursionsformel/Fakt/Beweis

Beweis

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