Exercise 965Combinatorics › Graph theoryL1Added 3 Nov 2026

Spanning trees

#spanning tree#subgraph#connectivity

Statement

Show that every connected graph has a spanning tree.

Hint

Take a minimal connected spanning subgraph and show it is acyclic.

Show solutionHide solution

Existence. Consider the set of connected spanning subgraphs of $G$ (nonempty since $G$ connected). Pick one $T$ with minimum number of edges.

Acyclic. If $T$ had a cycle, remove an edge of the cycle: the graph stays connected with fewer edges, contradicting minimality.

Conclusion. $T$ is a spanning tree of $G$ .