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.
