GateAI
Minimum Spanning Trees

GATE CSE 2016 Set 1 · Q40

MCQ2 marksMedium

Time

G=(V,E)G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and ee is a particular edge of GG. Which of the following statements about the minimum spanning trees (MSTs) of GG is/are TRUE? I. If ee is the lightest edge of some cycle in GG, then every MST of GG includes ee II. If ee is the heaviest edge of some cycle in GG, then every MST of GG excludes ee

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: B) II only

Minimum Spanning Trees

Let us analyze both statements for a connected undirected graph with distinct edge weights (which guarantees a unique MST):

  1. Statement I is FALSE: The Cycle Property states that the strictly heaviest edge in any cycle cannot be in the MST. However, being the lightest edge of *some* cycle does not guarantee inclusion in the MST. For example, consider a 3-cycle where all three edges have large weights compared to other alternative paths in the graph. The lightest edge of this cycle might still be the heaviest edge in a cut, or it may not be part of the MST.

  2. Statement II is TRUE: This is the standard Cycle Property of Minimum Spanning Trees: for any cycle CC in a graph GG, the edge with the strictly largest weight in CC cannot be part of any MST. If an MST included this heaviest edge, removing it would disconnect the tree into two components, and there would be another edge in the cycle CC with a strictly smaller weight connecting the two components, yielding a spanning tree with a smaller total weight (a contradiction).

Therefore, only statement II is true, which corresponds to option (B).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Minimum Spanning Trees previous year question is Q40 of the GATE CSE 2016 Set 1 paper. Find more GATE CSE PYQs on Minimum Spanning Trees in Algorithms, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Minimum Spanning Trees PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Minimum Spanning Trees in GATE CSE

Minimum Spanning Trees has 13 GATE CSE PYQs across 9 papers from 2011 to 2026. 5 of them are 2-mark MCQs like this one, and GATE CSE 2016 Set 1 has 2.

How GATE tests Minimum Spanning Trees

More from GATE CSE 2016 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2016 Set 1 · Q40 · MCQ

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

Topic-wise GATE CS PYQs with verified steps

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