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? A) The edge with the second smallest weight is always part of any minimum spanning tree of G. B) One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G. C) Suppose S V be such that S and S V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V S. Such an edge will always be part of any minimum spanning tree of G. D) G can have multiple minimum spanning trees.

Official answer: A) The edge with the second smallest weight is always part of any minimum spanning tree of G.; B) One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.; C) Suppose S V be such that S and S V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V S. Such an edge will always be part of any minimum spanning tree of G.. Explanation: Since all edge weights in G are distinct, G has a unique Minimum Spanning Tree (MST). Let the edges in increasing order of weight be e1, e2, e3, e4, . - (A) is TRUE: By Kruskal's algorithm, e1 is always chosen. Since G is a simple graph, e2 cannot form a cycle with e1 (a cycle requires at least 3 edges in a simple graph). Thus, the edge with the second smallest weight (e2) is always included in the MST. - (B) is TRUE: e3 can only create a cycle if e1, e2, e3 form a triangle (K3) on 3 vertices. In this case, e3 is discarded. However, since the subgraph spanned by \e1, e2\ has only 3 vertices, any 4th distinct edge e4 must be incident to at least one new vertex or cannot form a cycle solely with \e1, e2\ (since a 3-vertex simple graph can have at most 3 edges). Thus, if e3 is rejected, e4 is guaranteed to be accepted. Therefore, one or both of e3 and e4 must belong to the MST. - (C) is TRUE: This is the standard Cut Property of MSTs: for any non-trivial cut (S, V S), the edge of minimum weight crossing the cut must belong to every MST (and here, the unique MST). - (D) is FALSE: When all edge weights in a connected undirected graph are distinct, the MST is always unique, so G cannot have multiple minimum spanning trees. Hence, the correct options are A, B, and C.

A) The edge with the second smallest weight is always part of any minimum spanning tree of G.

B) One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.

C) Suppose S V be such that S and S V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V S. Such an edge will always be part of any minimum spanning tree of G.

D) G can have multiple minimum spanning trees.

Algorithms · Graph Traversals, MSTs and Shortest Paths

Official IIT answer key · IIT Kharagpur · Audited Aug 2026

Take topic test

GATE CSE 2022 Q49 · MSQ · 2 marks

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?

Select one or more options

Key concept

Graph Traversals, MSTs and Shortest Paths

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals, MSTs and Shortest Paths

GATE questions on this topic heavily emphasize structural properties and theoretical invariants of Minimum Spanning Trees (MSTs) rather than raw algorithmic execution traces. Recurring themes include the Cut Property, the Cycle Property, distinct vs. non-distinct edge weights, and the invariance of MSTs under linear weight transformations compared to Shortest Paths. A typical problem presents either a small concrete graph (often with an unknown parameter or repeated weights) or a set of theoretical assertions evaluated across graph classes.

Full Graph Traversals, MSTs and Shortest Paths guide →

More on Graph Traversals, MSTs and Shortest Paths

All 7 questions on Graph Traversals, MSTs and Shortest Paths →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Algorithms · Graph Traversals, MSTs and Shortest Paths

Official IIT answer key · IIT Kharagpur · Audited Aug 2026

Take topic test

GATE CSE 2022 Q49 · MSQ · 2 marks

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?

Select one or more options

Key concept

Graph Traversals, MSTs and Shortest Paths

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals, MSTs and Shortest Paths

Full Graph Traversals, MSTs and Shortest Paths guide →

More on Graph Traversals, MSTs and Shortest Paths

All 7 questions on Graph Traversals, MSTs and Shortest Paths →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

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?

Step-by-step verified solution

Check you can still solve Graph Traversals, MSTs and Shortest Paths under a clock

More from GATE CSE 2022

More on Graph Traversals, MSTs and Shortest Paths

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?

Step-by-step verified solution

Check you can still solve Graph Traversals, MSTs and Shortest Paths under a clock

More from GATE CSE 2022

More on Graph Traversals, MSTs and Shortest Paths

Consider a simple undirected weighted graph GGG, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of GGG is/are TRUE?

Step-by-step verified solution

Check you can still solve Graph Traversals, MSTs and Shortest Paths under a clock

More from GATE CSE 2022

More on Graph Traversals, MSTs and Shortest Paths

Share this solution

Consider a simple undirected weighted graph GGG, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of GGG is/are TRUE?

Step-by-step verified solution

Check you can still solve Graph Traversals, MSTs and Shortest Paths under a clock

More from GATE CSE 2022

More on Graph Traversals, MSTs and Shortest Paths

Share this solution

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?

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?