let T=(V,A') and T'=(V,A) two MST's in an un-directed, weighted graph G=(V,E). prove that in each cycle of (V, A U A') there are two different edges with the same weight.
is this a formal correct proof?
Assume that there is a cycle C such that every edge has different weight. let e be the heaviest edge in C [exists since all the weights are different]. KRUSKAL algorithm would never choose e for MST since it'll pass all the other edges before getting to e, and by the time we got to e=(u,v) , u and v are already connected, so there are at least 2 edges in each cycle that weight the same - they are both the "heaviest".