Spanning Trees of the Complete Graph minus an edge

Question

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads...

Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number of spanning trees of $A$.

So how I approached this problem was by creating the Laplacian of A. I set the edge to be deleted as the edge between the first and second vertices in the graph. After an obscene amount of potentially dubious matrix operations, I received a result of...

$n^{n-3}*[2n^{3}-5n^{2}+3n \pm 1]$

Can anyone shed some light on this problem? I feel as I am approaching it the wrong way...

Answer 1

There's no need to consider the Laplacian. We can obtain this by a simple symmetry argument.

Every edge of the complete graph is contained in a certain number of spanning trees. By symmetry, this number is the same for each edge, call it $k$. Let us now count the total number of edges in all spanning trees in two different ways.

First, we know there are $n^{n-2}$ spanning trees, each with $n-1$ edges. Therefore there are a total of $(n-1)n^{n-2}$ edges contained in the trees.

On the other hand, there are $\binom{n}{2} = \frac{n(n-1)}{2}$ edges in the complete graph, and each edge is contained in precisely $k$ trees. This means there are a total of $\binom{n}{2}k$ edges.

This gives us $$(n-1)n^{n-2} = \binom{n}{2}k$$ which upon simplification gives $k=2n^{n-3}$.

If we delete an edge, then we effectively remove the set of all spanning trees containing that edge. By assumption that number is $k$. Therefore there will remain $$n^{n-2} - k = n^{n-2} - 2n^{n-3} = n^{n-3}(n-2)$$ total spanning trees.

Answer 2

Maybe an easier approach is to first count the number of spanning trees that containing that edge (which I think is equal to: $$\sum_{k=0}^{n-2} C(n-2,k) (k+1)^{k-1} (n-k-1)^{n-k-3}$$)

and subtract it from total $n^{n-2}$ spanning trees.