1
$\begingroup$

Given a graph G, if the graph is interconnected, possibly containing a cycle, who do we find a minimum spanning tree at all? Most texts I've seen don't seem to explain the reason at all. Why don't we find a subgraph in the graph possibly containing a cycle whose weight is minimized, possibly by removal of some edges?

$\endgroup$
3
$\begingroup$

If you want a connected spanning subgraph whose total edge weight is minimized, it will necessarily be a tree. Trees are precisely the minimally connected graphs: graphs that don't contain any edge you can remove and still have a connected graph.

If you don't need the subgraph to be connected, then the total edge weight is minimized by not taking any edges at all...

$\endgroup$
  • $\begingroup$ say for a 4 vertex graph, if I traverse in this ABCD graph, from A to D the cost is 10 and if from AtoBtoCtoD the cost is 20, so...... come to think of it you're right,it would be a tree, is there a mathematical proof for this?(just leaving my knowledge barier undeleted for those who could fall in the same pit) $\endgroup$ – mathmaniage May 25 at 13:16
  • 1
    $\begingroup$ Usually, a tree is defined as a connected graph with no cycles. As a result, if a connected spanning subgraph is not a tree, then it contains a cycle, and you can delete any edge of the cycle to reduce the weight. $\endgroup$ – Misha Lavrov May 25 at 13:43

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.