Multigraph/Aufspannender Baum/Rekursionsformel/Fakt

Rekursionssatz für aufspannende Bäume

Es sei ${}G$ ein schleifenfreier Multigraph und ${}e$ eine Kante von ${}G$.

Dann besteht für die Anzahl der aufspannenden Bäume der Zusammenhang

${}t(G)=t(G\setminus e)+t(G/e)\,.$

Zum Beweis, Alternativen Beweis erstellen