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 statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?
Solution :
The correct option is: Every MST remains an MST, and SPs need not remain SPs.
Let us understand why this statement is true by analyzing the effect of adding a positive constant to the weight of every edge on Minimum Spanning Trees (MSTs) and Shortest Paths (SPs) separately.
1. Effect on Minimum Spanning Trees (MSTs):
Let be a connected undirected graph with vertices.
Any spanning tree of must contain exactly edges.
Let be the original weight of edge , and let the new weight be .
The total weight of a spanning tree under the new weight function is:
Since there are exactly edges in , this simplifies to:
Here, is a constant value added to the total weight of every spanning tree in the graph. Since the weights of all spanning trees are shifted by the exact same constant, the relative ordering of their weights does not change. Thus, any tree that minimized the original weight will also minimize the updated weight . Therefore, every MST remains an MST.
2. Effect on Shortest Paths (SPs):
Let be a path between two vertices and . The number of edges in (path length in terms of edges) can vary. Let be the number of edges in .
Under the new weight function, the total weight of path becomes:
Since paths between two vertices can have different numbers of edges, adding to every edge penalizes paths with more edges more heavily than paths with fewer edges. Consequently, the relative ranking of path weights can change, and a path that was previously the shortest may no longer be so.
For example, consider a graph with two vertices and connected by two alternative paths:
- Path has 1 edge of weight 4.
- Path has 2 edges of weights 1.5 and 2 (total original weight = 3.5).
Originally, is the shortest path since .
Now, add to every edge weight:
- New weight of = .
- New weight of = .
After the update, becomes the shortest path (). Thus, shortest paths need not remain shortest paths.
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.