1. ## Spanning Trees

For $\displaystyle n \geq 2$ , let u be a fixed vertex of the complete graph $\displaystyle K_{n}$. Compute the number $\displaystyle \tau_{u}(n)$ of spanning trees of $\displaystyle 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 $\displaystyle 1/e$ where $\displaystyle e = 2.71828182...$ is the base number for the natural logarithm.

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

Then we have the generating function: $\displaystyle 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}$ $\displaystyle (*)$

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

But of course if we require the exponent of $\displaystyle x_u$ to be one we have the generating function: $\displaystyle 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 $\displaystyle x_u$ in one of the $\displaystyle (x_1+x_2+...+x_n)$ we had in $\displaystyle F$.

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

And the total number of labelled trees is .

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