Spanning trees of the complete graph minus two edges Here is the following problem:
What two edges should one remove from the complete graph $K_n$ so that the number of the spanning trees of the new graph is as small as possible? 
One can solve this problem of course by computing the determinant of the Laplacian matrix associated to this graph, however I was wondering if there is some more elegant solution involving perhaps some intelligent counting, like say for the problem of counting the number of the spanning trees when we remove just one edge instead.
 A: Let $A(e_1,e_2)$ be the number of spanning subtrees of $K_n$ containing both $e_1$ and $e_2$.
We want to minimize $A(e_1,e_2)$.
If $e_1$ and $e_2$ are adjacent then we can count exactly how many trees have $e_1$ and $e_2$. To do this contract those edges into a single vertex $v$, for each spanning tree in the new graph with $n-2$ vertices there are $3^{d(v)}$ spanning trees on all $n$ vertices.
So using the prufer code we can see there are $\sum_{i=0}^{n-4}3^{i+1}\binom{n-4}{i}(n-3)^{n-4-i}$ trees in total.
If $e_1$ and $e_2$ are not adjacent then we can also count exactly how many trees have $e_1$ and $e_2$ exactly, we do the same trick (contract each edge into vertices $v_1,v_2$), but now we notice that for each spanning tree on the new graph with $n-2$ vertices there are $2^{d(v_1)+d(v_2)}$ spanning trees on all $n$ vertices
So using the prüfer code we can see there are $\sum_{i=0}^{n-4}\binom{n-4}{i}2^{i+2}2^i(n-4)^{n-4-i}$
Since there are $\binom{n}{i}$ ways to pick the $i$ vertices that are $v_1$ or $v_2$ and $2^i$ ways to split them (between $v_1$ and $v_2$).
So all that remains is to compare:
$\sum_{i=0}^{n-4}\binom{n-4}{i}3^{i+1}(n-3)^{n-4-i}$ and $\sum_{i=0}^{n-4}\binom{n-4}{i}4^{i+1}(n-4)^{n-4-i}$
But using the binomial theorem, the sum on the left is:
$3n^{n-4}$ and the sum on the right is $4n^{n-4}$, so the left is smaller.
