Minimum spanning trees of sub-graphs?

97 Views Asked by At

Any hint please if I should prove or search for counterexample, at least to know which direction to go...

Consider the following 2 graphs:

G1 (V, E1)
G2 (V, E2)

and a weight function for the vertices w: (E1 \untion E2) -> R

and 2 minimum spanning trees T1, T2 of G1 and G1.

We define a new graph: G(V, E1 \untion E2)

Is it true to say that there is always a minimum spanning tree T in the new graph G (using same w function) such that all edges of T are from T1 or T2?


The claim is wrong in case for every T it has an edge e which isn't included in T1 or T2, Now in G1 we can remove this edge (e) and the problem is solved for T1. But I can't remove edge e from G2 too, which means I must take it and the claim is right, am I wrong?

Note: no need for detailed answer, only looking to know what is correct and giving it myself a deep prove and thinking.

0

There are 0 best solutions below