What is the number of spanning sub_tree $_$ that have exactly $( − 2)$ leaves?

Question

What is the number of labelled spanning trees of $_$ that have exactly $(n-2)$ leaves?(Consider that $n\geq 4$ )

Do not consider isomorphic trees as one.

I know that the number of labelled spanning trees of $K_$ is equal to $n^{n-2}$.

I think it can be proved with the theorem of inclusion and non-inclusion, but it is very long!

Can you help me?

Answer 1

Hint: consider what a tree with $n-2$ leaves looks like. It is one single central edge $uv$, where every vertex is adjacent to either $u$ or $v$. Further, $u$ has at least one neighbor other than $v$, and $v$ has at least one neighbor other than $u$.

---

Answer: (click spoiler)

$$\text{number of spanning trees of $K_n$ with $n-2$ leaves} = \binom{n}{2}\cdot \left(2^{n-2}-2\right)$$

Proof: (click spoiler)

Each spanning tree with $n-2$ leaves is uniquely determined by a choice of edge $uv$ (i.e., the 'middle' of the spanning tree), and a choice of which of the remaining $n-2$ vertices are adjacent to $u$ --- subject to the constraint that the neighborhood of $u$ cannot contain either all or none of these remaining vertices (see the diagram). There are $\binom{n}{2}$ choices for the middle edge, and $(2^{n-2}-2)$ non-empty, non-full subsets of the remaining $n-2$ vertices that can be the set of neighbors of $u$.