2
$\begingroup$

What is the number of spanning trees in an undirected simple graph?

My attempt:

Let $m$ be the number of edges in a simple graph, and let $n$ be the number of vertices.

Then number of spanning trees is $\binom{m}{n-1}$ minus the number of cycles of length $n-1$.

I read on Wikipedia that the number of spanning trees in the complete graph $K_n$ is $n^{n-2}$.

According to the formula I stated above, it should be $\binom{n(n-1)/2}{n-1} - \binom{n}{n-1} (n-1)!$.

How do I show that this is equal to $n^{n-2}$ for $K_n$?

$\endgroup$
1
$\begingroup$

You cannot show this since it isn't true. I encourage you to try out some actual numbers (e.g. $n=2$) and see for yourself that the numbers don't match. The problem is that what you should be subtracting is not the number of cycles of length $n-1$, but rather the number of collections of $n-1$ edges which contains at least one cycle. Such a collection need not be a cycle of length $n-1$.

In addition, the formula for the number of cycles of length $n-1$ is wrong. The number is $n(n-2)!$ rather than your $n(n-1)!$, and even this formula is only valid for $n \geq 4$ (for smaller $n$ there are no such cycles). However, even after replacing $n(n-1)!$ by $n(n-2)!$, the numbers don't match.

$\endgroup$
  • $\begingroup$ sir i got what you are saying. Can you please elaborate how you wrote formula for number of cycles of length n-1: What i did was --> choose n-1 vertices out of n vertices. Cycle is permutation of n-1 vertices. SO i thought it was nC(n-1)*(n-1)! . I have recently started studying graph theory. I was just thinkng about this problem. I saw some proofs based on kirchofs theorem etc which was way above my head. How the equivalence between that laplacian matrix and number of trees was established ? $\endgroup$ – Nascimento de Cos Nov 10 '19 at 15:42
  • $\begingroup$ I wrote wrongly. It should be number of collections of size n-1 with cycle in it. $\endgroup$ – Nascimento de Cos Nov 10 '19 at 15:45
  • $\begingroup$ The matrix tree theorem is a standard result, and there are many lecture notes and textbooks covering it. If it’s above your head then you’ll need to step up to it. $\endgroup$ – Yuval Filmus Nov 10 '19 at 17:24
  • $\begingroup$ Thank you sir, i will refer to some lecture notes. $\endgroup$ – Nascimento de Cos Nov 10 '19 at 19:08

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.