0
$\begingroup$

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.

Improve this question
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. That's what I suspected, but you're proof clears it all ;) $\endgroup$ – joaoaccarvalho Mar 26 '17 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.