Definition:Spanning Tree/Cutting-Down Method

From ProofWiki
Jump to navigation Jump to search

Definition

Start with the graph $G$.

Choose any cycle in $G$, and remove any one of its edges.

By Condition for Edge to be Bridge, this will not disconnect $G$.

Repeat this procedure till no cycles are left in $G$.