in Algorithms edited by
14,409 views
61 votes
61 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?

  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.
in Algorithms edited by
14.4k views

4 Comments

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

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
1
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
0

9 Answers

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

3 Comments

(c) option says whether e is part of a cycle in the original graph- not in the minimum spanning tree.
0
0
not really. Consider the case when all edges in cycle are of same weight.
0
0
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
1
Answer:

Related questions