2.2k views

Let $w$ be the minimum weight among all edge weights in an undirected connected graph. Let $e$ be a specific edge of weight $w$. Which of the following is FALSE?

1. There is a minimum spanning tree containing $e$

2. If $e$ is not in a minimum spanning tree $T$, then in the cycle formed by adding $e$ to $T$, all edges have the same weight.

3. Every minimum spanning tree has an edge of weight $w$

4. $e$ is present in every minimum spanning tree

D is the false statement.

A minimum spanning tree must have the edge with the smallest weight (In Kruskal's algorithm we start from the smallest weight edge). So, C is TRUE.

If e is not part of a minimum spanning tree, then all edges which are part of a cycle with e, must have weight $\leq e$, as otherwise we can interchange that edge with $e$ and get another minimum spanning tree of lower weight. So, B and A are also TRUE.

D is false because, suppose a cycle is there with all edges having the same minimum weight $w$. Now, any one of them can be avoided in any minimum spanning tree.

edited by
+4
what the difference between third and fourth statement?
+5
@ankyAS
a minor difference.
'e' is the specific edge of weight "W".
but there may be more edges of weight 'W'.
so the 4th statement is talking only about specific edge 'e'. while 3rd is about all the edges having minimum weight 'w'.
+1
consider a triangle with all edge weights 1(all weights are minimum) then at least one edge will not be present in the minimum spanning tree even though it's weight is minimum.
+1
whats option b want to express i can't understand
0

@arjun sir,you mentioned

If e is not part of a minimum spanning tree, then all edges which are part of a cycle with e, must have weight ≤ e,

The highlighted <=e should be =e,because e is the minimum edge and no edge weight can be less than that.

0
Yes but they are talking about specific edge weight e of w
0

any example for b part

+1
If e is not part of a minimum spanning tree, then all edges which are part of a cycle with e, must have weight ≤ e, as otherwise we can interchange that edge with e and get another minimum spanning tree of lower weight. So, B is true

@set2018
0

A minimum spanning tree must have the edge with the smallest weight (In Kruskal's algorithm we start from the smallest weight edge). So, C is TRUE.
this is a nice point given by arjun sir

0
Why D) is wrong ? Please explain with a example.
0
0
Thank you Sir
0
What does it means when we say ..minimum weight among all edge weights..

What is the other word for a unique minimum in case if such thing comes in GATE?
0
I also get confused when it said minimum weight among all I thought it to be a unique weight.🙄

w is a weight.

e is an edge with weight w.

There can be more edges with weight w other than e.

1