14,409 views

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?

1. There exists a cutset in $G$ having all edges of maximum weight.
2. There exists a cycle in $G$ having all edges of maximum weight.
3. Edge $e$ cannot be contained in a cycle.
4. All edges in $G$ have the same weight.

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

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.

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

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