MinimumSpanningTree
Question 1 
• 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 2 
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 3 
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 4 
Let G = (V, E) be any connected undirected edgeweighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:

(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 5 
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 6 
G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

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 7 
69  
70  
71  
72 
⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69
Question 8 
995  
996  
997  
998 
Question 9 
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 10 
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 11 
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 12 
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 13 
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 14 
(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 15 
(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 16 
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 17 
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 18 
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 19 
(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 20 
29  
31  
38  
41 
1+2+3+2+8+4+4+2+5 =31
Question 21 
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 22 
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'.