5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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'$ $\endgroup$
    – Gabi G
    Dec 4, 2018 at 18:44
  • $\begingroup$ And I need to formally prove that such thing cant happen $\endgroup$
    – Gabi G
    Dec 4, 2018 at 18:44

3 Answers 3

2
$\begingroup$

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)?
$\endgroup$
10
  • $\begingroup$ So $G_2$ will have a cycle $\endgroup$
    – Gabi G
    Dec 4, 2018 at 18:46
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Gabi G
    Dec 4, 2018 at 20:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gabi G
    Dec 4, 2018 at 20:49
  • 1
    $\begingroup$ @GabiG: Actually I think you almost have it already! Call the sub-forest of $T$ $F$, and the sub-forest of $T'$ $F'$. Instead of letting $u$ and $v$ be arbitrary vertices in different components $F$, require them to additionally be the endpoints of an edge in $F'$. This is always possible, since on any path in $F'$ beginning in one $F$-component and ending in a different $F$-component, there is at least one crossing edge with one endpoint in each $F$-component. By your step 5, there must be a path in $T$ between $u$ and $v$ with at least one edge of weight $> w'_i$; adding $uv$ => cycle! $\endgroup$ Dec 5, 2018 at 0:38
  • 2
    $\begingroup$ 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 $\endgroup$
    – Gabi G
    Dec 5, 2018 at 1:58
0
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ What is $G'_{p(T')}$? $\endgroup$
    – Gabi G
    Dec 4, 2018 at 23:07
  • $\begingroup$ 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. $\endgroup$ Dec 5, 2018 at 0:08
  • $\begingroup$ 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}$. $\endgroup$ Dec 5, 2018 at 0:41
  • $\begingroup$ @j_random_hacker, surely we can. Check my rephrased answer. $\endgroup$
    – John L.
    Dec 5, 2018 at 6:23
  • $\begingroup$ The other answer of mine indicates a way to do the exercise and solve the problem at the end of this answer. $\endgroup$
    – John L.
    May 20, 2020 at 22:31
0
$\begingroup$

Here is a very simple proof that is built on top of two results.

The replace-by-lighter-edge algorithm generates a minimum spanning tree (MST). Start with any spanning tree $H$ of $G$. Find the cycle in $H$ plus an edge $e$ not in $H$. If an edge $t$ in that cycle is heavier than $e$, remove $t$ from $H$ and add $e$ to $H$. Repeat until we cannot any more. Then $H$ is a MST of $G$.
This is proven in this answer.

All MSTs of $G$ have the same number of edges with any given weight.
This is a classic result proven in this answer.

For the sake of contradiction, suppose for some $i$: $w_i \gt w'_i$. Then the number of edges in $T'$ with length less than $w_i$ is at least $i$. Now apply the replace-by-lighter-edge algorithm on $T'$ so that the new $T'$ is an MST. Note that the number of edges in the new $T'$ with length less than $w_i$ is still at least $i$. However, since all MSTs have the same number of edges with any given weight, $T'$ and $T$ should have the same number of edges with length less than $w_i$, which is false. QED.

$\endgroup$

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.