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

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.

Answer 1

3 will be always true. There is no cycle in a minimum spanning tree ever.

Comments

(c) option says whether e is part of a cycle in the original graph- not in the minimum spanning tree.

---

not really. Consider the case when all edges in cycle are of same weight.

---

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.