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
ein T that's not in T', there is an edge
e'in T' that's not in T such that if we replace
e'in T (let's call it T_new) then it's still a minimal spanning tree of
I think I am too close for finding the right algorithm but stuck a little:
I have proved that
weight(e)must be exactly equal to
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)