## Problem

Suppose we are given both an undirected graph G with weighted edges and a minimum spanning tree T of G.

Describe an algorithm to update the minimum spanning tree when the weight of a single edge e is decreased.

The input to your algorithm is the edge e and its new weight; your algorithms should modify T so that it is still a minimum spanning tree.

Hint: Consider the cases e in T and e not in T separately.

## Algorithm description

Let the edge whose weight decreases be e = (u, v). Update the weight of e in the graph.

instance 1: e is already in the MST T
Simply update its weight inside T. Lowering the weight of a tree edge cannot make T non-optimal, so no edges need to be replaced.

instance 2: e is not in T

Add e to T. Since T is a tree, adding one edge creates exactly one simple cycle. This cycle is formed by e plus the unique u-to-v path in T. Scan the cycle to find the edge f with the largest weight. If the new weight of e is less than the weight of f:
Remove f and keep e in the tree.
This yields a new spanning tree of strictly smaller weight.
Otherwise: Do not modify T and simply disregard e.

To obtain the path between u and v, run BFS or DFS on T (which has only V-1 edges).

fun reviseMST(Graph H, Tree M, Edge q, newW) {
    var a, b = endpoints(q);

    setWeight(q, newW);

    if (q belongsTo M) {
        return M;
    }

    var route = findTreePath(M, a, b);   // unique path in MST via DFS/BFS
    var heavy = maxWeightEdge(route);    // edge on route with maximum weight

    if (getWeight(q) < getWeight(heavy)) {
        M = M - {heavy};
        M = M + {q};
    }

    return M;
}

## Proof of Correctness:

We explain why the algorithm always returns a minimum spanning tree after the weight decrease.

instance 1: e is in T
Reducing the weight of a tree edge only lowers the total weight of T. Since no other spanning tree becomes better relative to T, its structure does not need to change. T remains an MST.

instance 2: e is not in T
When e is added to T, exactly one cycle is formed. By the Cycle Property of MSTs:
On any cycle, the heaviest edge cannot belong to an MST if there exists a lighter alternative on the same cycle.

Two possibilities here:
1) New weight of e is less than the weight of the heaviest edge f on the cycle.
In this case, an MST must include e and exclude f. Replacing f with e strictly reduces the total weight of T. The resulting tree is an MST for the updated graph.

2) New weight of e is greater than or equal to the weight of f.
Here, using e does not improve the total weight. The cycle property does not force e into the MST, so the original T remains optimal and unchanged.

Therefore, in all cases the algorithm preserves the minimum spanning tree.

## Time complexity:

Checking whether e is in T: O(1) with appropriate storage.

instance 1: Only update the weight: O(1).
instance 2: BFS/DFS on T to find the u-to-v path: O(n)

Scanning the path to find the maximum-weight edge: O(n)
This is significantly faster than recomputing the MST from scratch.