Zeal Test Series 2019: Graph Theory - Counting

Question

Is there any short trick to do it ?

Comments

324

if all the vertices are labeled

---

I'm getting 8*3*15=360

---

i'm getting the same  Naveen Kumar 3

---

yeah 360 ist time i did calculation mistake

Answer 1

Observe the given graph(rectangular+traingle+hexagon)

Spanning tree contains no cycles. & connects all vertices.

for rectangular area=> select 3 out of 5 edges & remove 2 traingular cycle = 5c3-2 = 8

for traingular area=> select 2 out of 3 edges = 3c2 = 3

for hexagonal area=> select 5 out of 7 edges & remove cycles(formed by 4 edges with any 1 edge out of remaining 3 edges) = 7c5-2(3c1) = 21-6 = 15.

so, total possible spanning tree = 8*3*15= 360.

Comments

https://gateoverflow.in/262814/spanning-tree see this also, you will get it.

---

@naveen thnxx very much for this explanation it really helped -https://gateoverflow.in/262814/spanning-tree 

---

 Thnx