Find the probability that the n-th vertex of a labeled spanning tree
defined on $\{1 \dots n\}$ is a leaf
The Cayley's formula gives the number of labeled trees on the set in question as $n^{n-2}$.
To get n-th vertex to be a leaf, we need to have a spanning tree defined on $\{1 \dots n-1\}$. Then, the vertex can be appended to any of these trees in $n-1$ places (to each vertex). So, the solution would be:
$$(n-1)^{n-3} \cdot (n-1) / (n^{n-2})$$
However, can I be sure that this solution dos not generate any isomorphic trees that are counted more than once?
Best Answer
The concept of isomorphism doesn’t really apply here – since the trees are labeled, you either have the same tree or you don’t. If you start from different trees with $n-1$ vertices, you can’t get the same tree because the $n-1$ vertices would have different edges, and if you start from the same tree with $n-1$ vertices and append the leaf to different vertices, you also can’t get the same tree because the vertex labeled $n$ is connected to different vertices. Thus you’re counting each tree only once.