GATE IT 2005 | Question: 52

Question

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?

• A. There exists a cutset in $G$ having all edges of maximum weight.
• B. There exists a cycle in $G$ having all edges of maximum weight.
• C. Edge $e$ cannot be contained in a cycle.
• D. All edges in $G$ have the same weight.

Comments

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

---

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.

---

😎

Answer 1

Option $A$ is correct.

Questions says the MST of graph $G$ contain an edge $e$ which is a maximum weight edge in $G$. Need to choose the answer which is always true to follow the above constraint.

Case 1:

Option B says that if edge $e$ is in MST then for sure there is a cycle having all edges of maximum weight. But it is not true always because when there is only n-1 edges( but no cycle) in graph then also maximum edge has to be taken for MST.

Case 2:

Option C says otherwise. That if e is in MST then it cannot be in any cycle that is wrong as if there is a cycle with all maximum edges then also e will be in MST

Option D says all edges should be of same weight same explanation if there are $n-1$ distinct edges( but no cycle)  in $G$ then have to take all edges including maximum weight edge.

And at last option A says if e is in MST then for sure there is a cut-set ( A subset of Edge set of G whose removal disconnects the graph) in $G$ having all edges of maximum weight. And it is true.

Because then only we maximum weight edges has to be taken in MST.

For eg. If there are $n-1$ edges (but no cycle) then if edge e is not taken in the MST then MST will not be connected.

Comments

Cut Set is A MINIMAL set of edges......not MINIMUM, some admin correct it.

---

Option A :: There exists a cutset in G having all edges of maximum weight - This means, Edges in the cut set have same weight. 

 

There exists a cutset in G having all edges of maximum weight of G - This means cut set contains all the edges of G whose weight is equal to maximum weight

---

Shaik Masthan

aren’t both statements same?

Answer 2

Option A is correct.

Here, in this example we can easily see that B, C, D are false. So, B,C,D are not always true.

  that's why A is always true..  A (Ans)

Comments

for eliminating option b, take a diagonal edge with weight 2 in the above graph. (option says all edges)

 

cutset is the minimum edge set whose removal disconnects the graph.

option a will always be correct as more than 1 e have to be there for it to be in mst, leaving us no choice to select it, so it has to be in cutset because its only beacuse of its selection we got a mst which is connected.. case 2: also if we take e if its removal disconnects the graph on single occurance, that also relates with cutset defination

---

I understood why option B C D cannot be the answer but can you please clarify the reason for option A?

An edge cut set is a set of edges of a graph which, if removed (or "cut"), disconnects the graph (i.e., forms a disconnected graph). Reference: http://mathworld.wolfram.com/EdgeCutSet.html

By removing one of the edges with weight=2 we cannot disconnect the graph. By removing 2 such edges we can disconnect it. Since it has not been asked to get the minimum cut-set so we can remove 3 such edges and can get 3 connected components(one with an edge and other two pendant vertices). So now the cut-set has all the edges with max weight.

---

it has written always bro @28

Answer 3

Option a is always true

Option b is not true when e is not part of a cycle.

Option c is not true when e is part of a cycle and all edge weights are same in that cycle

Option d is need not be true when e is not part of a cycle

Option a is always true as only the min weight edge in a cut set will be part of a minimum spanning tree.

Comments

pooja, u can check my answer.

---

can you proof option A with an example

---

U hav explained option A wrong ... according to that question ... they hav considered max weight edge ... not minimum one ...

Answer 4

(A) True, because if there is heaviest edge in MST, then there exist a cut with all edges with weight equal to heaviest edge.

(B) False, because the cutset of heaviest edge may contain only one edge.
(C) False. The cutset may form cycle with other edge.
(D) False. Not always true.