alleryStart learning →If you remove an edge (u, v) from an MST T, the two resulting sub-trees
Aare themselves MSTs of their induced subgraphs
Bare no longer trees of any kind
Cmust share at least one vertex to remain connected
Dalways have equal total weight
Answer & Solution
Correct answer: A. are themselves MSTs of their induced subgraphs
Removing one edge from a tree gives two sub-trees on disjoint vertex sets.
The MST's optimal substructure says each sub-tree is itself an MST of its induced subgraph (proven by a cut-and-paste exchange argument).
Without this property, greedy MST construction would not work.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.