Spanning trees

Question

Find the number of spanning trees in the following graph;

Comments

Bro they have followed same approach..see the BEST ans.

---

Yes, it is same but could not understand the part of selecting cycles of length 3,4 and 5?

Would you please elaborate that ?

---

Plz tag me @ that question . Else people will misinterprete this question.

Answer 1

Spanning Trees of above graph means

1. Subgraph of given graph
2. It should be edge cover
3. It should be a tree

Here tree Contains n-1 Edges =5 Edges

Total edges in the graph=7

Here No of Spanning tree = All possible Subgraphs which contains 5 edges out of 7 edges  -  5edged Subgraph but not Spanning tree due to presence of  Cycle 

 So No. Of spanning tree= 7C5 - (3+3)= 21-6=15 is Ans

The following 6 subgraphs are 5-edged but not spanning tree bcz they contain cycle

So Ans is 15

Comments

Can you please tell me why you subtracted 6?

---

Spanning tree should never contain cycles but above drawn 6 subgraphs violates this property. So they are excluded.

Take any subgraph having 5edges except this 6 drawn graphs..It is a spanning tree.