GATE Overflow Test Series | Algorithms | Test 2 | Question: 2

Question

Which of the following statements regarding Minimum Spanning Tree (MST) is/are TRUE? (Mark all the appropriate choices)

• A. If $e$ is the maximum weight edge in a connected graph $G,$ then there is always a MST of $G$ that does not include $e$
• B. If all the edge weights of a graph $G$ are positive, then any subset of edges that connects all the vertices and has minimum total weight forms a tree
• C. If we decrease the weight of an edge in MST, it still remains a MST
• D. If all the edge weights of a graph are increased by a value $k,$ the MST remains the same

Comments

These all are CLRS Excercise 23.1 problem..

---

a. Doesn't hold true for cut vertex. False.
b. That's the definition of MST.
c. Decreasing the weight is optimum for MST, so nothing will change.
d. MST is just to scan vertices (at each node, pick a vertex with the least weight among present), so it's true. The shortest distance will change, not MST.

Check this for reference: https://gateoverflow.in/39673/gate-cse-2016-set-1-question-14

Answer 1

A is false as $e$ will be in the MST if it is a cut edge.

Comments

option d is false.

consider the graph with 3 vertices A,B, C

and

edges (A,B)-4

(A,C)-1

(C,B)-2

then MST will contain the edges (A,C) and (C,B)

if every edge weight is increased by 5 the MST will contain Edges (A,B) and (A,C).

---

no @rahul

AB=9

CB=7

AC=6

MST still contain 7&6 weight edges

---

please elaborate, as i know that in a cut edge if an edge weight is strictly lower than all other edge weights in a cut set then smaller edge must be a part of MST.

---

@theredeepakb

If only maximum edge e2 crosses a cut then it has to be included in MST as there is no other choice to keep mst connected

Answer 2

Option A: what if e is not a cut edge.

Option B: subset of edges connecting all vertices forms a tree: MST

Option C: decreasing edge strengthens the fact that edge will remain in MST. increase in edge weight will not ensure its presence.

Option D: increase or decrease all edge edges will not change MST.

Comments

@Udhay_Brahmi subset of edges connecting all vertices + No cycle forms a tree