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.1k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments `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.