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?
Solution :
The correct statements are:
1. In every cycle C of G, the edge with the largest weight in C is not in any MST
2. For every vertex v ∈ V, the edge with the smallest weight incident on v is in every MST
Here is the detailed step-by-step explanation of why these statements are correct:
1. Explanation of the Cycle Property Statement:
Let be any cycle in the graph , and let be the edge in with the strictly largest weight (since edge weights are unique). We want to prove that cannot belong to any minimum spanning tree (MST) of .
Suppose, for the sake of contradiction, that there is an MST that contains the edge . If we delete the edge from , the tree is disconnected into exactly two components, say and .
Since is part of the cycle , there must exist at least one other edge in the cycle that also connects and . Since is the unique edge with the largest weight in cycle , the weight of must be strictly less than the weight of :
If we construct a new spanning tree by removing and adding , the new tree remains connected and spans all vertices. However, the total weight of is strictly less than the total weight of . This contradicts the assumption that is a minimum spanning tree. Thus, the edge with the largest weight in any cycle cannot be in any MST.
2. Explanation of the Cut Property (Incident Edges) Statement:
For any vertex , let us define a cut in the graph that separates from all other vertices. This cut is represented by the partition .
The edges crossing this cut are precisely all the edges incident on the vertex . By the Cut Property of minimum spanning trees, for any cut of a graph, the edge with the minimum weight crossing that cut must belong to the MST. Because all edge weights in the graph are unique, there is a unique edge incident on that has the smallest weight among all incident edges.
Since is the unique minimum-weight crossing edge for the cut , it must be included in every MST of .
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.
Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.