# Minimum Spanning Tree

 Question 1
Let G be a connected undirected weighted graph. Consider the following two statements.

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.
S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree.

Which one of the following options is correct?
 A Both S1 and S2 are true B S1 is true and S2 is false C S1 is false and S2 is true D Both S1 and S2 are false
GATE CSE 2021 SET-2   Algorithm
Question 1 Explanation:
 Question 2
Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is __________
 A 4 B 6 C 5 D 3
GATE CSE 2021 SET-1   Algorithm
Question 2 Explanation:
 Question 3
Consider a graph $G=(V,E)$, where $V=\{v_1,v_2,...,v_{100}\}$, $E=\{(v_i,v_j)|1\leq i \lt j\leq 100\}$, and weight of the edge $(v_i,v_j)\; is \; |i-j|$. The weight of minimum spanning tree of G is _________
 A 100 B 99 C 199 D 90
GATE CSE 2020   Algorithm
Question 3 Explanation:
 Question 4
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 weighed edge $(u,v)\in V \times V$ is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
 A $\Theta (|E|+|V|)$ B $\Theta (|E||V|)$ C $\Theta (|E|\log |V|)$ D $\Theta (|V|)$
GATE CSE 2020   Algorithm
Question 4 Explanation:
 Question 5
Let G be any connection, weighted, undirected graph:

I. G has a unique minimum spanning tree if no two edges of G have the same weight.
II. G has a unique minimum spanning tree if, for every cut of G, there is a unique minimum weight edge crossing the cut.

Which of the above two statements is/are TRUE?
 A I only B II only C Both I and II D Neither I nor II
GATE CSE 2019   Algorithm
Question 5 Explanation:
 Question 6
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 ______.
 A 3 B 4 C 5 D 1
GATE CSE 2018   Algorithm
Question 6 Explanation:
 Question 7
Let G = (V, E) be any connected undirected edge-weighted 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?
 A (I) only B (II) only C Both (I) and (II) D Neither (I) nor (II)
GATE CSE 2017 SET-1   Algorithm
Question 7 Explanation:
 Question 8
G = (V,E) is an undirected simple graph in which each edge has a distinct weight,and e is a particular edgeof 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
 A I only B II only C both I and II D neither I nor II
GATE CSE 2016 SET-1   Algorithm
Question 8 Explanation:
 Question 9
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 haveis .
 A 6 B 7 C 8 D 5
GATE CSE 2016 SET-1   Algorithm
Question 9 Explanation:
 Question 10
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increasedby the same value ,then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change
 A P only B Q only C Neither P nor Q D Both P and Q
GATE CSE 2016 SET-1   Algorithm
Question 10 Explanation:
There are 10 questions to complete.

### 4 thoughts on “Minimum Spanning Tree”

1. in ques 24 plz update option B (b-c) –> (d-c)