Say that a graph, $ G = (V, E)$ has 2 minimum spanning trees (MSTs). Given this condition stipulated, prove that any cycle formed by all the edges in both the MSTs (i.e., the union of the edges in of the 2 MSTs) that at minimum, 2 of the edges in the set which is the union of the edges have equal weight. Also show that either this edge is the largest weight in the cycle, or not the largest weight in the cycle.

Overall am pretty stuck on this question.

My initial thoughts are the following: In any graph with more than 1 MST, clearly this means that the edge weights can’t be distinct, otherwise there wouldn’t be multiple MSTs. Also the graph $ G$ must contain cycles, otherwise, it wouldn’t have multiple MSTs.

My idea for proving that any cycle formed by the union of the edges of the two MSTs would be that in $ MST_1$ there is some edge, $ e$ that is not in $ MST_2$ and there is also some edge $ f$ that is not in $ MST_1$ . Using the cut property if $ e$ was not placed in $ MST_2$ and $ f$ was not placed in $ MST_1$ then then we have that the weight of $ f$ , and $ e$ , $ w(f) = w(e)$ .

Having trouble formalizing this though, and wondering if its actually a correct deduction. I feel that it makes sense given some examples and drawing, but not quite certain that’s actually true. Then from there I felt that there had to be some node, $ z$ such that $ z$ had 2 edges with the same weights, and when we combine the edges from $ MST_1$ and $ MST_2$ we end up with both the edges from $ z$ forming a cycle, and the edges are the same weights, so we know at least 2 of the edges form a cycle… Or the union of the edges could form a cycle graph itself which would then show that the 2 edges with the same weights are part of a cycle, I think? Is this somewhat on the right track? Is there some sort of condition for a graph, $ G$ , in order for it to have exactly 2 MSTs? Or is there some property I’m missing?

If someone could please provide a bit of guidance in the right direction, it would be extremely appreciated. Thanks.