# Updating One Edge in MST Problem
## 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.

## Algorithm Description
There are two cases to look at:

Case 1: The decreased edge e is already in the MST T
If e is already in T, reducing its weight only improves the total weight of T, it will still hold all properties of an MST, thus do nothing.

Case 2: The decreased edge e = (u,v) is not in the MST T
After decreasing the weight, edge e might become good enough to belong in the MST. If we try hadding it to T, the tree will become a cycle. In order to restore a spanning tree, we must remove the maximum weight edge on the unique path between u and v in T. We will do this by first inserting e into T, forming a cycle. Then we find the heaviest edge f on the u->v path in the current MST. If the weight of e is less than the weight of f, then replace f with e since it produces a cheaper spanning tree. Else, do nothing as the old MST would still be optimal.

fun updateMST(G, T, e, newWeight) {
    var u, v = endpoints of e;
    
    weight(e) = newWeight;
    
    if (e is in T) {
        return T;
    }
    
    var path = pathInT(u,v); a function that finds the unique path in the MST using dfs
    var f = edge with maximum weight on path;
    
    if (weight(e) < weight(f)) {
        T = T - {f};
        T = T + {e};
    }
    
    return T;
}

## Correctness Proof
Goal: Show that after the algorithm runs, the resulting Tree T' is a minimum spanning tree of G.

### Base Cases:
Case: e is in T
- If e is already belonging to the MST, decreasing its weight can't violate the cut or cycle properties, replacing no edges is necessary, and the tree stays a valid MST. Thus this is correct.

Case: E is not in T
- We add e to create a cycle and remove the heavist edge on that cycle if beneficial. This will follow from the Cycle Property. Since the old MST plus e creates exactly one cycle, removing the heaviest edge on the cycle will yield a valid MST. If the heaviest edge is not e, and e is now light enough, the replacement lowers the total weight and must be part of the new MST.

### Inductive Step
Assume the algorithm correctly maintains the MST property for all trees with fewer than n nodes.

Consider a tree T with n vertices. Adding an edge creates exactly one cycle due to the tree property. The algorithm removes exactly one edge, restoring a spanning tree. By the cycle property, choosing the maximum-weight edge ensures minimality, thus no other weights changed and no other part of the MST is affected.

Therefore, by inducted the updates structure is still an MST.

## Time Complexity
Let V = |V|, E = |E|

First check if e is in T, if so then O(1)
Then find path from u to v in MST using dfs which is O(V)
Then find the maximum-weight edge on that path doing a traversal of O(V)
Replace edge if needed which is O(1)

The total time complexity would be