3
$\begingroup$

Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T'

Then I want to prove the following:

For every edge e in T that's not in T', there is an edge e' in T' that's not in T such that if we replace e with e' in T (let's call it T_new) then it's still a minimal spanning tree of G.

I think I am too close for finding the right algorithm but stuck a little:

  1. I have proved that weight(e) must be exactly equal to weight(e').

  2. Since T is a tree, deleting e will result in 2 separated components, then for T_new to be a tree it must use one of the edges connecting two vertices from those different components.

But, I wasn't able to know which edge e' exactly will work. Plus I wasn't able to prove that always there is such an edge (I just found some requirements for e' that is must satisfy).

Some notes: I know Kruskal algorithm, and familiar with an algorithm in which we can paint some edges in yellow and request it to generate minimal spanning trees with maximum yellow edges (In other words from all found minimal spanning trees return the one with maximum number of yellow edges)

$\endgroup$
6
  • 2
    $\begingroup$ It's funny because every spanning tree is minimal by definition. $\endgroup$
    – Pål GD
    May 9 '21 at 12:20
  • 2
    $\begingroup$ no? a tree is spanning, but not necessarily a minimal spanning tree $\endgroup$
    – nir shahar
    May 9 '21 at 12:29
  • 1
    $\begingroup$ take a look at this link for the definition: en.wikipedia.org/wiki/Minimum_spanning_tree $\endgroup$
    – nir shahar
    May 9 '21 at 12:30
  • 2
    $\begingroup$ @nirshahar "minimal" has a different meaning than "minimum". Pal GD is correct. A spanning tree is always minimal since it is spanning all nodes and is a tree. However, in old times the term "minimal spanning tree" was also used to signify "minimal spanning tree". And, it is still continuing now. (shrug) $\endgroup$ May 9 '21 at 17:03
  • 2
    $\begingroup$ Yes. Agreed. :). Edit in the previous comment: "However, in old times the term "minimal spanning tree" was also used to signify "minimum spanning tree". $\endgroup$ May 9 '21 at 17:08
6
$\begingroup$

Here is a proof. Let $V$ be the vertices of $G$. $V$ are also the vertices of $T$ and the vertices of $T'$.

If $e$ is deleted from $T$, we will get two trees. Let the vertices of these two trees be $(V_1, V_2)$, which is a cut of $V$.

Since $T'$ is a tree, if we add $e$ to it, we will obtain a cycle. Since that cycle crosses $(V_1, V_2)$ at $e$, it must cross $(V_1, V_2)$ at another edge, say, $e'\in T'$.

  • Since $T \setminus \{e\}\cup \{e'\}$ is a spanning tree of $G$ and $T$ is an MST, $\text{weight}(e) \le \text{weight}(e')$.
  • Since $T' \setminus \{e'\}\cup \{e\}$ is a spanning tree of $G$ and $T'$ is an MST, $\text{weight}(e') \le \text{weight}(e)$.

So, $\text{weight}(e) = \text{weight}(e')$.

$T \setminus \{e\}\cup \{e'\}$, which is a spanning tree of the same weight as $T$, must be an MST of $G$. $\quad\checkmark$

$\endgroup$
11
  • $\begingroup$ What we have proved is, in fact, that for every cut $C$ and every MST $T$ of $G$, $T$ must contain at least one edge of minimum weight in the cut-set of $C$. $\endgroup$
    – John L.
    May 23 '21 at 15:59
  • $\begingroup$ If you can kindly help me prove that: "The edge e' cannot be heavier than e, or else T' would not be minimum (T' \ {e'} U {e})" From: stackoverflow.com/questions/67456739/…? $\endgroup$ May 23 '21 at 17:59
  • $\begingroup$ You made a mistake claiming: Since 𝑇′∖{𝑒′}∪{𝑒} T ′ ∖ { e ′ } ∪ { e } is a spanning tree of 𝐺 G. Please read my counter example here: cs.stackexchange.com/questions/140652/… In case you delete e' and replace it with e you will get a circle which contradicts the definition of tree. $\endgroup$ May 23 '21 at 18:33
  • $\begingroup$ The $e'$ in my proof is not an arbitrary edge that cross the cut. It is the very edge in $T'$ in your counterexample which together with $e$ forms the circle you mentioned. Please check again how $e'$ is selected. In particular, $e'$ is part of "that cycle". $\endgroup$
    – John L.
    May 23 '21 at 18:45
  • $\begingroup$ Got you, so his answer is wrong too. Can't upvote you I need 15 rep points $\endgroup$ May 23 '21 at 19:32
-1
$\begingroup$

Add an edge to a spanning tree and you have a cycle. Deleting any edge in that cycle results in a new spanning tree.

$\endgroup$
1
  • $\begingroup$ it doesn't prove its a minimal spanning tree $\endgroup$
    – nir shahar
    May 9 '21 at 12:29

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.