How many labeled trees exist with vertices $\{1,2,3,4,5\}$ that contain the edge $\{1,2\}$? How many labeled trees exist with vertices $\{1,2,3,4,5\}$ that contain the edge $\{1,2\}$?
 A: HINT: If you remove the edge $\{1,2\}$ from such a tree, you get a pair of trees, the subtrees rooted at $1$ and at $2$; call these $T_1$ and $T_2$. You can split the remaining three vertices, $3,4$, and $5$, arbitrarily between $T_1$ and $T_2$.


*

*For $k=0,1,2,3$, how many ways are there to assign $k$ of these three vertices to $T_1$ (and the rest to $T_2$)?  

*Suppose that $T_1$ is a rooted tree with $k$ vertices and $T_2$ a rooted tree with $5-k$ vertices. How many distinct possibilities for $T_1$ are there? How many for $T_2$? How many for the pair?  


Now sum over $k$.
This is the general approach; you can apply it to $n$ vertices instead of $5$ to get a general formula. If you take this approach, you’ll need to know how many labelled, rooted trees there are on $n$ vertices. There are $n^{n-2}$ labelled trees on $n$ nodes, and in each of them there are $n$ ways to choose a root, so there are $n\cdot n^{n-2}=n^{n-1}$ labelled rooted trees on $n$ vertices.
A: Since each spanning tree of $K_5$ contains $4$ of the $10$ possible edges, by symmetry each edge belongs to $4/10$ of the $5^3=125$ trees; $40\%$ of $125$ is $\boxed{50}.$
More explicitly:
The complete graph $K_5$ has $5^3=125$ spanning trees, each having $4$ edges. Thus the number of edge-tree pairs $(e,T),$ where $T$ is a spanning tree of $K_5$ and $e$ is an edge of $T,$ is $4\cdot125.$
Let $e_1,\dots,e_{10}$ be the edges of $K_5,$ and let $n_i$ be the number of spanning trees containing the edge $e_i.$ Thus the number of edge-tree pairs is
$$\sum_{i=1}^{10}n_i=4\cdot125$$
By symmetry (one edge is like another), we have $n_1=\cdots=n_{10},$ whence
$$n_i=\frac{4\cdot125}{10}=50.$$
More generally, in $K_n$ the number of spanning trees containing a given edge is
$$\frac{(n-1)n^{n-2}}{\binom n2}=2n^{n-3}.$$
