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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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, 2019 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, 2019 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, 2019 at 17:24
  • $\begingroup$ Thank you sir, i will refer to some lecture notes. $\endgroup$
    – Nascimento de Cos
    Nov 10, 2019 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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