Spanning tree for a simple, complete graph minus an edge

Question

Hello everyone interested. Here's a problem I can't figure out. I wish to find the number of spanning trees in a simple, complete graph G with at least three vertices after I remove one of its edges.

I tried counting but even for small values of n this becomes hard. Is there a theorem or some other result I could employ?

Thanks in advance...

Answer 1

It is not hard to prove by induction on the number of components (using prufer codes and newtons formula) that if $G$ is a forest with components of size $c_1,c_2,\dots , c_k$ then the number of spanning trees containing $G$ is $n^{k-2}\prod\limits_{i=1}^n c_i$.

In your particular case the forest has $n-1$ components of sizes $2,1,1,1\dots$

And so the number of trees not containing the edge is $n^{n-2} -2n^{n-3}$

Answer 2

Hint: The number of spanning trees without removing the edge is given by the Cayley formula. Given that a tree contains exactly $n-1$ edges, and given that the problem is symmetric (it doesn't matter which edge you remove), you can count in two ways the number of elements in the set $\{(e,T): e \text{ is an edge}, T \text{ is a tree containing }e\}$.