# Number of spanning trees in $K_9$ with the degree of vertex $1$ being $4$

I believe I've gotten this problem, but I'm not sure whether I'm correct, because my familiarity with Prufer codes is very weak. I would appreciate any corrections / comments on the mistakes I've made. Thanks!

The problem is as stated in the title: Imagine $K_9$, with the restriction that vertex $1$ has degree $4$.



Then in the Prufer code for each spanning tree, there must be exactly three $1$'s, because the degree of each vertex is equal to the number of times the vertex's index appears in a Prufer code, plus one.

This leaves the remaining $4$ elements to be picked from the set $\{2,3,4,5,6,7,8,9\}$, with any number of repetitions and/or counts allowed.

So we first order the values: There are ${7 \choose 3}$ ways to order the three values that are $1$. There are $4^8$ ways to pick the remaining $4$ elements. So there are a total of ${7 \choose 3} 2^{16}$ spanning trees satisfying the given restriction.

According to Prüfers method you want the lists of length $9-2$ with the numbers $1$ through $9$ that contain the number $1$ three times. There are $\binom{7}{3}$ ways to select the spaces with the number $1$ and then $8^4$ ways to fill in the remaining numbers. So the answer is $\binom{7}{3}8^4$
• Do you mean $8^4$? – druckermanly Dec 12 '14 at 5:05
• Yeah, just as I hit submit I saw "An edit...". It seems I just mixed up my $8$ and $4$. Thanks! – druckermanly Dec 12 '14 at 5:06