Spanning Tree

Question

How to count the number of spanning tree?

Comments

I have a problem with $(1)$?

---

check my approach for 1 :
AB and AC should be included.
I am at C now I have two choices CD or CE-->2
if I pick CD again I have two choices DE or DF -->2
if I pick CE I have two choices ED or EF-->2
Total choices = 2*2*2

---

1) ED is a common edge in ist figure

remove common edge ED

Now , CDEF cycle is form

remove anyone from the CDEF = 4c1

now add ED

two cycles are formed {CED} {DEF}

2c1 -- > remove any one of the edge {CD} or {CE}

2c1 --- > remove any one of the edge {DF} or {EF}

Answer 1

1)

spanning tree will contain 5 edges out of 7 edges and edges AB and AC must be in spanning tree.

so, now, we have to select 3 edges out of 5. ==>5c3=10

But, we'll have to remove cycles i.e., CDE & EDF

so, total spanning tree=10-2=8.

--------------------------------------------------------------------------------------------------------------------------------------------

2)

Here, 4 edges to be selected out of 6.

total ways= 6c4=15

remove cycles==> if ABC then 3 invalid & if CDE then 3 invalid

so, total spanning tree= 15-6=9.

-----------------------------------------------------------------------------------------------------------------------------------

3)

4 edges to be selected out of 6.==> total = 6c4=15.

remove cycles=> if BDE then 3c1 & ABEC then 2c0

so, total spanning tree= 15-3-1=11.

Comments

@Mayankprakash in 1st part, we are selecting 3 edges. so, only traingles are invalid

while in 2nd part, we are selecting 4 edges. so, invalids are traingle+any edge=> which 3c1 for each traingle

---

@Naveen

Please help me in understanding as when we need to reject cycle and when to reject edges like you did first and second part.

Please suggest

Thanks

Mayank

---

spanning tree doesn't contain cycles. spanning tree just connects all the vertices.

so, In graph, you have to only select edges that connect all vertices & reject all cyclic parts.

observe: https://gateoverflow.in/202571/spanning-tree, https://gateoverflow.in/266403/zeal-test-descrete-math

you'll get it!