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.

### 5 Comments

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.

## 9 Answers

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.

### 1 comment

I have seen all the answers ...and truly I am not satisfied with the best answer and I also think that option A is not always correct.

So, my explanation will be for option A, as options B, C, and D are correctly demonstrated in the above answers.

**WHAT IS THE CUT SET?**

** – The Cut set of a connected graph in G is a set S of edges with the following properties:**

**The removal of all edges in S disconnects G.****The removal of some (but not all) edges in S does not disconnect G.**

If we consider a triangle or cycle graph with 3 vertices with all edge weights are same. Then clearly cut set will contain two edges. If we go along with option A and take all the edges-, then it is violating the “cut set” definition (point number 2) because by taking two edges already we can disconnect the graph G into two partitions.

So, I think the correct option would be for A “There exists a cutset in G having edges of maximum weight”

ans is B)

**For each possible simple cycle in a connected weighted graph G with
distinct edge weights, the heaviest edge in the cycle does not belong to a MST of G. Bcz we can select a minimum weight edge from the cycle to be in MST.**

Hence,If the heaviest edge belongs to MST then there exist a cycle having all edges with maximum weight.