Bridges in a spanning tree

Task number: 4219

Show that each spanning tree contains all the bridges, i.e. the edges whose removal makes the graph disconnected.

  • Solution

    If there was a bridge \( e \) and a spanning tree \( K \) such that \( e \notin K \), then by adding \( e \) to \( K \) creates a cycle.

    Subsequently, even after removing \( e \), the graph would remain connected, which is a contradiction with the fact that \( e \) is a bridge.

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