0
$\begingroup$

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!

1 Answers 1

1

If you're not sure about this sort of thing, it's always a good idea to check your results with some examples for small numbers. The numbers for $n=1,2,3,4$ are readily counted to be $1,1,2,9$, so your formula seems to work out (except for $n=1$, which was to be expected since Cayley's formula doesn't hold for $n=0$).

I think your argument is correct, but I don't know why you mention the degree sequence and what you mean when you write it as an argument for $T_{n-1}$. The number $(n-1)^{n-3}$ is the number of all trees with $n-1$ vertices, not just the ones with a particular degree sequence.

Your result for B) is also correct; this is simply the number of trees with $n-1$ vertices, since there is exactly one way to attach a leaf $1$ to vertex $2$ in such a tree.