4
$\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)

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ It's funny because every spanning tree is minimal by definition. $\endgroup$
    – John K.
    Commented May 9, 2021 at 12:20
  • 2
    $\begingroup$ no? a tree is spanning, but not necessarily a minimal spanning tree $\endgroup$
    – nir shahar
    Commented May 9, 2021 at 12:29
  • 1
    $\begingroup$ take a look at this link for the definition: en.wikipedia.org/wiki/Minimum_spanning_tree $\endgroup$
    – nir shahar
    Commented May 9, 2021 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$
    – Inuyasha Yagami
    Commented May 9, 2021 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$
    – Inuyasha Yagami
    Commented May 9, 2021 at 17:08

2 Answers 2

Reset to default
7
$\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$

Improve this answer
$\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.
    Commented May 23, 2021 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$
    – sup_user136396
    Commented May 23, 2021 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$
    – sup_user136396
    Commented May 23, 2021 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.
    Commented May 23, 2021 at 18:45
  • $\begingroup$ Got you, so his answer is wrong too. Can't upvote you I need 15 rep points $\endgroup$
    – sup_user136396
    Commented May 23, 2021 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ it doesn't prove its a minimal spanning tree $\endgroup$
    – nir shahar
    Commented May 9, 2021 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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