Minimum Spanning Trees: GATE CS previous year questions (Algorithms)

GATE CS 2026 Set 1MSQ2 marksMedium (estimate)
GATE CS 2026 Set 1, Q.49
Let $G (V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?
Minimum Spanning Trees
GATE CS 2025 Set 1MCQ1 markEasy (estimate)
GATE CS 2025 Set 1, Q.18
Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$ . For any two vertices, $u$ and $v$ , let $d_{1} (u, v)$ and $d_{2} (u, v)$ be the...
Minimum Spanning Trees
GATE CS 2025 Set 1NAT2 marksMedium (estimate)
GATE CS 2025 Set 1, Q.64
The maximum value of $x$ such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is _________ . (answer in integer) An undirec...
Minimum Spanning Trees
GATE CS 2025 Set 2MCQ2 marksEasy (estimate)
GATE CS 2025 Set 2, Q.37
Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $α$ is added to the weight of every edge. Which ONE of the following st...
Minimum Spanning Trees · Single-Source and All-Pairs Shortest Paths
GATE CS 2024 Set 2MSQ2 marksHard (estimate)
GATE CS 2024 Set 2, Q.51
Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following state...
Graph Theory · Minimum Spanning Trees
GATE CS 2024 Set 2NAT2 marksMedium (estimate)
GATE CS 2024 Set 2, Q.59
The number of distinct minimum-weight spanning trees of the following graph is _________ Undirected weighted graph with 7 vertices a, b, c, d, e, f, g and 12 edges: (a,b)=1, (a,...
Minimum Spanning Trees · Graph Theory
GATE CS 2022MSQ2 marksMedium (estimate)
GATE CS 2022, Q.49
Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?
Minimum Spanning Trees
GATE CS 2021 Set 1NAT1 markMedium (estimate)
GATE CS 2021 Set 1, Q.27 (CS Q.17)
Consider the following undirected graph with edge weights as shown: A 3 by 3 grid graph with 9 vertices and labeled edge weights of 0.1 and 0.9. The number of minimum-weight spa...
Minimum Spanning Trees
GATE CS 2021 Set 2MCQ1 markMedium (estimate)
GATE CS 2021 Set 2, Q.11 (CS Q.1)
Let $G$ be a connected undirected weighted graph. Consider the following two statements. $S_{1}$ : There exists a minimum weight edge in $G$ which is present in every minimum spann...
Minimum Spanning Trees
GATE CS 2016 Set 1MCQ1 markMedium (estimate)
GATE CS 2016 Set 1, Q.24 (CS Q.14)
Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements...
Minimum Spanning Trees
GATE CS 2016 Set 1NAT2 marksMedium (estimate)
GATE CS 2016 Set 1, Q.49 (CS Q.39)
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...
Minimum Spanning Trees
GATE CS 2016 Set 1MCQ2 marksMedium (estimate)
GATE CS 2016 Set 1, Q.50 (CS Q.40)
$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 spa...
Minimum Spanning Trees
GATE CS 2015 Set 1NAT2 marksHard (estimate)
GATE CS 2015 Set 1, Q.53 (CS Q.43)
The graph shown below has 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...
Minimum Spanning Trees
GATE CS 2015 Set 3NAT2 marksEasy (estimate)
GATE CS 2015 Set 3, Q.50 (CS Q.40)
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 f...
Minimum Spanning Trees
GATE CS 2014 Set 2NAT2 marksMedium (estimate)
GATE CS 2014 Set 2, Q.62 (CS Q.52)
The number of distinct minimum spanning trees for the weighted graph below is _____. Weighted undirected planar graph with edge weights 1 and 2 for MST enumeration Weighted grap...
Minimum Spanning Trees
GATE CS 2011MCQ2 marksMedium (estimate)
GATE CS 2011, Q.54 (CS Q.54)
What will be the cost of the minimum spanning tree (MST) of such a graph with $n$ nodes?
Minimum Spanning Trees
GATE CS 2011MCQ2 marksMedium (estimate)
GATE CS 2011, Q.55 (CS Q.55)
The length of the path from $v_{5}$ to $v_{6}$ in the MST of previous question with $n = 10$ is
Minimum Spanning Trees

Questions

Other topics of Algorithms