MinimumSpanningTree
Question 1 
Consider the following undirected graph G:
Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is _________.
4  
5  
6  
7 
If x = 5 then the total number of MWSTs are 4.
If r = 1
If r = 2
If r = 3
If r = 4
If r = 5
Question 2 
(I) Minimum Spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(I) only  
(II) only  
both (I) and (II)  
neither (I) nor (II) 
Let us take an example
Step 1:
Using kruskal’s algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step 2:
Step 3:
17+18+20+21+22+23+26 = 147
Step 4:
Here, all the elements are distinct. So the possible MCST is 1.
StatementII: May or may not happen, please take an example graph and try to solve it. This is not correct always.
So, we have to pick most appropriate answer.
Question 3 
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is __________.
7  
8  
9  
10 
Now consider vertex A to make Minimum spanning tree with Maximum weights.
As weights are 1, 2, 3, 4, 5, 6. AB, AD, AC takes maximum weights 4, 5, 6 respectively.
Next consider vertex B, BA = 4, and minimum spanning tree with maximum weight next is BD & BC takes 2, 3 respectively.
And the last edge CD takes 1.
So, 1+2+4 in our graph will be the Minimum spanning tree with maximum weights.
Question 4 
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
I only  
II only  
both I and II  
neither I nor II 
The MSTs of G may or may not include the lightest edge.
Take rectangular graph labelled with P,Q,R,S.
Connect with PQ = 5, QR = 6, RS = 8, SP = 9, PR = 7.
When we are forming a cycle RSPR. PR is the lightest edge of the cycle.
The MST abcd with cost 11
PQ + QR + RS does not include it.
Statement2: True
Suppose there is a minimum spanning tree which contains e. If we add one more edge to the spanning tree we will create a cycle.
Suppose we add edge e to the spanning tree which generated cycle C.
We can reduce the cost of the minimum spanning tree if we choose an edge other than e from C for removal which implies that e must not be in minimum spanning tree and we get a contradiction.
Question 5 
The graph shown below 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ______________.
69  
70  
71  
72 
⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69
> First we compare AC and AB we find 9 at AC it means AB must greater than AC and for minimum possible greater value than 9 will be 10
> Second we compare BE and CD in which we select BE is 15 which CD possible weight 16.
> Third, we compare ED and FD in which we select FD 6 means ED must be greater than 6 so possible value greater than 6 is 7 .
Note: Add First+Second+Third=(AB=10)+(CD=16)+(ED=7)
Question 6 
Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes __________.
995  
996  
997  
998 
Question 7 
The number of distinct minimum spanning trees for the weighted graph below is _______.
6  
7  
8  
9 
Minimum Spanning Tree:
From the diagram, CFDA gives the minimum weight so will not disturb them, but in order to reach BE=1 we have 3 different ways ABE/ DBE/ DEB and we have HI=1, the shortest weight, we can reach HI=1 through GHI/ GIH.
So 3*2=6 ways of forming Minimum Spanning Tree with sum as 11.
Question 8 
Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?
T' = T with total weight t' = t^{2}  
T' = T with total weight t'  
T' ≠ T but total weight t' = t^{2}  
None of the above 
Then MST for G is,
Now let's square the weights,
Then MST for G' is,
So, from above we can see that T is not necessarily equal to T' and moreover (t^{1}) < (t^{2}).
So option (D) is correct answer.
Question 9 
An undirected graph G(V, E) contains n (n > 2) nodes named v_{1}, v_{2}, ….v_{n}. Two nodes v_{i} , v_{j} are connected if and only if 0 < i – j ≤ 2. Each edge (v_{i}, v_{j}) is assigned a weight i + j. A sample graph with n = 4 is shown below.
What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
1/12(11n^{2}5n)  
n^{2} – n + 1  
6n – 11  
2n + 1 
Cost of MST,
= 3+4+6+8 = 21
Only option (B) satisfies it.
Question 10 
An undirected graph G(V, E) contains n (n > 2) nodes named v_{1}, v_{2}, ….v_{n}. Two nodes v_{i} , v_{j} are connected if and only if 0 < i – j ≤ 2. Each edge (v_{i}, v_{j}) is assigned a weight i + j. A sample graph with n = 4 is shown below.
The length of the path from v_{5} to v_{6} in the MST of previous question with n =10 is
11  
25  
31  
41 
Now MST of above graph is,
∴ The length of path from v_{5} to v_{6} in the MST is,
8+4+3+6+10 = 31
Question 11 
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge {i, j}.
What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?
7  
8  
9  
10 
So, the edges of the spanning tree given that vertex 0 is a leaf node in the tree,
So, the minimum possible weight of spanning tree will be
= 1 + 4 + 2 + 3
= 10
Question 12 
Consider the following graph
Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?
(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)
 
