6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – EuYu Feb 7 '14 at 5:22
  • $\begingroup$ 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... $\endgroup$ – Arek Krawczyk Feb 7 '14 at 7:58
  • $\begingroup$ 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. $\endgroup$ – EuYu Feb 7 '14 at 16:04
  • $\begingroup$ 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. $\endgroup$ – Especially Lime Feb 3 '17 at 6:47
9
$\begingroup$

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:

enter image description here

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.