Question Details

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?

Options

A

Every MST remains an MST, and every SP remains an SP.

B

MSTs need not remain MSTs, and every SP remains an SP.

C

Every MST remains an MST, and SPs need not remain SPs

D

MSTs need not remain MSTs, and SPs need not remain SPs.

Show Answer
Correct Answer
C Every MST remains an MST, and SPs need not remain SPs

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 G=(V,E) be a connected undirected graph with n=|V| vertices.
Any spanning tree T of G must contain exactly n-1 edges.
Let w(e) be the original weight of edge e, and let the new weight be w′(e)=w(e)+α.
The total weight of a spanning tree T under the new weight function w′ is:

W′(T)=∑e∈Tw′(e)=∑e∈T(w(e)+α)

Since there are exactly n-1 edges in T, this simplifies to:

W′(T)=(∑e∈Tw(e))+(n-1)α=W(T)+(n-1)α

Here, (n-1)α 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 T that minimized the original weight W(T) will also minimize the updated weight W′(T). Therefore, every MST remains an MST.

2. Effect on Shortest Paths (SPs):
Let P be a path between two vertices u and v. The number of edges in P (path length in terms of edges) can vary. Let k be the number of edges in P.
Under the new weight function, the total weight of path P becomes:

W′(P)=W(P)+kα

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 u and v connected by two alternative paths:
- Path P1 has 1 edge of weight 4.
- Path P2 has 2 edges of weights 1.5 and 2 (total original weight = 3.5).
Originally, P2 is the shortest path since 3.5<4.
Now, add α=2 to every edge weight:
- New weight of P1 = 4+2=6.
- New weight of P2 = (1.5+2)+(2+2)=3.5+2(2)=7.5.
After the update, P1 becomes the shortest path (6<7.5). Thus, shortest paths need not remain shortest paths.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

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.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

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.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: