Let $e$ be an edge of $K_n$- the complete graph on $n$ vertices. Prove that the number of labelled spanning trees of $K_n-e$ is $(n-2)n^{n-3}$.

I think the answer lies in using some modified form of Prüfer's sequence but I can't quite nail it.

  • $\begingroup$ The vowels 'u' and 'ü' are graphically and historically but not phonetically related, so omitting the dieresis distorts the word as much as replacing the vowel by any other vowel. (If you don't have characters with diacritical marks on your keyboard, you can copy them e.g. from the corresponding Wikipedia articles.) $\endgroup$ – joriki Jun 20 '16 at 7:47
  • $\begingroup$ @joriki The spelling Pruefer is also acceptable, right? $\endgroup$ – bof Jun 20 '16 at 8:15
  • $\begingroup$ @bof: Historically, the umlaut and the corresponding simple vowel followed by an 'e' were interchangable (in fact the two dots for the umlaut arose as an abbreviated version of a superscript 'e'), and this is still reflected in the correct spelling of many names, e.g. Noether. But nowadays this is only a substitute used e.g. when typing quickly on an English keyboard; it wouldn't be acceptable in a publication as a spelling of "Prüfer". $\endgroup$ – joriki Jun 20 '16 at 8:21

You know that $K_n$ has $n^{n-2}$ spanning trees, right? You want to find out how many of those spanning trees do not contain the edge $e.$ You can do that by finding the number of spanning trees that do contain $e$ and subtracting that from $n^{n-2}.$

By symmetry, each edge of $K_n$ is in the same number of spanning trees, call that number $t.$ Let $p$ be the number of pairs $(T,e)$ where $T$ is a spanning tree of $K_n$ and $e$ is an edge of $T.$

On the one hand, $p=\binom n2t,$ since there are $\binom n2$ edges and each edge is in $t$ spanning trees.

On the other hand, $p=n^{n-2}(n-1),$ since there are $n^{n-2}$ spanning trees and each spanning tree contains $n-1$ edges.

Solving the equation $\binom n2t=n^{n-2}(n-1)$ for $t,$ we get $t=2n^{n-3}.$

Finally, the number of spanning trees of $K_n-e$ is $$n^{n-2}-2n^{n-3}=\boxed{(n-2)n^{n-3}}.$$


The last entry in the Prüfer code is one of the two highest labels if and only if the edge between them exists, so the number of trees with that edge is $2n^{n-3}$.


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.