How many different spanning trees of $K_n \setminus e$ are there?

I need to know how many different spanning trees of $K_n \setminus e$ are there. $K_n \setminus e$ is a graph created by removing one of the edges of a full graph $K_n$.

Well as we all know the number of spanning trees of a full graph is $n^{n-2}$. But graphs fulfill the deletion-contraction rule, meaning that $\tau$ being the number of spanning trees fulfills the following equality.

$\tau(K_n)-\tau(K_n / e)=\tau(K_n \setminus e)$, where $K_n / e$ is a graph made by joining two vertices at the end of edge $e$ and connecting it to all neigbours of edges that lie on $e$. But $K_n / e$ is $K_{n-1}$, right? It has $n-1$ vertices and each an every one of them connects to each other. Therefore $\tau(K_n \setminus e)=n^{n-2}-(n-1)^{n-3}$, right?

Or does deletion contraction rule not apply to simple graphs?

Solution 1:

We create a bipartite graph. In one part we have the $n^{n-2}$ labeled spanning trees of $K_n$, and in the other part we have the $\binom{n}{2}$ edges in $K_n$, and we draw an edge between two vertices whenever a tree contains an edge. It'll looks something like the image below:

Trees have $n-1$ edges, so the degree of every tree vertex in the above graph is $n-1$. By symmetry, every edge in $K_n$ belongs to the same number of trees, say $d$, which is also the degree of any edge vertex in the above graph. Hence the number of edges in the above graph is $$n^{n-2} (n-1)=d \binom{n}{2}$$ which implies that $$d=\frac{n^{n-2} (n-1)}{\binom{n}{2}}=2n^{n-3}.$$

The number of trees that contain a given edge is $d$, so the number of trees that don't contain that edge is $$n^{n-2}-d=n^{n-3}(n-2).$$ This is also the number of labeled spanning trees of $K_n \setminus \{e\}$.

Solution 2:

Your notation is confusing, but I think you want the number of spanning trees in the graph $K_n-e$, obtained by removing one edge from the complete graph $K_n$. In other words, you want the number of spanning trees in $K_n$ which do not contain a given edge $e$.

Each spanning tree contains $n-1$ of the $\binom n2$ edges of $K_n$, that is, the proportion $\dfrac{n-1}{\binom n2}=\dfrac2n$ of all the edges. Equivalently, a given edge $e$ belongs to $\dfrac2n$ of all the spanning trees, and is omitted by $\dfrac{n-2}n$ of all the spanning trees. Since the total number of spanning trees is $n^{n-2}$, the number of spanning trees omitting $e$ is$$\frac{n-2}n\cdot n^{n-2}=(n-2)n^{n-3}.$$

Solution 3:

Another way to solve this is to use Prüfer Code (Wikipedia), a sequence of $n-2$ numbers each from $1$ to $n$ that uniquely identifies all $n^{n-2}$ spanning trees, where n is the number of vertices.

Without the loss of generality (due to isomorphism), we can label the two vertices containing the edge that is deleted as "$n$" and "$n-1$".

Since in the process of constructing Prufer code, we always remove the smallest labeled leaf vertices, $e$ will always be the last edge left. Therefore, the last removed leaf must be attached to either the vertex with label n, or n-1, making the last element of the generated Prüfer code n, or n-1.

For all spanning trees, we have $n^{n-2}$ of them because in Prüfer code, there are $n$ choices each for the $n-2$ slots. Instead of having $n$ choices for the last element of the Prufer code, we have two. As a result, there are $2n^{n-3}$ spanning trees using edge e, and $(n-2)n^{n-3}$ spanning trees in $(G-e)$.