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?
Best Answer
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\}$.