Aufgabe:
Wie viele aufspannende Bäume mit genau einer Ecke vom Grad 3 hat der vollständige Graph K7?
Problem/Ansatz:
Der Baum hat 7 Ecken, die Prüfercodes werden also 7-2 = 5 Stellen lang sein.Die Ecke vom Grad 3 taucht genau zweimal auf da deg(v) - 1 = 2 ist.
Ich hätte gesagt, ( 7 über 1) Möglichkeiten die Ecke vom Grad 3 zu wählen.
(5 über 3) Möglichkeiten, die drei Positionen der Ecke vom Grad 3 im Prüfercode zu wählen.
Auf der ersten noch freien Position im Prüfercode können wir eine der sechs verbleibenden Ecken wählen. Und dann auf der letzten freien Position eine der verbleibenden 5 Ecken.
Also 7 * 10 * 6 * 5 = 2100 Möglichkeiten.
Ist das richtig?
