GATE CSE 2016 Set 1 | Question: 40

Question

$G=(V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees $(MSTs)$ of $G$ is/are TRUE?

1. If $e$ is the lightest edge of some cycle in $G$, then every MST of $G$ includes $e$.
2. If $e$ is the heaviest edge of some cycle in $G$, then every MST of $G$ excludes $e$.

• A. I only.
• B. II only.
• C. Both I and II.
• D. Neither I nor II.

Comments

Very Good Question.

---

Similar question

https://gateoverflow.in/3813/gate2005-it-52

(II) follows reverse krushal's algo http://www.geeksforgeeks.org/reverse-delete-algorithm-minimum-spanning-tree/

---

$1$ is false here because it can be possible that an edge is lightest for some cycle bt same edge can  be maximum for other cycle too As in the given best answer 3 is the lowest weight edge for cycle $3-4-5$ bt it is heaviest for $1-2-3$  .

Answer 1

Statement 1:- False by [Cut Property of MST]

See counter example :- Here in below Graph $G$ in $($cycle $3,4,5 ) \ 3$ is the lightest edge and still it is not included in MST.

Statement 2:- True by[ Cycle property of MST] : (in above Graph $G \  \ 1-2-3$ is a cycle and $3$ is the heaviest edge) If heaviest edge is in cycle then we will always exclude that because cycle is there means, we can have other choice of low cost edges. (If edge weights are not distinct even the heaviest edge can be part of the MST and here in question distinct edge weight is clearly mentioned)

So, option B is answer.

Must visit Link: http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/mst.pdf

Comments

cutset is more emergency than a cycle

---

For the graph below:-

 

Wouldn't the MST look like this:-

And so option 1 If is the lightest edge of some cycle in G, then every MST of includes will also be false since both the light weighted edges are present in the MST?

Please explain.

---

@Ayush,

in your example, $dc$ is the lightest edge in the cutset but is it the lightest in any cycle? Is your example only related to cutset?

Answer 2

1. For an edge to be INCLUDED in the MST, it must satisfy the CUT PROPERTY which states that

• Assume that all edge costs are distinct. Let $S$ be any subset of nodes that is neither empty nor equal to all of $V,$ and let edge $e = (v, w)$ be the minimum cost edge with one end in $S$ and the other in $V − S.$ Then every minimum spanning tree contains the edge $e.$

It is given that $e$ is the lightest edge of some cycle in $G,$ but it may not be the lightest edge connecting $S$ and $V - S.$ See the below image for clarification.

Here, $\bf{e}$ is the lightest edge of cycle C. There are three edges $e,e^{'},e^{"}$ connecting $S$ and $V - S.$

$\bf{e}$ is obviously minimal weighted than $e'$ since $e'$ is part of the cycle $C,$ but $e$ MAY NOT be minimal weighted than $e^".$

So, every MST of $G$ MAY NOT include $e.$

2. For an edge to be EXCLUDED from the MST, it must satisfy the CYCLE PROPERTY which states that

• Assume that all edge costs are distinct. Let $C$ be any cycle in $G,$ and let edge $e = (v, w)$ be the most expensive edge belonging to $C.$ Then $e$ does not belong to the minimum spanning tree of $G.$

It is given that $e$ is the heaviest edge of some cycle C.

But, there will always be an edge in the cycle, say $e',$ which is lighter than $e$ connecting $S$ and $V - S$.

So, every MST of $G$ MUST exclude $e.$

ANSWER is B.

Courtesy: Algorithm Design by Jon Kleinberg and Eva Tardos

Comments

Awesome explanation. What do you think would be the answer if $e$ is the lightest edge in every cycle it is part of? Would this change the answer?

---

@ytheuyr.. If e is the lightest edge in every cycle it is part of, then as per the given answer, it is lighter than both $e’$ and $e”$, satisfying the cut property and hence will be part of the MST.

---

let edge e=(v,w)e=(v,w) be the minimum cost edge with one end in S    according to this e is the minimum weight edge right how does e’’ become minimum than e

Answer 3

I think the answer is an option $B$

Statement $2$ is correct absolutely. if e is the heaviest edge in a cycle every MSTexcludes it.

Regarding statement $1$, It is not fully right I think. When we think of a complete graph with $4$ vertices and edge weights $1,2,5,6$ in non-diagonal and diagonal edges $3$ and $4$. $4,5,6$ will create a cycle and we can exclude the lightest edge e (4) from it, in an MST

So I think the answer could be $B$

Comments

Cycle property: Let C be any cycle, and let f be the max cost edge
belonging to C. Then the MST does not contain f.

http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/mst.pdf

Answer 4

First thing to immediately take notice here, is that edges have distinct weights. This characteristic changes results.

Whenever it isn't mentioned that edge weights are distinct, you always should keep all edges at same weight to fetch an extreme case, which will generate counter-examples in a lot of graph problems.

Now, coming to the question:

---

If e is the lightest edge of some cycle in G, then every MST of G includes e.

The only reason a lighter edge is not preferred in some MST is when it somehow forms a loop. So, try to make a loop out of it.

If this lightest edge of some cycle contributes to a loop somewhere else, then we will exclude it.

See this:

50 is the lightest edge of some cycle. But we will exclude it because it'll form a loop in our MST.

Hence, Statement I is False

---

If e is the heaviest edge of some cycle in G, then every MST of G excludes e.

The edge weights are distinct. It means there's only one heaviest edge strictly.

The only reason a heavier edge is included in an MST is when it is a bridge (cut edge). Including it is our necessity because without it, the MST can't be connected.

Also, it is a property that a bridge can't be a part of a cycle.

This means given heaviest edge is NOT a bridge. So including it is not our necessity. And when it's not necessary, we certainly won't include it in our MST — we'll always prefer a lighter edge.

Statement II is True.

Option B

 

Please note that this statement is true only because the edge weights are distinct.

If not, then there exists a graph where many, if not all edge weights are the heaviest — in such a case we will be including multiple max-weight edges, lol. (Take a graph with one edge of weight 1, and all other edges of weight 500)

https://gateoverflow.in/3813/gate2005-it-52