Given a graph with distinct edge weights and a not-minimum ST, there always exist another ST of lesser total weight that differs only by one edge

Question

I have to show that, if all the edge weights of a graph are distinct, given a spanning tree $T$ that is not a MST, there always exist a spanning tree $T'$ of lesser total weight, s.t. $T'$ differs from $T$ only by one edge.

I started reasoning from this question, but it's not helpful for my case and I cannot go over.

Answer 1

Actually that question (in particular this answer) is helpful.

A proof using cycle property:

Let $G=(V,E)$ be the original graph. Let the set of edges $T \subseteq E$ be a spanning tree on $G$ that is not minimum.

Now, there will exist an edge $e$ which belongs to the MST and not to $T$.

Adding $e$ it to $T$ creates a cycle. By cycle property, the most expensive edge of this cycle (call it $e'$) does not belong to the MST, so it must belong to $T$.

Removing $e'$ we break the cycle and we obtain a new subgraph $T'$ with lesser total weight than $T$. Furthermore, $T'$ is a spanning tree because:

• It doesn't have cycles: we broke the cycle removing $e'$.
• It is connected: creating and breaking a cycle cannot affect connectivity.
• It covers all the vertices of $G$: the two vertices of the removed edge $e'$ are still covered by the adjacent edges of $e'$.

So there must exist a spanning tree of lesser total weight, s.t. it differs from $T$ only by one edge.

Answer 2

Consider a spanning tree $E$ and label its edges $e_1$, $\ldots$,$e_n$. Consider now a spanning tree $F$. Then there exists a labeling of the edges of $F$ $\ $ $f_1$, $\ldots$, $f_n$ so that the following are still spanning trees (use an exchange lemma like for two bases of a vector space):

$$(e_1, e_2, \ldots, e_{n-1},e_n) \\ (e_1, e_2, \ldots, e_{n-1},f_n)\\ (e_1, e_2, \ldots, f_{n-1}, f_n)\\ \ldots \\ (e_1, f_2, \ldots, f_{n-1}, f_n)\\ (f_1, f_2, \ldots, f_{n-1}, f_n)$$

Assume now that $E$ is obtained using the greedy algorithm: $e_1$ is of minimal weight, $e_2$ is of minimal weight so that $e_1$, $e_2$ form no cycles, $e_3$ is of minimal weight so that $e_1$, $e_2$, $e_3$ form no cycles, and so on, up to $e_n$. From the above we conclude that $w(e_i) \le w(f_i)$ for all $i$. Since $F$ is arbitrary we conclude that $E$ is a minimal tree.

Now assume that $F$ itself is not a minimal tree. Then for some $i$ we have a strict inequality $w(e_i) < w(f_i)$. Let $i$ the smallest index for which this happens. Let's assume now that all the edges have different weights. Then we have $e_1= f_1$, $\ldots$,$e_{i-1} =f_{i-1}$. Hence the tree $(e_1, \ldots, e_{i-1}, f_{i}, \ldots, f_n)$ is $F$ and the tree $(e_1, \ldots, e_{i-1}, e_i, f_{i+1}, \ldots, f_n)$ is obtained from it by exchanging the edge $e_i$ with an edge of larger weight $f_i$.

Answer 3

This is true even if not all the edge weights are distinct. Define

$$ w'(e) = \begin{cases} 2 \cdot w(e) &\text{ if } e \text{ belongs to } T \\ 2 \cdot w(e) + 1 & \text{otherwise}\end{cases} $$

then sort all the edges according to $w'$ (rather than $w$). Observe that it produces the same ordering as sorting according to $w$ only that it prioritizes edges of $T$ if possible. Now run the Kruskal's algorithm using that new ordering and denote by $e$ the first edge not in $T$ that was chosen by the algorithm.

Let $e'$ be the heaviest edge on the cycle created by $e$ in $T \cup \{e\}$. Observe that $e$ does not create a cycle with edges of strictly smaller $w'$, otherwise it would not be chosen by the algorithm. Thus $w'(e) \leq w'(e')$, and so $w(e) < w'(e')$, because $e$ is not in $T$ while $e'$ is. Therefore we can set $T' = T \setminus \{e'\} \cup \{e\}$.

I hope this helps $\ddot\smile$