Q:

Number of labelled trees on $n$ vertices containing $2$ fixed non-adjacent edges

Let $n\in \mathbb{N}$. Choose $e,f$ two disjoint pairs of integers in $1,...,n$. How many labelled trees on $n$ vertices ($1, 2, ..., n$) are there such that $e,f$ are edges of the tree?
I could not proceed in any way which made any significant progress. Any hints/ideas ?

A:

Such problems can generally be solved by using Prüfer codes, which let us count trees with a prescribed degree for some specific vertices.
Take your tree on vertices $\{1,2,\dots,n\}$ containing edges $e$ and $f$, and contract these two edges. This gives us a tree on $n-2$ labeled vertices, two of which are the contracted vertices $x_e$ and $x_f$. (At this point we know that there are $(n-2)^{n-4}$ such trees, but that doesn't help us yet.
Each such tree can be expanded to an $n$-vertex tree in $2^{\deg(x_e) + \deg(x_f)}$ ways: for each edge incident to $x_e$ (respectively, to $x_f$) we have to choose an endpoint of $e$ (respectively, of $f$) it will connect to in the expanded tree.
The number of trees on $n-2$ vertices in which $\deg(x_e) = i+1$ and $\deg(x_f) = j+1$ is $\frac{(n-4)!}{i!\,j!\,(n-4-i-j)!} (n-4)^{n-4-i-j}$: this is just the number of Prüfer codes in which $x_e$ appears $i$ times and $x_f$ appears $j$ times. So we can count the number of trees we want by
$$
   \sum_{i,j\ge 0}^{i+j \le n-4} 2^{(i+1)+(j+1)} \cdot \frac{(n-4)!}{i!\,j!\,(n-4-i-j)!} (n-4)^{n-4-i-j}.
$$
By the multinomial theorem, this is just
$$
   4 \sum_{i,j \ge 0}^{i+j \le n-4} \binom{n-4}{i,j,n-4-i-j} 2^i 2^j (n-4)^{n-4-i-j} = 4 (2 + 2 + (n-4))^{n-4} = 4n^{n-4}.
$$

