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

Dark Mode

14,409 views

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?

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

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.

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

–4 votes

0