Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same weight as $e$ (including $e$ itself) is the same as the number of edges in $E_2$ with the same weight as $e$? If the statement is true, then how can we prove it?

share|improve this question
    
One tricky but feasible approach is to show 1) Kruskal's algorithm can produce every minimal spanning tree and 2) all minimal spanning trees found by Kruskal have the same edge-weight multiset. –  Raphael Mar 6 '13 at 10:38
add comment

1 Answer 1

up vote 7 down vote accepted

Claim: Yes, that statement is true.

Proof Sketch: Let $T_1,T_2$ be two minimal spanning trees with edge-weight multisets $W_1,W_2$. Assume $W_1 \neq W_2$ and denote their symmetric difference with $W = W_1 \mathop{\Delta} W_2$.

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

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

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


  1. The nodes incident of $e$ are in $T_2$ connected by a path $P$; $e'$ is the unique edge in $P \cap C_{T_1}(e)$.
share|improve this answer
2  
In reference to Dave's comment, I came up with this proof after 0) believing I had a counter-example which I saw was wrong after TikZing it, 1) trying to prove the statement but failing, 2) trying to construct a counter-example based on where the proof failed and failing again, and finally 3) using the way these new examples failed to work for coming up with the proof. That's probably also why it is not as refined as it could be. –  Raphael Jun 5 '12 at 11:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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