# Prove: If $T’$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree

Prove: If $$T’=(V,F’)$$ is not a MST of $$G=(V,E)$$, then there are edges $$e’ \in F$$ and $$e \in$$ $$E$$ \ $$F$$ such that $$w(e) and $$T’$$ \ $$\{e’\} \cup \{e\}$$ is a spanning tree.

My idea:

Let $$T=(V,F)$$ be a MST of $$G$$

for all $$e \in T$$, try to insert it into $$T’$$ and see if there is an edge in the cycle created that is heavier than $$e$$. If we found such $$e$$ we are done.

If not, define $$G’=(V,F \cup F’)$$

This graph obviously has a MST.

We didn’t find a suitable $$e$$ in the previous part so all edges in $$F$$ may be colored in red.

That means there is a MST $$T”=(V,F”)$$ such that $$F” \ F’$$ but that is impossible because $$T’$$ is not a MST of $$G’$$, because $$T$$ is lighter.

Does that seem correct?