1. ## Spanning Trees

For $n \geq 2$ , let u be a fixed vertex of the complete graph $K_{n}$. Compute the number $\tau_{u}(n)$ of spanning trees of $K_{n}$ that contain the vertex u as a leaf. Use this to show that the probability a vertex in a tree on n vertices is a leaf is approximately $1/e$ where $e = 2.71828182...$ is the base number for the natural logarithm.

2. Let's denote by $f_n(d_1,...,d_n)$ the number of labeled ( label set $\{1,...,n\}$ ) trees - with n vertices- such that the degree of vertex $i$ is $d_i$.

Then we have the generating function: $F(x_1,..,x_n) = \sum f_n(d_1,..,d_n)\cdot x_1^{d_1}\cdot x_2^{d_2}...x_n^{d_n} = x_1\cdot ...x_n\cdot (x_1+...+x_n)^{n-2}$ $(*)$

Now if $\text{deg}(u)=1$ what we want is the sum of the entries where the corresponding exponent of $x_u$ is 1.

But of course if we require the exponent of $x_u$ to be one we have the generating function: $R(x_1,..,x_n) = x_1\cdot ...\cdot x_n \cdot (x_1+...+x_{u-1}+x_{u+1}+...+x_n)^{n-2}$ since we may never choose $x_u$ in one of the $(x_1+x_2+...+x_n)$ we had in $F$.

Thus the number of trees such that vertex u is a leaf is: $R(1,...,1) = (n-1)^{n-2}$

And the total number of labelled trees is .

$(*)$ For further details on this read here.