16 votes 16 votes How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges). Algorithms gate1995 algorithms graph-algorithms spanning-tree easy descriptive + – Kathleen asked Oct 8, 2014 recategorized Apr 25, 2021 by Lakshman Bhaiya Kathleen 5.0k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply `JEET commented Dec 24, 2019 reply Follow Share @Satbir @ankitgupta.1729 @techbd123 @imShreyas I want to solve this by $\mathbf{PnC}$. I know answer is $\mathbf 2$ only as I have verified it by drawing. But with permuation, for $\mathbf 3$ we have $2-\textbf{choices}$ and for $4$ we again have $2$ choces. $\therefore$ Ans $=2\times 2 = 4$ What's wrong here? 0 votes 0 votes Satbir commented Dec 24, 2019 reply Follow Share For 3 we have 1 choice. 0 votes 0 votes `JEET commented Dec 24, 2019 reply Follow Share We can take any $3$, isn't it?? So $2$ choice? 0 votes 0 votes Satbir commented Dec 24, 2019 reply Follow Share see the daigram in answer both 3 are taken , only 4 has 2 choices which are taken in diagram. 0 votes 0 votes `JEET commented Dec 24, 2019 reply Follow Share Oh, yes actually that was the mistake I was doing. I was thinking that at one of point of time, i can take any of the $3$. So, if this $3$ would not have come in the diagram again then it would have been two choices, right? 0 votes 0 votes Human commented Feb 14, 2020 reply Follow Share The question is a bit ambiguous. It asks for minimum spanning tree which is 13 for this graph. Whereas the answer they are expecting is for number of minimum cost spanning tree which is 2. 0 votes 0 votes sameer_hack commented Jan 25, 2023 reply Follow Share “Minimum Spanning Tree” directly means that we have to find a spanning tree which is of minimum cost. The question is not ambiguous.@Human 0 votes 0 votes Please log in or register to add a comment.
Best answer 31 votes 31 votes $2$ only. $\{AB,BC,AE,BD\}$ and $\{AB,BC,AE,CD\}$. Gate Keeda answered Oct 8, 2014 edited May 6, 2019 by Lakshman Bhaiya Gate Keeda comment Share Follow See all 0 reply Please log in or register to add a comment.