Let $n \geq 4$. How many labeled trees are there with $n$ vertices where vertex with label 1 has degree 3?

Question

So I'm a beginner to graph theory and really unsure how to approach this. I was thinking by counting Prufer codes, in which case you would want the second element in the Prufer code to be 3. So, it would be the number of Prufer codes where one of the labels are fixed at 3, so $n^{(n-1)-2}$ labeled trees?

Answer 1

First of all, you should probably draw out the cases $n=4,5$ by hand, and you'd see that your guess is wrong.

I'll assume we are counting unrooted trees. In that case, think about what happens if we remove the node with label $1$. Then we have a forest of $3$ rooted trees (the root is the node connected to $1$). You can probably count these a number of ways, but I'll show how I'd do it with generating functions / the symbolic method.

The EGF for rooted labeled trees satisfies $T(z)=ze^{T(z)}$ (because $\mathcal T = \mathcal Z\star SET(\mathcal T)$). Let $\mathcal F^{(k)}$ be the class of rooted $k$-forests. Then $$ \mathcal F^{(k)} = SET_k(\mathcal T) \implies F^{(k)}(z) = \frac{T(z)^k}{k!} $$ Now we can use Lagrange inversion / the Lagrange–Bürmann formula to get $F_n^{(k)}$, the number of $k$-forests with $n$ nodes. $[z^n]$ denotes the $n$'th coefficient in a series expansion. $$ \begin{split} F_n^{(k)} &= n![z^n] \frac{T(z)^k}{k!} \\ &= \frac{n!}{k!} [u^{n-1}]\frac 1n ku^{k-1} e^{nu} \\ &= \frac{(n-1)!}{(k-1)!} [u^{n-k}] e^{nu}\\ &= \binom{n-1}{k-1} n^{n-k} \end{split} $$ Wonderful! So the number you seek is equal to $F_{n-1}^{(3)} = \binom{n-2}{2}(n-1)^{n-4}$.