I'm struggling with a homework assignment, and would like for a review of how I'm doing so far. I'm trying to answer this question:
A. Count the number of trees for vertices $1 \dots n$, where $1$ is a leaf
B. Count the number of trees for vertices $1 \dots n$, where $1$ is a leaf and $(1,2)$ is an edge.
Here's what I have so far:
A. Say I cut the leaf ($1$) and I'm left with vertices $2 \dots n$ and their degree sequence is $d_2,\dots,d_j-1,\dots\,d_n$, where $j$ is the vertex that was connected to $1$ before I cut it. By Cayley's theorem $T_{n-1}(d_2,...,d_j-1,...,d_n) = (n-1)^{n-3}$. $J$ could be anything from $2$ to $n$, but whatever it is $T_{n-1}$ stays the same, so to get $T_n$ I just multiply $T_{n-1}$ by the $(n-1)$ possible values of $j$ and I get $T_n = (n-1)^{n-2}$.
Is that true? Somehow I feel that its not, but I can't think of anything better.
B. This time I know that the leaf I cut is connected to $2$, so there's no need to multiply by $(n-1)$ which means that $T_n = (n-1)^{n-3}$.
If I was right about the first question I think I should be right here as well, but I'm not sure at all.
Any hints or ideas would be welcomed, thanks!