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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top