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.

$\endgroup$

1 Answer 1

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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