Is it right : all edge weights are positive, then any that connects all vertices and has minimum total weight must be a minimum spanning tree?

Question

This problem is evolved from the exercise 23.1-7 of introduction to algorithms.

The original problem is:

23.1-7 Argue that if all edge weights of a graph are positive, then any subset of edges that connects all vertices and has minimum total weight must be a tree. Give an example to show that the same conclusion does not follow if we allow some weights to be nonpositive.

But I think if all edges weights of a graph are positive, then any subset of edges that connects all vertices and has a minimum total weight must be a minimum spanning tree.

Is my corollary right ? If not, please give me a counterexample.

Answer 1

I think your corollary is equivalent to the statement that you are asked to prove. A spanning tree is a subset of edges such that all vertices are connected without any cycles (so it's a tree). If it's a minimum spanning tree, then the total weight of the edges is minimized.

So yes, your corollary is correct, but you haven't proved the statement. Hint: a tree doesn't contain any cycles, so try to make a proof by contradiction by assuming that you have a subset connecting all vertices with minimum total weight that has a cycle.