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.7k 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.