0
$\begingroup$

Can anyone please help me out with my query: can disconnected graphs have minimum spanning trees?

$\endgroup$
1
  • 2
    $\begingroup$ Hint: what the word "spanning" stands for ? $\endgroup$
    – Optidad
    May 20, 2019 at 8:02

2 Answers 2

1
$\begingroup$

No, because by definition trees are connected. However, one might talk about spanning forests when referring to a collection of trees each of which is a spanning tree of some disconnected graph.

Wikipedia has some discussion on spanning forests and related definitions.

$\endgroup$
1
$\begingroup$

A spanning tree, by definition, has the same vertices as the graph it spans. Since such a tree is an induced subgraph and, since trees are (by definition) connected, the graph itself must be connected.

Note this applies to any spanning tree, not just a minimal one (i.e., an MST).

$\endgroup$

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.