Aufspannender Baum/Rekursionsformel/1/Beispiel

Wir betrachten den Diamantgraphen und führen die Kontraktionen und Herausnahmen wie im Bild durch. Dieser Algorithmus liefert letztlich ${}8$ lineare Graphen, die jeweils einen Spannbaum haben (und einen Spannbaum des ursprünglichen Graphen repräsentieren). Nach Fakt gibt es also ${}8$ Spannbäume.