# Sensitivity analysis of $MST$ edges

I am working on the following exercise:

Consider an undirected graph $$G = (V,E)$$. Let $$T^* = (V,E_{T^*})$$ be a $$MST$$ and let $$e$$ be an edge in $$E_{T^*}$$. We define the set of all values that can be assigned to $$w_e$$ such that $$T^*$$ remains a MST as $$I_e$$.

1. Show that $$I_e$$ is an interval.
2. Devise an efficient algorithm to calculate $$I_e$$ for a given edge $$e$$.
3. Devise an efficient algorithm that determines all $$I_e$$ in one step. It should be more efficient than repeatedly using the algorithm from 2.

I did the following:

1. Consider an edge $$e$$ in $$E_{T^*}$$. Delete it from $$G$$ and find the new lowest weighted edge connecting the resulting components, say $$e'$$. The upper bound for $$I_e$$ is $$w(e')$$. The lower bound would be $$-\infty$$.
2. Use the algorithm sketched in 1.
3. I do not know what to do here. Could you help me?

The solution in short. For each edge $$e$$ not in the tree, check the path between its endpoints in the tree. The weight of each edge on this path is upper-bounded buy the weight of $$e$$. Keep track of the smallest upper-bound for each edge on the tree while iterating over all edges not in the tree. Following is a sketch of the correctness.
Let us call an edge in a simple cycle Heavy for this cycle, if its weight is maximum among all edges in the cycle. We claim that each edge $$e$$ in $$G\setminus T^*$$ is Cycle heavy for some cycle in $$G$$.
Proof. By adding the edge $$e$$ to the tree, it constructs a cycle with a path in the tree between its endpoints. If there is an edge in the cycle with strictly heavier weight, we can remove this edge and keep $$e$$ constricting a lighter tree which contradicts the assumption that the given tree is minimum.