Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$.

Now let $T'$ be some other spanning tree of $G$ (doesn't have to be minimum) with edge weights: $w'_1 \le w'_2 \le ... \le w'_{n-1}$.

I need to prove\disprove the following claim: for every $i$: $w_i \le w'_i$.

I've tried to find a counterexample, but I wasn't successful. So I'm quite sure the claim is correct. However, I had trouble to prove it formally.

I assume the contrary, which means there is an $i$ that satisfies $w'_i < w_i$ and I take the first one that does. I tried adding it to the tree $T$ or trying to find a minimum spanning tree with this edge using Kruskal, but no luck.

  • Well I wasn't sure how to phrase it in the title, but it means that there is an edge weight $w'_i < w_i$ in $T'$ – Gabi G Dec 4 at 18:44
  • And I need to formally prove that such thing cant happen – Gabi G Dec 4 at 18:44

Here are some hints:

  1. Flesh out your counterexample with quantifiers properly: "There exists a graph $G$, and a minimum spanning tree $T$ for $G$ with edge weights $w_1 \le w_2 \le \dots \le w_{n-1}$, and another spanning tree $T'$ of $G$ with edge weights $w'_1 \le w'_2 \le \dots \le w'_{n-1}$, and an integer $i$ obeying $1 \le i \le n-1$, such that $w'_i < w_i$". In a situation like this, from the set of all such counterexamples ($(G, T, T', i)$ tuples), you are free to choose one having minimum possible $i$, and it's nearly always useful (and never harmful) to do so.
  2. "I tried adding it to the tree $T$" -- you must first show that it is not already in $T$. Here you can use minimality of $i$ for edges to the left, and the increasing weight order for edges to the right.
  3. Let's add it to $T$, to make a graph I'll call $G_2$. What noticeable feature does $G_2$ contain?
  4. What simple modifications could you make to that feature in $G_2$ to turn it back into a tree? Hint: With this particular feature, there will always be at least 3 ways to do this, and there could be as many as $n$.
  5. Can you choose an option in the previous step that will lead to a tree that is strictly lighter than $T$, and thus a contradiction (since we assumed $T$ to be minimal)?
  • So $G_2$ will have a cycle – Gabi G Dec 4 at 18:46
  • Let's call this edge $e=${$u,v$}. the cycle is between $u and v$. Since the path between was already existent in $T$ is it correct that the edge that wights more in $T$ is in this path? – Gabi G Dec 4 at 18:50
  • 1
    I'll write here the steps that I went through: 1. I look at the minimal $i$ that satisfies $w'_i < w_i$. 2. I look at the edges of $T$ that are of weight $ \le w'_i$ (there are $i-1$ edges like this) and I look at the edges of $T'$ that are of weight $ \le w'_i$ (there are at least $i$ edges like this). 3. Since a forest with $n$ nodes and $k$ edges has $n-k$ connected components, this sub-forest $T$ has more connected components the sub-forest $T'$. 4.Therefor there are nodes $u,v$ that are connected in the sub-forest of $T'$ but not in the sub-forest of $T$. – Gabi G Dec 4 at 20:47
  • 1
    5.Since $T$ himself is a spanning tree, there exists a path between $u$ and $v$ in $T$, and it has to contain at least one edge with weight $>w'_i$. 6.What is left is to get a contradiction to the fact that $T$ is a minimum spanning tree, and this is what I couldn't manage. – Gabi G Dec 4 at 20:49
  • 1
    If we take look at the path between $u$ and $v$ in $T$ and remove the "heavy" edge on it then we get two components. Then, there must exist an edge in the cheap path in $T'$ that will reconnect them. If we add it to what's left of $T$ we get a cheaper spanning tree => contradiction to the fact that $T$ is a MST – Gabi G Dec 5 at 1:58

Let us fix $G$ and $T$, a minimum spanning tree (MST) of $G$ as in the question. Assume weights of all edges are distinct; we will come back to the general case later.

Since all weights are distinct, there is one-to-one correspondence between edges and their weights.

Let $e_i$ be the edge with weight $w_i$ and $e_i'$ be the edge with weight $w_i'$. Let $T_i$ be the graph with edges $\{e_1, \cdots, e_i\}$ for $i\le n-1$. The proof of Kruskal's algorithm in the case of $G$ proves, in fact, $G$ has a unique MST that will be found by Kruskal's algorithm, because all weights are distinct. Specifically, the case "Otherwise, $e$ is not in $T$" cannot happen.

Minimality Lemma. If an edge not in $T_i$ can be added to $T_i$ without creating a cycle, $e_{i+1}$ must not weigh more than that edge.

Proof. Kruskal's algorithm tries adding the edge of the least weight among the available edges repeatedly, thus including $e_1, e_2, \cdots$ to form $T$ in that order. Let us inspect the moment when Kruskal's algorithm adds $e_{i+1}$ to $T_i$. If $e$ is an edge that weigh less than $e_{i+1}$, it must have been tried to be added to $T_k$ for some $k\le i$. Either $e$ was added to $T_k\subseteq T_i$ or a cycle was created at that time, which means adding it to $T_i$ will create a cycle, too. Done.

For any graph $S$, let $p(S)=0$ if $e_1\not\in S$; otherwise let $P(S)$ be the largest index $k$ such that the first $k$ lightest edges in $S$ is the same as the first $k$ lightest edges in $T$. WLOG, let $T'$ be a counterexample such that $p(T')$ is the largest (among all spanning trees of $G$). Let $q=p(T')$.

Observation: $w_{q+1}\lt w'_{q+1}$.
Proof. $\{e_1, e_2\cdots, e_q\}\subseteq T'$. Consider $e_{q+1}'$, the next heavier edge in $T'$. The Minimality Lemma tells that $e_{q+1}$ does not weighs more than $e_{q+1}'$. If it weighs the same as $e_{q+1}'$, then it is $e_{q+1}'$, which contradicts to our assumption of $q$ being the largest. So it must weigh less than $e_{q+1}'$. Done.

Since $T'$ is a spanning tree, if we add $e_{q+1}\not\in T'$ to $T'$, we must have created a cycle. Since we do not have a cycle in $T_{q+1}$, there must be an edge $e'\not\in T_q$ in that cycle. The above observation tells us $e_{q+1}$ weighs less than $e'$.

Let $T''$ be $T'$ with $e'$ replaced by $e_{q+1}$. Since $e'$ and $e_{q+1}$ are on that same cycle, $T''$ is also a spanning tree. Since the only difference between $T'$ and $T''$ is one edge of $T'$ is replaced with an edge of smaller weight, $T''$ is also a counterexample. Since both the first $q+1$ lightest edges of $T''$ and that of $T$ are $\{w_1, w_2\cdots, w_q, w_{q+1}\}$, $p(T'')\ge q+1>q$. This contradicts the assumption that $q$ is the largest. Done.


How about the general cases when all weights are not distinct?

For any $\epsilon>0$ that is smaller than the minimum positive difference among the original weights, if we subtract $\epsilon/i$ weight from $e_i$ and subtract $\epsilon/(2dn)$ weight from other edges using different positive integer $d$ for different edges, all new weights will be different and, since edges of $T$ are reduced more, $T$ remains to be an MST.

Letting $\epsilon$ go to 0 to take the limit of the inequalities that we have proved in the cases of distinct weights, we will obtain the same inequalities in the general cases.


Interested readers may enjoy the following exercise.

Exercise. Generalize MST $T$ to minimum-weighted sub-forest.

Problem. Can we prove the above generalization directly?

  • What is $G'_{p(T')}$? – Gabi G Dec 4 at 23:07
  • I like the direction you're going, of looking for a contradiction to the minimality of the counterexample :) But I think "the weight of $e'$ must be no less than the weight of $e_{p(T')+1}$" has problems: all we know about $e'$ is that it's not in $\{e_1, \dots, e_i\}$ -- we don't even know if it is equal to $e_j$ for some $j > i$. If we knew that adding $e'$ to $G_{p(T')+1}$ would result in no cycle, then we could infer things about its weight -- but AFAICT, we don't know this. – j_random_hacker Dec 5 at 0:08
  • My argument doesn't depend on there being duplicate weights. Even when weights are all distinct, we can't conclude that the weight of $e'$ must be no less than the weight of $e_{p(T')+1}$. – j_random_hacker Dec 5 at 0:41
  • @j_random_hacker, surely we can. Check my rephrased answer. – Apass.Jack Dec 5 at 6:23
  • The answer to the problem at the end is positive. If there is interest and I have time, I will write a full explanation. – Apass.Jack Dec 5 at 18:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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