1.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.

edited by
what the difference between third and fourth statement?
@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'.
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.
whats option b want to express i can't understand

@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.

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

any example for b part

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