Trees as minors

#tree#minor#contraction

Statement

Show that every connected graph contains a spanning tree.

Hint

Same as "spanning tree" in this category.

Show solutionHide solution

See "Spanning trees" in this category.

Conclusion. Every connected graph has a spanning tree.