# Updating One Edge in MST
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.
# Case 1
**Case: The edge e is in T**
* Let e = (u,v) be an edge that belongs to the current T, and its weight is decreased

**Algorithm**
The algorithm simply updates the weight of e in T to the new smaller value without changing the tree edges.
* by decreasing the weight of an edge, it makes it more suitable and does not invalidate the MST
* cut property --> guarantees that any MST containing the edge before updating it remains valid

Therefore, if:
* e ∈ T: update its weight --> MST remains the same

# Case 2
**Case: The edge e is not in T**
* Let e = (u,v) be an edge not in T, and its weight decreases

**Algorithm**
* Add edge e to the MST T, creating a unique cycle
* after adding edge e, find the cycle formed --> (edge e) + (path between u and v)
* find the heaviest edge f on the cycle
* compare weights between e and f
* if new weight of e is smaller than weight of f, remove f and keep e
* if new weight of e is NOT smaller than weight of f, keep old MST
* resulting tree is the final MST

Adding e creates a cycle:
Cycle property --> maximum weight edge on the cycle cannot belong to an MST

Therefore, if:
* 𝑒 ∉ 𝑇: add e, find the cycle, remove heaviest edge on the cycle