Multiple choice

Consider a minimum spanning tree T in a graph G. If the weight of an edge e of T is decreased, then the resulting tree T is still a minimum spanning tree.

  1. Yes

  2. No

  3. Sometimes yes sometimes no

  4. Cannot comment
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

If the weight of an edge already in a Minimum Spanning Tree (MST) is decreased, it remains the smallest possible edge for that cut, thus the tree remains an MST.

Keep practicing — related questions