# 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?

• Contraction-Deletion doesn't apply here the way you want it to. In particular, the edge contraction of $K_{n+1}$ doesn't give $K_n$. Instead, there are $2$ edges incident on the contracted vertex. So while it's a valid formula, the resulting graph is not a simple complete graph and so Cayley's theore no longer applies. – EuYu Feb 7 '14 at 5:22
• Why doesn't Cayley's formula apply here? A spanning tree of edge contracted $K_{n+1}$ only uses one of the double edges between the contracted vertex and all other ones, so we could form a bijection between such spanning tree and a spanning tree $K_n$. Does the fact which edge is used make such a difference? I thought that Cayley's formula only differentiated between which vertices are connected, and not which edges were used... – Arek Krawczyk Feb 7 '14 at 7:58
• Distinguishing between which vertices are used is equivalent to distinguishing between which edges are used for a simple graph. Any two vertices uniquely determine an edge in that case. To see why multiple edges must be considered, try your argument on $K_3$. $K_3$ has three spanning trees. If you contract an edge without considering multiple edges, you get $K_2$ which has a single spanning tree. Then your formula says $K_3\cdot e$ has two spanning trees, which is incorrect. – EuYu Feb 7 '14 at 16:04
• Your notation is nonstandard. Normally $G/e$ is the contracted graph. Some people use $G\setminus e$ for the graph with $e$ deleted, but since these notations are easy to mix up many people just use $G-e$ for that. – Especially Lime Feb 3 '17 at 6:47

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

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}.$$

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)$.