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)<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?