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?

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}$.
