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

Question

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?

Answer 1

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.