Finding Minimum Spanning Tree (MST) in graph?

1
votes

Given an Undirected graph G with with weight on its edges and 2 different minimal spanning trees: 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)

1
algorithmgraphtreeminimum-spanning-treekruskals-algorithm
"the provided answer...": what are you referring to? – trincot
I am also confused that you (1) want to prove a statement, and (2) look for an algorithm. Those are 2 different things: the proof is not an algorithm. And if you have an algorithm (for finding e'), then this is not a proof. – trincot
@trincot why it's not a proof? if the algorithm works and I prove it it's a proof – user15874403
Well, you seem to put an unnecessary constraint on answers: the statement is a pure graph theory statement, which a mathematician will prove without ever needing to know about algorithms. It looks like an unnecessary long road to first come up with an algorithm, to then have to prove that the algorithm proves the statement. Just saying that an algorithm itself is not a proof. NB: Any clarification on my first comment? – trincot

1 Answers

1
votes

Let T1 and T2 be the two connected components of T \ {e}. Consider the path P joining the endpoints of e in T'. Since e connects T1 and T2, so does P, and therefore there exists an edge e' in P that connects T1 and T2. The edge e' cannot be lighter than e, or else T would not be minimum (T \ {e} U {e'}). The edge e' cannot be heavier than e, or else T' would not be minimum (T' \ {e'} U {e}).