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

question is asking for the case which remains always true....let we take each option:

(b)This may be the case but not for always. If edge 'e _max' incident on a pendant vertex then MST must consider 'e_max' bcoz thats the only way to reach at that vertex....so this rejects option (b)

(c)  'e_max' can be there in cycle but not always. when it is in cycle and in MST also then all cycle edges will be of weight  'e_max'.

(d)obviously false

Ans option(a): assuming explanation of (b) above, we see that if we MST considering  'e_max' then it implies that, that's only the weight of edge to reach at that vertex(v). So there may be such multiple edges but will be having same weight only i.e.  'e_max' . Removal of all these edges will disconnect 'v' from G which is the cutset for 'v'.

Answer 2

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.

Comments

@JashanArora, Explain with example diagram

Answer 3

 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:

1.        The removal of all edges in S disconnects G.
2.        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”

Comments

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.

can you please explain what do you mean by these lines? 

---

@Pranavpurkar 

There exists a cutset in G having all edges of maximum weight.

Acc to option A, the cutset will contain all the sides of the triangle(which I mentioned above).

But point 2 is telling:

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

So, here taking two edges of a triangle already we can disconnect the graph G into two partitions. We don’t need the third side. Therefore it is violating the definition.

---

@samarpita

ohh okay!

But cut set is the minimum set of edges required to be removed to disconnect a graph , and in your example of a traingle the cut set is 2.

but in the question there exists is used so it need not be traingle right , and need not be the mst with 3 vertices .

and moreover if my above counter is weak than,

option A is 

There exists a cutset in G having all edges of maximum weight.

it is saying that  “ all edges of maximum weight”

so isn’t it true in your example  coz the cutset in traingle contains two edges and both having maximum weight. (i.e all edges havaing maximum wt in the cut set).

this option is not saying  “all maximum wt edges”. 

Answer 4

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.

Comments

but the heaviest edge will be part of MST if it is not part of a cycle as well.

---

@Arjun sir

The first statement: 

1. There exists a cutset in G having all edges of maximum weight.

Does this mean cutset has only maximum weight edges or cut set has all the edges with maximum wieght?

Because if it is later then counter examples are possible for that.Please clear this point.