71 votes 71 votes Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which of the following statements is always TRUE? There exists a cutset in $G$ having all edges of maximum weight. There exists a cycle in $G$ having all edges of maximum weight. Edge $e$ cannot be contained in a cycle. All edges in $G$ have the same weight. Algorithms gateit-2005 algorithms spanning-tree normal + – Ishrat Jahan asked Nov 3, 2014 edited Nov 17, 2017 by kenzou Ishrat Jahan 20.4k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments JashanArora commented Jan 5, 2020 reply Follow Share @vaibhav101 Your reasoning is absolutely correct for graphs with distinct weights. But, imagine a graph with a cycle, and all edges weighing 500. The question permits such graphs. 1 votes 1 votes neeraj_bhatt commented Jan 22, 2020 reply Follow Share If MST contains max weight edge e, then e must be a bridge(it is a necessity to include e). Moreover the cut-set will contain e, but we can now keep on adding other edges in the cut-set and it'll remain a cut-set. So, there is a possibility that all the max value edges are present in the cut-set. Hence, A is definitely correct. 0 votes 0 votes Gajanan Purud commented Sep 17, 2023 reply Follow Share 😎 0 votes 0 votes Please log in or register to add a comment.
–4 votes –4 votes 3 will be always true. There is no cycle in a minimum spanning tree ever. Gate Keeda answered Nov 3, 2014 Gate Keeda comment Share Follow See all 3 Comments See all 3 3 Comments reply Arjun commented Nov 4, 2014 reply Follow Share (c) option says whether e is part of a cycle in the original graph- not in the minimum spanning tree. 0 votes 0 votes Arjun commented Mar 21, 2015 reply Follow Share not really. Consider the case when all edges in cycle are of same weight. 0 votes 0 votes Arjun commented Mar 21, 2015 reply Follow Share maximum weight can be repeated unless edge weights are unique. Options B and C are true but need not be always. A is true always. 1 votes 1 votes Please log in or register to add a comment.