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 \).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email