Prove that minimum spanning tree is a tree

546 Views Asked by At

From the the Wikipedia page Minimum spanning tree:

A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges.

Let G be a connected, undirected graph, and let H be a connected subgraph of G such that "it connects all the vertices together with the minimal total weighting for its edges". How do I prove that H is a tree?

It's pretty easy if you think about it, if H is not a tree it will have one or more "useless" edges and those could be removed, resulting in a tree with a smaller total weighting for its edges. I can't find a way to write this down formally though.

1

There are 1 best solutions below

3
On BEST ANSWER

You just need to make an argument that if $H$ is not a tree then $H$ contains a cycle, therefore there is an edge that can be removed without disconnecting $H$. This contradicts the assumption that $H$ has minimal edge weight.