Dark Mode

14,027 views

58 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

35 votes

Best answer

Option $A$ is correct.

Questions says the MST of graph $G$ contain an edge $e$ which is a maximum weight edge in $G$. Need to choose the answer which is always true to follow the above constraint.

**Case 1:**

**Option B **says that if edge $e$ is in MST then for sure there is a cycle having all edges of maximum weight. But it** is not true always because when there is only n-1 edges( but no cycle) in graph then also maximum edge has to be taken for MST**.

**Case 2: **

**Option C** says otherwise. That if e is in MST then it cannot be in any cycle that is wrong as if there is a cycle with all maximum edges then also e will be in MST

**Option D** says all edges should be of same weight same explanation if there are $n-1$ distinct edges( but no cycle) in $G$ then have to take all edges including maximum weight edge.

And at last option A **says**** if e is in MST then for sure there is a cut-set ( A subset of Edge set of G whose removal disconnects the graph) in **$G$** having all edges of maximum weight. And it is true.**

**Because then only we maximum weight edges has to be taken in MST.**

For eg. If there are $n-1$ edges (but no cycle) then if edge e is not taken in the MST then MST will not be connected.

0

31 votes

**Option A is correct.**

Here, in this example we can easily see that B, C, D are false. So, B,C,D are not always true.

that's why A is always true.. **A (Ans)**

edited
Jan 19, 2017
by Nit9

for eliminating option b, take a diagonal edge with weight 2 in the above graph. (option says all edges)

cutset is the minimum edge set whose removal disconnects the graph.

option a will always be correct as more than 1 e have to be there for it to be in mst, leaving us no choice to select it, so it has to be in cutset because its only beacuse of its selection we got a mst which is connected.. case 2: also if we take e if its removal disconnects the graph on single occurance, that also relates with cutset defination

cutset is the minimum edge set whose removal disconnects the graph.

option a will always be correct as more than 1 e have to be there for it to be in mst, leaving us no choice to select it, so it has to be in cutset because its only beacuse of its selection we got a mst which is connected.. case 2: also if we take e if its removal disconnects the graph on single occurance, that also relates with cutset defination

1

I understood why option B C D cannot be the answer but can you please clarify the reason for option A?

An edge cut set is a set of edges of a graph which, if removed (or "cut"), disconnects the graph (i.e., forms a disconnected graph). Reference: http://mathworld.wolfram.com/EdgeCutSet.html

By removing one of the edges with weight=2 we cannot disconnect the graph. By removing 2 such edges we can disconnect it. Since it has not been asked to get the minimum cut-set so we can remove 3 such edges and can get 3 connected components(one with an edge and other two pendant vertices). So now the cut-set has all the edges with max weight.

2

14 votes

Option a is always true

Option b is not true when e is not part of a cycle.

Option c is not true when e is part of a cycle and all edge weights are same in that cycle

Option d is need not be true when e is not part of a cycle

Option a is always true as only the min weight edge in a cut set will be part of a minimum spanning tree.

Option b is not true when e is not part of a cycle.

Option c is not true when e is part of a cycle and all edge weights are same in that cycle

Option d is need not be true when e is not part of a cycle

Option a is always true as only the min weight edge in a cut set will be part of a minimum spanning tree.