# Must a min weight subset of edges connecting all vertices form a tree?

Got this question in an exam.

In a graph where all edge weights are positive, if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree?

True or false?

This seems to be the definition of a MST, but since it doesn't state anything about cycles I'm not 100% sure.

## 1 Answer

Claim : if a subset S of the edges connects all vertices and has minimum total weight, then the edges in S form a tree

True. It is the definition of MST on weighted (positive) graphs. Subset $S$ can't form a cycle due to minimum total weight condition.

You can prove this by contradiction, assume $S$ is a MST and forms a cycle, as all weights are positive, you can still remove a one edge $e$ from a cycle. $S -e$ is still going to be connect all the vertices of graph, but subset $S - e$ has total weight strictly less than the total weight of $S$, this is a contradiction to our assumption.

• Thank you. That's what I suspected, but you're proof clears it all ;) Commented Mar 26, 2017 at 11:29