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

mainly here we have to focus on 2 things firstly we have to be take care of our graph(G) must have max weight edge(e) and their MST will also contain e. and latter question are not asking about MST they will ask about (G) then for that if u able to draw a graph like himanshu  done then u easily eliminate the option B,C,D without caring of A  wheather u know or dont know the meaning of option A .

---

Cutset  is set of edges that once removed from graph yields a disconnected graph.  To ensure connectiveness of MST we must have an edge of cutset to be part of MST.  

Hence A is true in all the cases

---

For example check

https://www.geeksforgeeks.org/gate-gate-it-2005-question-52/

---

I have a doubt:

1. The edge with the maximum weight is present in an MST iff it is a bridge

2. An edge cannot be a bridge if it is part of a cycle.

Therefore, the max weight edge cannot be part of a cycle if it is part of some MST.

 

What is wrong with my reasoning?

---

brainstorming one :-D

---

@vaibhav it is not given in the question that all the edges have different edge weight

---

They haven't said anything about Distinct or same edge weight possible, so assume both case & check options for both.

---

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

---

😎

---

if you too thought that, option c was correct by cycle property

cycle property is true for MST iff, when there is a unique heaviest edge in the cycle, or more broadly; when edge weights are distinct

---

Important Points

1. The Cut Property: For any cut of the graph, if an edge is the minimum weight edge crossing that cut, it can be part of an MST. More importantly, if an edge $e$ is in an MST, there must exist a cut where $e$ is a minimum weight edge among all edges crossing that cut.

2. The Cycle Property: For any cycle in a graph, the strictly maximum weight edge in that cycle cannot be part of any MST.

Option A: There exists a cutset in $G$ having all edges of maximum weight.

Ans : TRUE

The Proof:

1. We are told that edge $e$ is in an MST and that $e$ has the maximum weight ($W_{max}$) in the entire graph $G$.

2. According to the Cut Property, since $e$ is in an MST, there must exist some cut $(S, V-S)$ such that $e$ is a minimum weight edge among all edges crossing that cut.

3. Let's look at any other edge $e'$ that crosses this same cut.

• Because $e$ is a minimum in this cut: $weight(e') \geq weight(e)$.
• Because $e$ is the maximum in the whole graph: $weight(e') \leq weight(e)$.

1. The only way both conditions ($weight(e') \geq W_{max}$ and $weight(e') \leq W_{max}$) can be true is if $weight(e') = W_{max}$.

2. Therefore, every single edge crossing that specific cut must have the same weight as $e$. Since $e$ is a maximum weight edge, the entire cutset consists of maximum weight edges.

Option B: There exists a cycle in $G$ having all edges of maximum weight.

Ans : FALSE

Reasoning:

A graph doesn't need to have cycles at all.

• Counterexample: Consider a simple path graph $v_1 \xrightarrow{1} v_2 \xrightarrow{2} v_3$. Here, $n=3$. The maximum weight is 2 (edge $e$). The MST is the path itself, which contains $e$. However, there are no cycles in this graph, so this statement cannot be always true.

Option C: Edge $e$ cannot be contained in a cycle.

Ans : FALSE

Reasoning:

An edge can definitely be part of a cycle and still be in the MST, provided it is not the strictly heaviest edge in that cycle.

• Counterexample: Consider a triangle (cycle of 3 nodes) where all edges have a weight of 10. Here, $W_{max} = 10$. Any MST will pick two of these edges. The edge $e$ (weight 10) is in an MST and it is part of a cycle.

Option D: All edges in $G$ have the same weight.

Ans: FALSE

Reasoning:

==> Counterexample: Look back at the path $v_1 \xrightarrow{1} v_2 \xrightarrow{2} v_3$. Edge $e$ (weight 2) is the max weight and is in the MST. But the edges have weights 1 and 2. They are not all the same.

---

Excellent explanation!

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

I have the same doubt thanks for clearing @Shaik Masthan sir

---

https://youtu.be/UbGDzdW7UjY?list=PLIPZ2_p3RNHjUCHdJp-_soSSmhgmO4i0T&t=1983

For detailed explanation

---

Option A) There exists a cutset in G having all edges of maximum weight.

It means there is a cutset in G such that in that cutset, every edge has weight = (maximum edge weight in the whole graph).

To put this in aother way: "There exists some way to split the vertices of the graph into two non-empty groups such that every edge connecting those two groups has the maximum weight found in the entire graph."

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.

Answer 5

question is asking for the case which remains always true....let we take each option:

(b)This may be the case but not for always. If edge 'e _max' incident on a pendant vertex then MST must consider 'e_max' bcoz thats the only way to reach at that vertex....so this rejects option (b)

(c)  'e_max' can be there in cycle but not always. when it is in cycle and in MST also then all cycle edges will be of weight  'e_max'.

(d)obviously false

Ans option(a): assuming explanation of (b) above, we see that if we MST considering  'e_max' then it implies that, that's only the weight of edge to reach at that vertex(v). So there may be such multiple edges but will be having same weight only i.e.  'e_max' . Removal of all these edges will disconnect 'v' from G which is the cutset for 'v'.

Answer 6

ALL the edges in a MST are "light edges" crossing some cut.

For e to be included in the MST, it has to be the light edge crossing the cut.

For e to be a light edge, all edges should weigh equal to e here, because e is the max weight here.

So, Option A is True.

---

This question can, however, easily be solved via counter examples.

---

PS: Note that all the edges in MST are light edges (minimum-weight edges) crossing the cut. But that doesn't mean if any edge is a light edge crossing some cut, it must be in MST.

Eg: Light edges crossing the cut = {A,B,C,D,E,F,G}

Edges included in MST = {A,B,C,D}

 

PPS: Read CLRS 3rd edition pages 625 to 630. You could solve probably every GATE MST question through those five pages.

Comments

@JashanArora, Explain with example diagram