2
$\begingroup$

We learned this theorem. Given an undirected graph $G$ with weight function $w : E \rightarrow \mathbb{R}$, if $T$ and $T'$ are two MST's (minimum spanning trees) of $G$, with distinct edges ($𝑇 \cap 𝑇′= \varnothing$), then $T$ has two edges with the same weight.

Can you help and give an intuition for this theorem and why it is true and how to prove it? thanks

$\endgroup$
7
  • $\begingroup$ Are there any restrictions on the weight function? If not, the claim would fail if all edges have distinct weights. $\endgroup$ – quasi Apr 14 at 18:37
  • $\begingroup$ no, there is no restrictions on weight function. but you can deduce that from the assumption that T and T' are two MST's with no overlapping edges that G doesn't have distinct weights. $\endgroup$ – user14732 Apr 14 at 18:42
  • $\begingroup$ The point of my initial comment is that, if there are no restrictions on the weight function, the theorem is false (provided there exists a graph having two spanning trees with no edges in common). $\endgroup$ – quasi Apr 14 at 18:45
  • $\begingroup$ there is no restrictions, can you explain why you think it is false ? $\endgroup$ – user14732 Apr 14 at 18:50
  • $\begingroup$ @quasi The restriction on the weight function is that there are two distinct MSTs. If all edges have distinct weights, that's impossible. $\endgroup$ – Misha Lavrov Apr 14 at 18:59
3
$\begingroup$

Let $e'$ be an edge with minimum weight in $T \cup T'$. Suppose for the moment that $e'$ is in $T'$. Then by assumption, $e'$ is not in $T$. It is well-known that in this case $T + e'$ contains a circuit $C$ and that for any edge $e \in C$, $T + e' - e$ is a spanning tree. The cost of this tree is $w(T) + w(e') - w(e) \leq w(T)$ (here we use the minimality of $e'$). But since $T$ was a MST , we can't have strict inequality here, and it follows that $w(e) = w(e')$. This holds for every edge of $C$, and since $C$ was a circuit in $T+e'$, it must have at least three edges, and so at least two edges in $T$.

What if $e'$ was in $T$ and not $T'$? Well, the previous argument showed that there is, after all, an edge (in fact, at least two edges) in $T'$ with the same weight as $e'$, so we can still assume that $e'$ is in $T'$.

Edit: I don't have a really good intuition for why this works, but the following ideas may be helpful in thinking about this and similar problems. It is well-known that the greedy algorithm (also known as Kruskal's algorithm) finds a MST. What is less commonly known is that every MST arises as the output to the greedy algorithm. That is, for any MST $T$, we can make the greedy algorithm output $T$ by choosing appropriately whenever we have a choice between multiple edges (necessarily of the same weight).

This somehow suggests that the more edges in $G$ there are with the same weight, the more MSTs we can find, and vice versa. Indeed, it immediately gives that if every edge weight is distinct, then there is a unique MST. It also shows that in every MST there is an edge that is a cheapest edge in $G$. So if there is a unique cheapest edge, then we can't have two edge-disjoint MSTs. On the other hand, if there are at least two cheapest edges in $G$, then every MST will contain at least two such edges, since the first two choices of the greedy algorithm will be from among these. So we get another proof of your theorem, modulo the fact that the greedy algorithm finds every MST. But the proof of the latter uses very similar ideas to those in my original proof.

$\endgroup$
4
  • $\begingroup$ Nice work +1. I was slowly working out the implication of those two edge-disjoint MSTs, It feels like there could be a lot more special properties here. $\endgroup$ – Joffan Apr 14 at 19:31
  • $\begingroup$ thank you, I understood the proof, but I didn't get the intuition from the solution, why this theorem makes sense? $\endgroup$ – user14732 Apr 14 at 19:33
  • $\begingroup$ I added some discussion, I hope it gives you some additional intuition about this problem. $\endgroup$ – Dániel G. Apr 14 at 20:13
  • $\begingroup$ Dániel I feel like the minimum edge weight is going to propagate through both MSTs until all edges in $T$ and $T'$ are at that weight - each min-weight edge joining a distinct cycle in the other tree, "infecting" all the edges in that cycle with the same weight, which can then join the other tree to further spread the same weight value. $\endgroup$ – Joffan Apr 14 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.