5 votes 5 votes Calculate the number of Spanning trees possible for each of these graphs Balaji Jegan asked Nov 5, 2018 Balaji Jegan 1.5k views answer comment Share Follow See all 23 Comments See all 23 23 Comments reply Balaji Jegan commented Nov 5, 2018 reply Follow Share I am getting : 81 77 27 0 votes 0 votes Sayan Bose commented Nov 5, 2018 reply Follow Share In the 2nd Fig,is O a node or just the pt of intersection of AC and BD? 0 votes 0 votes Utkarsh Joshi commented Nov 5, 2018 reply Follow Share Balaji Jegan for 1 i am getting 80. 0 votes 0 votes Mayankprakash commented Nov 5, 2018 reply Follow Share @balaji How bro? 0 votes 0 votes Mayank Gupta 3 commented Nov 5, 2018 i moved by Mayank Gupta 3 Nov 5, 2018 reply Follow Share Getting 64,61,24 0 votes 0 votes Utkarsh Joshi commented Nov 5, 2018 reply Follow Share Balaji Jegan in 2nd 5 vertices are there. We need to pick 4 edges from 8. answer will be less than 8c4=70. How are you getting 77? 0 votes 0 votes Utkarsh Joshi commented Nov 5, 2018 reply Follow Share For 1st, 3c2*3c2*3c2*3c2-8 (length 4 cycle) =73 0 votes 0 votes srestha commented Nov 5, 2018 reply Follow Share @balaji question is not correct u need to give weight to each edges Otherwise how do we calculate MST? 0 votes 0 votes srestha commented Nov 5, 2018 reply Follow Share is $(1,2)$ and $(1,3)$ same type of edge ? 0 votes 0 votes Sayan Bose commented Nov 5, 2018 reply Follow Share @srestha, if we use Kirchoffs algo, why would we require edge weights to determine spanning trees? Qstn didn't ask for min or max spanning tree 1 votes 1 votes Deepanshu commented Nov 5, 2018 reply Follow Share 2nd one 69 3rd one 54 0 votes 0 votes srestha commented Nov 5, 2018 reply Follow Share @Sayan then there will be no cycle right? So, 1st one will be $\binom{3}{2}\times \binom{3}{2}\times \binom{3}{2}\times \binom{2}{1}=54$ 1 votes 1 votes srestha commented Nov 5, 2018 reply Follow Share 2nd one will be $\binom{4}{3}\times \binom{4}{1}=16$ 3rd one will be $\binom{3}{2}\times \binom{3}{2}\times \binom{2}{1}=18$ 0 votes 0 votes Deepanshu commented Nov 5, 2018 reply Follow Share srestha mam for 3 rd one refer to this https://gateoverflow.in/10154/find-out-the-no-of-spanning-tree-possible 0 votes 0 votes srestha commented Nov 5, 2018 i edited by srestha Nov 5, 2018 reply Follow Share but is spanning tree means , $1$ edge need to be removed from the subgraph? Spanning tree means , every vertex need to be enclose and also no cycle will be there right? So, how can we tell if there is 5 edges, there wouldnot be any cycle? 0 votes 0 votes Deepanshu commented Nov 5, 2018 reply Follow Share srestha mam if u r referring to link i added then they take care of that case earlier so atlast only 5 edges cases remaining 0 votes 0 votes srestha commented Nov 5, 2018 reply Follow Share I need to draw the graph now otherwise, I havenot got any error in my answer too. Is there any answer given @Balaji?? or self doubt? 0 votes 0 votes Balaji Jegan commented Nov 5, 2018 reply Follow Share self doubt 0 votes 0 votes srestha commented Nov 5, 2018 reply Follow Share then do I give the picture I got? because it cannot be even checked :( 0 votes 0 votes srestha commented Nov 5, 2018 reply Follow Share plz chk my comment here https://gateoverflow.in/261720/ace-test-series 0 votes 0 votes Balaji Jegan commented Dec 21, 2018 reply Follow Share @Sayan Bose O is a vertex 0 votes 0 votes HeadShot commented Jan 4, 2019 reply Follow Share @adarsh_1997 I am getting : 792 - ( 468+32+56+4+4) = 228. Please help to point out my mistake. 0 votes 0 votes rish1602 commented Jun 21, 2021 reply Follow Share Adding to the answer, I’m getting for 1st 54 for 2nd 48 for 3rd 18 0 votes 0 votes Please log in or register to add a comment.