(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)  
(b,e)(a,c)(e,f)(b,c)(f,g)(c,d)  
(b,e)(e,f)(b,c)(a,c)(f,g)(c,d) 
1. It follows like forest structure(Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
As per the options below Option A,B,C, are following correct order but Option D is violating Kruskal’s procedure. The edge between ac of weight 4 comes after bc of weight 3.
Question 13 
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE?
There is a minimum spanning tree containing e.  
If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
 
Every minimum spanning tree has an edge of weight w.  
e is present in every minimum spanning tree. 
Question 14 
n1  
2n2  
n^{2} 
2) Weight of the minimum spanning tree = 22  1 + 23  2 + 24  3 + 25  4 .... + 2 n  (n1)  = 2n  2
Question 15 
Consider the following graph:
Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?
(a—b),(d—f),(b—f),(d—c),(d—e)  
(a—b),(d—f),(d—c),(b—f),(d—e)  
(d—f),(a—b),(d—c),(b—f),(d—e)  
(d—f),(a—b),(b—f),(d—e),(d—c) 
1. It follows like forest structure (Means we are disconnecting all the edges connected to vertices).
2. Sort edge weights in Ascending order.
3. Always select the minimum edge weight first according to Spanning Tree rules.
Note: The edge de cannot be considered before dc.
Question 16 
What is the weight of a minimum spanning tree of the following graph ?
29  
31  
38  
41 
1+2+3+2+8+4+4+2+5 =31
Question 17 
Consider a weighted undirected graph with vertex set V = {n1,n2,n3,n4,n5,n6} and edge set
E = {(n1,n2,2),(n1,n3,8),(n1,n6,3),(n2,n4,4),(n2,n5,12),(n3,n4,7),(n4,n5,9), (n4,n6,4)}. The third value in each tuple represents the weight of the edge specified in the tuple.
(a) List the edges of a minimum spanning tree of the graph.
(b) How many distinct minimum spanning trees does this graph have?
(c) Is the minimum among the edge weights of a minimum spanning tree unique overall possible minimum spanning trees of a graph?
(d) Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?
Theory Explanation is given below. 
(c) Yes, it always. Because 'the edge weight 2 is unique'.
(d) Yes, it always. Because 'the edge weight 9 is unique'.
Question 18 
Let G be an undirected connected graph with distinct edge weight. Let e_{max} be the edge with maximum weight and e_{min} the edge with minimum weight. Which of the following statements is false?
Every minimum spanning tree of G must contain e_{min}  
If e_{max} is in a minimum spanning tree, then its removal must disconnect G  
No minimum spanning tree contains e_{max}  
G has a unique minimum spanning tree 
Minimum Spanning Tree:
Question 19 
A complete, undirected, weighted graph G is given on the vertex {0, 1,...., n−1} for any fixed ‘n’. Draw the minimum spanning tree of G if
(a) the weight of the edge (u,v) is ∣u − v∣
(b) the weight of the edge (u,v) is u + v
Theory Explanation. 
Question 20 
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to the edge).
Theory Explanation. 
Question 21 
Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
θ(E+V)  
θ(E logV)  
θ(EV)  
θ(V) 
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge.
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V).
Method2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method1 is the most appropriate answer for giving a question.
Question 22 
Consider a graph G = (V, E), where V = {v_{1}, v_{2}, …, v_{100}}, E = {(v_{i}, v_{j})  1 ≤ i < j ≤ 100}, and weight of the edge (v_{i}, v_{j}) is i  j. The weight of the minimum spanning tree of G is ______.
99 
• N =100
• Edge weight is ij for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So, 99 edges of weight is 99.
Question 23 
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree?
(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)  
(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)  
(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)  
(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)

