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?
There is a minimum spanning tree containing $e$
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.
Every minimum spanning tree has an edge of weight $w$
$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.
@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.
Sandeep Suri
any example for b part
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
Gatecse