Number of spanning trees in $K_n$ that contain a fixed tree?

Question

Given a fixed tree $F$ with $f$ vertices in a complete graph $K_n$. What is the number of spanning trees of $K_n$ containing $F$ as a sub graph?

A comment suggests it is $n^{n-f-1}f$. But I am not sure why. Maybe it is related to Prufer code?

Answer 1

Lemma. The number of labeled $n$-vertex trees in which a fixed vertex has degree $k$ is $\binom {n-2}{k-1} (n-1)^{n-k-1}$.

Proof. The degree of the vertex is one more than the number of times its label shows up in the Prüfer code. If the degree is supposed to be $k$, it shows up $k-1$ times, so there are $\binom {n-2}{k-1} (n-1)^{n-k-1}$ Prüfer codes like this: $\binom{n-2}{k-1}$ ways to choose where the fixed vertex appears, and $n-1$ ways to choose each of the $(n-2)-(k-1) = n-k-1$ remaining values in the code.

---

We can choose a spanning tree of $K_n$ containing $F$ in two steps. First, contract the vertices of $F$ to one vertex $v_F$ and choose a spanning tree of the resulting $K_{n-f+1}$. Second, if $v_F$ has degree $k$, we can expand it in $f^k$ ways to the original tree; for each edge out of $v_F$, we must choose which vertex of $F$ it's incident on.

By the lemma, summing over all possibilities for $k$, we see that there are $$\sum_{k=1}^{n-f} \binom{n-f-1}{k-1} (n-f)^{n-f-k} f^k$$ such trees. If we factor out an $f$ from the $f^k$ term, the rest simplifies to $n^{n-f-1}$ by the binomial theorem.