Existence od a spanning tree
Task number: 4218
Show that each connected graph has a spanning tree.
Solution
By iduction by number of edges:
If \( G \) is a tree, it is a spanning tree.
If it is connected and not a tree, then it contains an edge \( e \) such that \( G-e \) is connected. According to the inductive hypothesis, \( G-e \) has a spanning tree, which is also a spanning tree of \( G \).
