The Minimum Spanning Tree of a connected weighted graph with

The Minimum Spanning Tree of a connected weighted graph with 40 edges always a. contains the least weight edge Always Sometimes Never b. contains 2 least weight edges Always Sometimes Never c. contains least weight edges Always Sometimes Never d. has at least 9 edges Always Sometimes Never e. has at least 10 edges Always Sometimes Never

Solution

a. Sometimes - Some of the weighted edge choosen can be more than the least weighted edge. This is because path using least can prove to costly sometimes

b) Always - If the least weight edge is unique then it will be part of MST.

c) Sometimes - Kruskal\'s algorithm always tries to find minimum path between two vertices. It is a greedy algorithm and always result in getting least weight edges.

d) Always - MST of 40 vertices will contains 39 edges

e) Always - MST of 40 vertices will contains 39 edges