1
$\begingroup$

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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Exactly. There are different claims that can be made when the weights are not unique. One is that if there is only one edge of maximum weight in a cycle, then it cannot belong to any MST. This is what I'm using. Another is that, for every edge $e$ of maximum weight in a cycle (not necessarily unique!), there is a MST that does not contain $e$. $\endgroup$
    – Steven
    Mar 11, 2020 at 17:24
  • $\begingroup$ $e_1$ is defined as the edge of maximum weight of $C$ among the ones of $T_1$. $e_2$ is defined as the edge of maximum weight of $C$ among the ones of $T_2$. Therefore if $e_2$ weighs more than $e_1$ it is necessarily the heaviest edge of $C$. $\endgroup$
    – Steven
    Mar 11, 2020 at 17:27
  • $\begingroup$ I have edited the answer to be less compact and to explicitly handle all cases. Please see if this answers your question. $\endgroup$
    – Steven
    Mar 11, 2020 at 18:11
0
$\begingroup$

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...

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.