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$