(A) (d, f) is chosen but neither 'd' nor 'f' vertices are part of previous MST (MST made till previous step).
(B) (g, h) is chosen but neither g or h vertices are part of MST made till previous step.
(C) Correct.
(D) (f, c) is chosen, but at that point (f, d) had less weight. So, (f , d) should have been chosen.
Question 24 
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?
1  
2  
3  
n 
→ If we create a different spanning tree by removing one edge at a time.
→ For cycle required 3 minimum edges. So there is at least 3 spanning trees in such a graph.
Question 25 
The number of minimumweight spanning trees of the graph is _______
3 
To find the number of spanning trees using 2 methods:
 If graph is complete, use n^n2 formula
 If graph is not complete, then use kirchhoff theorem.
Steps in Kirchoff’s Approach:
(i) Make an Adjacency matrix.
(ii) Replace all nondiagonal is by – 1.
(iii) Replace all diagonal zero’s by the degree of the corresponding vertex.
(iv) Cofactors of any element will give the number of spanning trees.
Using the Kirchhoff theorem will take lot of time because the number of vertices are 9.
So, we use brute force technique to solve the problem with the help of Kruskal's algorithm.
Question 26 
S_{1}: There exists a minimum weighted edge in G which is present in every minimum spanning tree of G.
S_{2}:If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which of the following options is correct?
S_{1}is false and S_{2}is true.
 
