Number of spanning Trees

Question

Hi, 

As all of us knows number of spanning tree of simple labeled graph could be computed by the Kirchhoff's theorem. 

But is there any other method (other than Brute force) to compute the number of spanning tree of given general graph ?

Formula for number of spanning tree possible in Simple Labeled Complete graph($K_{n}$) and Simple Labeled Complete Bipartite graph($K_{m,n}$)  are $n^{n-2}$ and $n^{m-1}m^{n-1}$ respectively. 

If anyone can state simple proof for above mentioned formula then it will great help. 

Comments

one direct way to calculate ST (not MST) which i use is choose 'v-1' edges out of 'e' edges (graph contain 'v' number of vertices and 'e' number of edges)and then substract those 'v-1' edges which will result in cycle.

About proof of # of spanning tree in complete graph , it's by cayley's formula. you can see proof there.

---

@rupendra bro

Why to subtract v-1 edges in the end?

Please explain with an example if possible.

Thanks in advance

---

See this graph there are $v=5$ vertices and $e=6$ edges. We know spanning tree contains $v-1$ edges.So we first select $v-1$ edges from total e edges.

So it's like $\binom{6}{4}$. But out of those ways there may be some way which is resulting in a cycle , eliminate those.We can observe there are $4$ such possibilities which are causing cycle

1)this rectangular

2) triangle and one non-common edge of rectangular (there are 3 such edges of rectangular so 3 ways)

so total= $\binom{6}{4}$$-$$4$=$11$ Spanning trees

---

Correct me if iam wrong

---

Hello chandra

Please try to write clearly , because in that way we both can save our time.

you see this graph is isomorphic to the graph i provided in my example.

---

got my doubt clarified thank you sir

---

Hi rupendra,

I was also thinking about the same approach but was getting answer for complete graphs as I was not substracting the number of cycles formed. Thanks for adding that point.

But now also I am calculating the same by this approach and the formula n^n-2. But both of the answers are not same.

Am I missing some thing. Can you please explain if possible for K5.

Thanks in advance.

---

Hello harish

Number of total possible spanning trees in $K_{5}$

$ Method$ $1) $ :- $n^{n-2}$ $=$ $5^{3}$ $=$ $125$

$ Method$ $2) $ :- $\binom{10}{4}$ $-$ $15$ $-$ $70$ $=$$125$

in $K_{5}$ total edges $=$$10$ so for spnning tree we have to choose $4$ edges out of those $10$ edges.Now substract those $4$ edges which are causing some cycle.We can see cycle can be possible in two ways , first cycle itself can be of $4$ vertices and second when cycle is of $3$ vertices.

number of ways to have a cycle of length $4$ from a complete graph of $5$ vertices$=15$

https://gateoverflow.in/473/gate2012-38

Number of ways to have a cycle of $3$vertices $=10$  ,Now to choose $4$th vertex we have total $10-3=7$ ways so total became=$10*7=70$

---

Thanks rupendra, I got it now.

---

Hi Rupendra,
Can you please explain how you are getting 4 cycles.

---

Can you please tell which 4 are the cycles?