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$

  • $\begingroup$ Do you mean $8^4$? $\endgroup$ – druckermanly Dec 12 '14 at 5:05
  • $\begingroup$ yes, thank you, although I beat you too it :) $\endgroup$ – Jorge Fernández Hidalgo Dec 12 '14 at 5:05
  • $\begingroup$ Yeah, just as I hit submit I saw "An edit...". It seems I just mixed up my $8$ and $4$. Thanks! $\endgroup$ – druckermanly Dec 12 '14 at 5:06
  • $\begingroup$ No problem, happy I could help. $\endgroup$ – Jorge Fernández Hidalgo Dec 12 '14 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.