How many labelled trees with $n$ vertices have a vertex of degree $n − 2$? I have a labelled tree with $n$ vertices for $n > 1$. How do I find the number trees with vertices tree that has a degree of $n-2$? I have been trying to figure it out but cannot seem to solve it. Is there any theorems that would help me with this?
I have tried using the Prufer sequence to solve it. I saw a pattern that if a vertex in the Prufer sequence shows up $n-2$ times, then that graph has a vertex with degree $n-2$. However, I am not sure how to work out the Prufer sequence for the larger number of vertices without drawing all the graphs which is not ideal.
 A: First we have to find out how such a tree looks like. Note that a tree with $n$ vertices has exactly $n-1$ edges. Since $n-2$ of these have to emanate from a single vertex there are not many possibilities left.
Given the possible unlabeled trees you have to find out in how many different ways you can label these trees with the numbers $1$, $2$, $\ldots$, $n$.
A: The Prufer sequence approach would also work (except that your condition should be that a vertex appears exactly $n-3$ times*). You should be able to count the number of such sequences. All that matters is which vertex appears $n-3$ times, which other vertex appears, and which position the other vertex appears in - how many possibilities is this?
*Note that a vertex of degree $k$ appears exactly $k-1$ times in the Prufer sequence. This is because as you construct the sequence you remove leaves one by one. If a vertex $v$ has degree $k$, then $k-1$ of its neighbours must be removed before it becomes a leaf, and each time this happens $v$ is added to the sequence. Once $v$ becomes a leaf, either it is removed itself or $v$ and its remaining neighbour are the final two vertices. In neither case is it added to the sequence again.
