Minimum spanning Tree (MST) is an important topic for GATE. Therefore, we will discuss how to solve different types of questions based on MST. Before understanding this article, you should understand basics of MST and their algorithms (Kruskal's algorithm and Prim's algorithm).
The number of edges in MST with n nodes is (n-1).
The weight of MST of a graph is always unique. However there may be different ways to get this weight (if there edges with same weights).
The weight of MST is sum of weights of edges in MST.
Maximum path length between two vertices is (n-1) for MST with n vertices.
There exists only one path from one vertex to another in MST.
Removal of any edge from MST disconnects the graph.
For a graph having edges with distinct weights, MST is unique.
(A) Every minimum spanning tree of G must contain emin.
Solution: As edge weights are unique, there will be only one edge emin and that will be added to MST, therefore option (A) is always true.
As spanning tree has minimum number of edges, removal of any edge will disconnect the graph. Therefore, option (B) is also true.
As all edge weights are distinct, G will have a unique minimum spanning tree. So, option (D) is correct.
Option C is false as emax can be part of MST if other edges with lesser weights are creating cycle and number of edges before adding emax is less than (n-1).
Arrange the edges in non-decreasing order of weights.
Add edges one by one if they don't create cycle until we get n-1 number of edges where n are number of nodes in the graph.
Adding first three edges (v4,v5), (v3,v5), (v2,v4), no cycle is created. Also, we can connect v1 to v2 using edge (v1,v2). The total weight is sum of weight of these 4 edges which is 10.
If all edges weight are distinct, minimum spanning tree is unique.
If two edges have same weight, then we have to consider both possibilities and find possible minimum spanning trees.
Solution: There are 5 edges with weight 1 and adding them all in MST does not create cycle.
As the graph has 9 vertices, therefore we require total 8 edges out of which 5 has been added. Out of remaining 3, one edge is fixed represented by f.
For remaining 2 edges, one is to be chosen from c or d or e and another one is to be chosen from a or b. Remaining black ones will always create cycle so they are not considered. So, possible MST are 3*2 = 6.
To solve this type of questions, try to find out the sequence of edges which can be produced by Kruskal. The sequence which does not match will be the answer.
(b,e), (e,f), (a,c), (b,c), (f,g), (a,b), (e,g), (c,d), (b,d), (e,d), (d,f).
First it will add (b,e) in MST. Then, it will add (e,f) as well as (a,c) (either (e,f) followed by (a,c) or vice versa) because of both having same weight and adding both of them will not create cycle.
However, in option (D), (b,c) has been added to MST before adding (a,c). So it can't be the sequence produced by Kruskal's algorithm.