Suppose given complete undirected weighted graph $G=(V,E)$ with $n$ vertices, also we have Minimum spanning tree $T$ that obtained from $G$. if we decrease the weight of $n$ arbitrary edges, how we can find MST of $G$ without computing MST of $G$?
My idea is as follow:
create a graph $T'$ with $n$ vertices that contains those edges that decreased.
Compute MST $T''$ from $T\cup T'$.
now suppose MST of $G$ after decrease edges weights be $T'''$, but I can't prove that $T'''=T''$.
