Number of trees with a fixed edge Consider a vertex set $[n]$. By Cayley's theorem there there are $n^{(n-2)}$ trees on $[n]$, but how can one count the following slightly modified version: 
What is the number of trees on $[n]$ vertices where the edge $\{1,2\}$ is definitely contained in the trees?
 A: We can actually do it directly from Cauchy’s theorem, without making use of a proof of that result.
For each $e=\{k,\ell\}\in[n]$ with $k\ne\ell$ let $S_n(e)$ be the number of trees on $[n]$ that contain the edge $e$, let $e_0=\{1,2\}$, and let $S_n=S_n(e_0)$; clearly $S_n(e)=S_n$ for all $e\in E$, where $E$ is the set of possible edges. Then
$$\sum_{e\in E}S_n(e)=\binom{n}2S_n$$
counts each tree on $[n]$ $n-1$ times, once for each of its edges. There are $n^{n-2}$ trees on $[n]$, so
$$\binom{n}2S_n=(n-1)n^{n-2}\;,$$
and
$$S_n=2n^{n-3}\;.$$
A: It seems that you can adjust this proof.
First, we denote by $S_n$ the number of trees with one of your edges fixed, and then we follow, as to count the number of ways the directed edges can be added to form rooted trees where your edge is added first. As in original proof, we can pick the root in $n$ ways, and add the edges in $(n-2)!$ permutations (the difference is that we add your edge first). We arrive at $S_n n(n-2)!$ sequences.
Secondly, we will add edges one by one, but we will start with your edge (which is already picked). The only thing we need to pick is its direction. Then, we proceed usually with the rest, that is if there are $k$ forests, we can pick starting point in $n$ ways (any vertex) and ending point in $(k-1)$ (only the roots). When multiplied together we get (similarly to the original proof)
$$ 2\prod_{k=2}^{n-1}n(k-1) = 2n^{n-2}(n-2)!$$
Comparing the two we get
$$S_n n (n-2)! = 2n^{n-3}n(n-2)!$$
hence
$$S_n = 2n^{n-3}.$$
I hope this helps ;-)
A: Lemma 6 in this paper gives a stronger result: the number of labeled spanning trees on $n$ vertices containing any fixed forest. In your case of a single edge forest, the formula simplifies to $2n^{n-3}$.
