edited by
26,007 views
117 votes
117 votes

$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$.
  1. I only.
  2. II only.
  3. Both I and II.
  4. Neither I nor II.
edited by

6 Answers

Best answer
137 votes
137 votes

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

edited by
61 votes
61 votes

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

edited by
38 votes
38 votes
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$
edited by
4 votes
4 votes

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

Answer:

Related questions

85 votes
85 votes
18 answers
1
Sandeep Singh asked Feb 12, 2016
35,080 views
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight s...
61 votes
61 votes
5 answers
3
Sandeep Singh asked Feb 12, 2016
28,244 views
Consider the following directed graph:The number of different topological orderings of the vertices of the graph is _____________.
44 votes
44 votes
5 answers
4
go_editor asked Feb 15, 2015
10,735 views
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is i...