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: The    reader   is    asked    to   consult    the   following    MSE
link           for
references and additional documentation. 
We will provide  a closed form of the  exponential generating function
of the quantities that are involved.
The species of labelled trees has the specification
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = 
\mathcal{Z} \times \textsc{SET}(\mathcal{T})$$
which gives the functional equation
$$T(z) = z \exp T(z).$$
We   have   by   Cayley   that
$$T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}.$$
We get from the functional equation
$$T'(z) = \exp(T(z)) + z \exp(T(z))  T'(z)$$
so that
$$T'(z) = \frac{\exp(T(z))}{1-z\exp(T(z))}
= \frac{T(z)/z}{1-zT(z)/z}
= \frac{1}{z} \frac{T(z)}{1-T(z)}$$
With these  preliminaries we  can answer the  question. We  may assume
from  symmetry considerations  that the  two edges  are $\{1,2\}$  and
$\{3,4\}.$  We   now  attach  the   tree  to  a  horizontal   line  by
straightening the unique path containing  the two edges and placing it
on the  line.  There are  four possibilities  for the ordering  of the
four nodes on  the line. Let $\mathcal{S}$ be  the combinatorial class
of trees  with two nodes marked  which includes two marks  on the same
node, so that
$$S(z) = \sum_{n\ge 1} n^2 n^{n-2} \frac{z^n}{n!}
= \sum_{n\ge 1} n n^{n-1} \frac{z^n}{n!}
= z \frac{d}{dz} T(z) = \frac{T(z)}{1-T(z)}.$$
Observe that the  tree matched to the line has  five components. There
are sets of trees, possibly  empty, attached to the four distinguished
nodes. The fifth component is a tree  at the center that has two nodes
marked where the trees sustained by the two special edges are attached
to it. The  latter may be empty  which is the case of  an edge between
the two special ones. This is where  we use the fact that the marks in
$\mathcal{S}$ are ordered, which  enforces the distinction between the
attachment locations of the first and the second special edge.
We get the specification
$$\mathcal{Q} = 
\textsc{SET}(\mathcal{T}) \textsc{SET}(\mathcal{T})
\times (\epsilon + \mathcal{S}) \times
\textsc{SET}(\mathcal{T}) \textsc{SET}(\mathcal{T})$$
This yields for the EGF the closed form
$$G(z) = \exp(T(z))\exp(T(z)) 
\times \left(1 + \frac{T(z)}{1-T(z)} \right) \times
\exp(T(z))\exp(T(z))$$
which simplifies to
$$G(z) = \frac{\exp(4T(z))}{1-T(z)}
= \frac{T(z)^4}{z^4 (1-T(z))}.$$
Extracting coefficients via Lagrange inversion we have
$$Q_n = n! [z^n] G(z) =
n! \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\frac{T(z)^4}{z^4 (1-T(z))} \; dz.$$
Put $T(z)=w$ so that $z=w/\exp(w) = w\exp(-w)$ and 
$dz = \exp(-w) - w\exp(-w)$ 
to get
$$n! \frac{1}{2\pi i}
\int_{|w|=\gamma} 
\frac{\exp(w(n+5))}{w^{n+5}} 
\frac{w^4}{1-w} 
(\exp(-w) - w\exp(-w)) \; dw
\\ = n! \frac{1}{2\pi i}
\int_{|w|=\gamma} 
\frac{\exp(w(n+4))}{w^{n+1}} \; dw
\\ = n! [w^n] \exp(w(n+4)) = (n+4)^n.$$
Now these are the  nodes that do not include the  four special ones. A
target tree is obtained  from an element of $Q$ by  adding four to the
labels of all  nodes, which together with the  special ones constitute
the set of $n$ unique  labels.  Making the appropriate adjustments and
taking  into account  the four  possible orientations  of the  pair of
special edges we obtain the closed form
$$\bbox[5px,border:2px solid #00A000]{
4 \times n^{n-4}.}$$
and zero for $n\lt 4.$ The sequence starting at $n=4$ goes like this:
$$4, 20, 144, 1372, 16384, 236196, 4000000, 77948684, 
\\ 1719926784, 42417997492, 1157018619904, \ldots$$
The  first  five entries  were  verified  by enumeration  through  the
following Maple routine.

with(combinat);

pruef2tree :=
proc(a)
local deg, tree, u, v, p, q, n;

    n := nops(a) + 2;

    deg := [seq(1, q=1..n)];

    for q to n-2 do
        deg[a[q]] := deg[a[q]] + 1;
    od;

    tree := [];

    for q to n-2 do
        p := 1;

        while deg[p] <> 1 do
            p := p + 1;
        od;

        tree := [op(tree), {p, a[q]}];

        deg[p] := deg[p] - 1;
        deg[a[q]] := deg[a[q]] - 1;
    od;

    for u to n do
        if deg[u] = 1 then break fi;
    od;

    for v from u+1 to n do
        if deg[v] = 1 then break fi;
    od;

    [op(tree), {u, v}];
end;

trees_12_34 :=
proc(n)
option remember;
local ind, d, a, edges, q, res;

    if n = 1 then return 0 fi;

    res := 0;

    for ind from n^(n-2) to 2*n^(n-2)-1 do
        d := convert(ind, base, n);
        a := [seq(d[q]+1, q=1..n-2)];

        edges := pruef2tree(a);

        if {1,2} in edges and {3,4} in edges
        then
            res := res + 1;
        fi;
    od;

    res;
end;

T := solve(TF=z*exp(TF), TF);

X1 := n ->
`if`(n<4, 0, 4*(n-4)! * coeftayl(exp(4*T)/(1-T), z=0, n-4));

X2 := n ->
`if`(n<4, 0, 4*(n-4)! * coeftayl(T^4/(1-T)/z^4, z=0, n-4));

XX := n -> `if`(n<4, 0, 4*n^(n-4));

A: Here's a low-tech answer using Prüfer codes. Let's start by answering a couple of related questions.
How many trees are there containing $e$? Without loss of generality, we can assume $e = \{n, n - 1\}$. Then trees containing $e$ correspond exactly to Prüfer codes that end in either $n - 1$ or $n$. So there are $2n^{n - 3}$ of them.
How many trees are there containing adjacent edges $e$ and $f$? Without loss of generality, we can assume $e = \{n, n - 1\}$ and $f = \{n, n - 2\}$. Then these trees correspond exactly to Prüfer codes that end in $n$ and whose next-to-last entry is one of $\{n - 2, n - 1, n\}$. So there are $3n^{n - 4}$ of them.
Now for some counting. Suppose that if $e$ and $f$ are disjoint then there are $k$ trees containing both. If we list out every tree containing $e$, then this consists of $2n^{n - 2} \cdot (n - 2)$ non-$e$ edges. All the $2( n -2)$ edges adjacent  to $e$ show up on this list $3n^{n - 4}$ times, and all the $\binom{n}{2} - 2( n - 2) - 1$ edges not adjacent to $e$ show up $k$ times. This is true by the symmetry of $K_n$. So $$2n^{n - 3} \cdot (n - 2) = 2( n -2) \cdot 3n^{n - 4} + \left(\binom{n}{2} - 2( n - 2) - 1 \right) \cdot k$$
which means
$$
\begin{align}
k &= \frac{2 n^{n - 3} \cdot (n - 2) - 2( n -2) \cdot 3n^{n - 4} }{\binom{n}{2} - 2( n - 2) - 1} \\
&= 4 n^{n - 4} 
\end{align}
$$
as required.
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}.
$$
