Graph with exactly 2 Minimum Spanning Trees

Question

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.

Answer 1

Lemma: Let $C$ be a cycle of $G$ that contains an unique edge $e$ of maximum weight. Edge $e$ does not belong to any MST of $G$.

Proof: Suppose that a MST $T^* = (V, E^*)$ of $G$ contains $e = (u,v)$. Root $T^*$ in $u$ and let $f$ be any edge of $C \setminus E^*$ that has exactly one endpoint in the subtree of $T^*$ rooted in $v$ (this edge always exists since $C \setminus \{ e \}$ is a path from $v$ to $u$ that avoids $e$). The edge $f$ closes a fundamental cycle containing $e$ and is such that $w(f) < (e)$. Then $(V, (E^* \setminus \{e\}) \cup \{ f \}$) is a spanning tree of $G$ that weighs less than $T^*$. This is a contradiction. $\square$

Let $T_1 = (V, E_1)$ and $T_2 = (V, E_2)$ be two distinct MSTs of $G$. Let $C$ be a cycle in $(V, E_1 \cup E_2$). Let $M = \arg\max_{e \in C} w(e)$.

If $|M|>1$ we are done. Suppose then that $M = \{ e \}$. By the above lemma, $e$ is the unique heaviest edge of $C$ and hence it cannot belong to any MST of $G$. This is a contradiction since $e$ must belong to at least one of $E_1$ and $E_2$.

Answer 2

Consider the typical MST algorithms. You get exactly two MST if at some step you have to choose between two edges of equal weight, and that will happen only if they are part of a cycle. And they have to be cheap enough to get included in the MST, but that is harder to characterize...