S_{1}is true and S_{2}is false.  
Both S_{1} and S_{2}are false.  
Both S_{1} and S_{2}are true. 
Statement1: FALSE: The given statement is not valid for all the cases because they are not mentioned, edge weights are in distinct or duplicate. So, we can take any random edge weights for the given statement.
Example:
Statement2: TRUE: Using the kruskal’s (or) prim's algorithm we get a unique MST when there is a unique edge weight.
Example:
Based on the above graph, we get the MST is
Question 27 
The sum of the qualityscores of all the vertices in the graph shown above is _________.
929 
Question 28 
The edge with the second smallest weight is always part of any minimum spanning tree of G .  
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G .  
G can have multiple minimum spanning trees. 
OptionA: TRUE: As per the above graph, the second minimum edge weight is also part of the MST.
The second smallest weight is always in MST because it will not form a cycle.
OptionB: FALSE: As per the above graph, the third minimum edge weight is not part of the MST.
The third or fourth edge weight may be part of the cycle. So, it may or may not be in MST.
OptionC: TRUE: As per the example graph, it is always correct.
OptionD: FALSE: We will get a unique minimum spanning tree if edge weights are distinct.
Question 29 
24 
Graph have 3 elements > We get 2 MSTs
Graph have 4 elements > We get 6 MSTs (3*2*1)
Graph have 5 elements > We get 24 MSTs(4*3*2*1)
Question 30 
Consider the graph shown below :
Use Kruskal’s algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is
13  
16  
17  
14 
The weight of this minimum spanning tree is 16.
Question 31 
Every minimum spanning tree of G must contain E_{ min}.  
If E _{max} is in minimum spanning tree, then its removal must disconnect G.  
No minimum spanning tree contains E_{ max}.  
G has a unique minimum spanning tree. 
Minimum Spanning Tree:
Question 32 
According to kruskal’s algorithm, first we have sort an elements.
Elements are: 10,12,14,16,18,22,24,25,28
Question 33 
Complete graph  
Hamiltonian graph  
Euler graph  
None of the above 
→ Hamiltonian graph will get more than one spanning tree.
→ Euler graph will get more than one spanning tree.
Question 34 
125  
64  
36  
16 
n=5
=5^{52}
=5^{3}
=125
Question 35 
O (n)  
O (n log n)  
O (e log n)  
O (e) 
1. A=∅
2. for each vertex v∈ G.V
3. MAKESET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v)∈G.E, taken in nondecreasing order by weight
6. if FINDSET(u)≠FINDSET(v)
7. A=A∪{(u,v)}
8. UNION(u,v)
9. return A
Analysis:
The running time of Kruskal’s algorithm for a graph G=(V,E) depends on how we implement the disjointset data structure.
→ Initializing the set A in line 1 takes O(1) time, and the time to sort the edges in line 4 is O(ElgE). (We will account for the cost of the V MAKESET operations in the for loop of lines 2–3 in a moment.)
→ The for loop of lines 5–8 performs O(E) FINDSET and UNION operations on the disjointset forest.
→ Along with the V MAKESET operations, these take a total of O((V+E)α(V)) time, where α is the very slowly growing function.
→ Because we assume that G is connected, we have E>=V1, and so the disjointset operations take O(Eα(V)) time.
→ Moreover, since α V=O(lg V)=O(lg E), the total running time of Kruskal’s algorithm is O(ElgE)
→ Observing that E<V^{2} , we have lg E=O(lg V), and so we can restate the running time of Kruskal’s algorithm as O(E lg V)
Question 36 
88  
91  
49  
21 
Question 37 
4n^{2}  
n  
4n4  
2n2 
2)Weight of the minimum spanning tree
= 42  1 + 43  2 + 44  3 + 45  4 .... + 4 n  (n1) 
= 4n  4
Question 38 
1  
2  
4  
6  
8 
Question 39 
is NOT ALWAYS TRUE?
The minimum weight edge of G is in T.  
The maximum weight edge of G is not in T.  
G has a unique cycle C and the minimum weight edge of C is also in T.  
G has a unique cycle C and the maximum weight edge of C is not in T.  
T can be found in O(n) time from the adjacency list representation of G. 
Question 40 
8  
16  
32  
64  
None of the above 
Question 41 
Which of the following statements is TRUE in the above graph? (Note that all the edge weights are distinct in the above graph)
There is more than one minimum spanning tree and similarly, there is more than one maximum spanning tree here.  
There is a unique minimum spanning tree, however there is more than one maximum spanning tree here.  
There is more than one minimum spanning tree, however there is a unique maximum spanning tree here.  
There is more than one minimum spanning tree and similarly, there is more than one secondbest minimum spanning tree here.  
There is a unique minimum spanning tree, however there is more than one secondbest minimum spanning tree here. 
Question 42 
Suppose the wavy edges form a Minimum Cost Spanning Tree for G. Then, which of the following inequalities NEED NOT hold?
cost(a, b) ≥ 6.  
cost(b, e) ≥ 5  
cost(e, f) ≥ 5.  
cost(a, d) ≥ 4  
cost(b, c) ≥ 4 
Question 43 
Which of the following statements is FALSE?
The tree T has to contain the edge e1  
The tree T has to contain the edge e2.  
The minimum weight edge incident on each vertex has to be present in T  
T is the unique minimum spanning tree in G.  
If we replace each edge weight wi = w(ei) by its square w^{2}_{i} , then T must still be a minimum spanning tree of this new instance. 
Question 44 
2015  
4030  
1008  
None of the above 
So weight of MST is (n1)*2 = (20161)*2=4030
Question 45 
Using Prim’s algorithm to construct a minimum spanning tree starting with node a, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
(a,b), (a,h), (g,h), (f,g), (c,f), (c,i), (c,d), (d,e)  
(a,b), (b,h), (g,h), (g,i), (c,i), (c,f), (c,d), (d,e)  
(a,b), (b,c), (c,i), (c,f), (f,g), (g,h), (c,d), (d,e)  
(a,b), (g,h), (g,f), (c,f), (c,i), (f,e), (b,c), (d,e)  
A and C 
The final sequence is ab, bc, ci, cf, fg, gh, cd, de