Question

If any edge from a spanning tree T0 is contained in some minimum spanning tree T*, does this imply that T0 is also a minimum spanning tree ?

Right now, I'm trying to draw on paper some graphs to prove that it doesn't. Please correct me if it does, or help me find an example if it doesn't.

Thanks in advance.

Was it helpful?

Solution

A triangle with edge weights 2,2,1.

EDIT:

There are three different spanning trees with costs 3 (1+2),3 (2+1) and 4 (2+2) in this graph. all the edges from the spanning tree with cost 4 are contained in one of the minimum spanning trees with cost 3, and it is NOT minimal.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top