4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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