1
$\begingroup$

I'm asking about the answer here:

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

I didn't understand the best answer here

Choose edge $e \in T_1 \mathop{\Delta} T_2$ with $w(e) = \min W$, that is $e$ is an edge that occurs in only one of the trees and has minimum disagreeing weight. Such an edge, that is in particular $e \in T_1 \mathop{\Delta} T_2$, always exists: clearly, not all edges of weight $\min W$ can be in both trees, otherwise $\min W \notin W$. W.l.o.g. let $e \in T_1$ and assume $T_1$ has more edges of weight $\min W$ than $T_2$.

First of all, what does minimum disagreeing weight mean?

assume $T_1$ has more edges of weight $\min W$ than $T_2$.

Does the above line mean, $T_1$ has multiple edges with weight $\min W$

Now consider all edges in $T_2$ that are also in the cut $C_{T_1}(e)$ that is induced by $e$ in $T_1$. If there is an edge $e'$ in there that has the same weight as $e$, update $T_1$ by using $e'$ instead of $e$; note that the new tree is still a minimal spanning tree with the same edge-weight multiset as $T_1$. We iterate this argument, shrinking $W$ by two elements and thereby removing one edge from the set of candidates for $e$ in every step. Therefore, we get after finitely many steps to a setting where all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $g(e)$.

This paragraph seems to be a problem for me. So, we remove edges with weight $e$ which is also $\min W$ and replace it with $e'$. So we do that for all edge weight $e$ present in $T_1$

Therefore, we get after finitely many steps to a setting where all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $g(e)$.

I didn't understand this line at all. What is supposed to be $g(e)$?

Now we can always choose $e' \in C_{T_1}(e) \cap T_2$ such that we can swap $e$ and $e'$¹, that is we can create a new spanning tree

$\qquad \displaystyle T_3 = \begin{cases} (T_1 \setminus \{e\}) \cup \{e'\} &, w(e') \lt w(e) \\[.5em] (T_2 \setminus \{e'\}) \cup \{e\} &, w(e') \gt w(e) \end{cases}$

which has smaller weight than $T_1$ and $T_2$; this contradicts the choice of $T_1,T_2$ as minimal spanning trees. Therefore, $W_1 = W_2$.

Why is $w(e') \lt w(e)$ here? isnt $e'$ same as $e$ ? and why does $T_1,T_2$ contradict as minimal spanning trees?

$\endgroup$
1
  • 1
    $\begingroup$ You may want to take a look at my answer that proves a stronger result. $\endgroup$
    – John L.
    May 8, 2019 at 17:12

1 Answer 1

1
$\begingroup$

The question and this post refers to this answer at its version 2.

First of all, what does minimum disagreeing weight mean?

The better word should have been "distinguishing". If the set of edges of some fixed weight in $T_1$ is different from that of $T_2$, then $T_1$ and $T_2$ disagree on that weight, i.e., that weight is distinguishing the two minimal trees.

What is supposed to be $g(e)$?

That is a typo. It should have been $w(e)$.

Why is $w(e') \lt w(e)$ here? isn't $e'$ same as $e$ ? and why does $T_1,T_2$ contradict as minimal spanning trees?

Let us use a new dummy variable instead of $e'$ for the last part of that answer.

Let $f \in C_{T_1}(e) \cap T_2$. Had $f$ weighed the same as $e$, we should have update $T_1$ by using $f$ instead of $e$. Since we have done all such updates, $f$ must weigh differently from $e$. That is the conclusion in the previous paragraph, "all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $w(e)$".

There are two disjoint cases.

  • the case when $w(f)\lt w(e)$. Consider the spanning tree $(T_1 \setminus \{e\}) \cup \{f\}$, which is lighter than $T_1$.
  • the case when $w(f)\gt w(e)$. Consider the spanning tree $(T_2 \setminus \{f\}) \cup \{e\}$, which is lighter than $T_2$.

In either case, we have found a spanning tree that is lighter than a minimum spanning tree, which is a contradiction.

$\endgroup$
3
  • 1
    $\begingroup$ I will update this answer when the dust is settle here. $\endgroup$
    – John L.
    May 8, 2019 at 18:16
  • $\begingroup$ Thanks! I understood everything except this part "Had $f$ weighed the same as $e$, we should have update $T_1$ by using $f$ instead of $e$. Since we have done all such updates, $f$ must weigh differently from $e$". If $f$ was same as $e$, why would we choose $f$ instead of $e$ (even the $e$ is same right?) $\endgroup$ May 8, 2019 at 21:54
  • 1
    $\begingroup$ Before the replacement of $e$ in $T_1$ by $f$, $e$ in $T_1$ corresponded to $f$ in $T_2$. After the replacement, $f$ in $T_1$ corresponded to the same edge, $f$ in $T_2$. So each replacement made the difference between $T_1$ and $T_2$ smaller. After all possible replacements had been made, there should have been no pair of $(e,f)$ such that $w(e)=w(f)=\min(W)$, $e\in T_1$, $f\in C_{T_1}(e)\cap T_2$ and there should have no pair of $(e,f)$ such that $w(e)=w(f)=\min(W)$, $e\in T_2$, $f\in C_{T_2}(e)\cap T_1$, either. $\endgroup$
    – John L.
    May 8, 2019 at 23:19

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.

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