A graph G has a spanning tree if and only if G is connected; from this it follows that to determine a spanning tree of a graph, the graph must be connected.

Question

Quizplus · Accepted Answer

A spanning tree of a graph G is a subgraph that includes all the vertices of G and is a tree. For a graph to have a spanning tree, it must be connected, because a tree is a connected graph without cycles. Therefore, to determine a spanning tree, the graph must indeed be connected.

A Graph G Has a Spanning Tree If and Only