Algorithms
Graph Algorithms
GATE 2007
Hard
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?
- AThere is a minimum spanning tree containing e
- BIf 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
- CEvery minimum spanning tree has an edge of weight w
- e is present in every minimum spanning tree
Explanation
(A),(B),(C) are all standard true MST properties of the global-minimum-weight edge (there's always an MST containing it, any cycle formed by adding it to another MST has only equal-weight edges, and every MST contains at least one minimum-weight edge). (D) is FALSE in general: if multiple edges share the minimum weight w, an MST could include a different one instead of e specifically.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.