Project ForgeSign up free
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.

Start revising free