Spanning forest contains all bridges

Dependencies:

1. Bridge in graph
2. Spanning forest

Let $G$ be an undirected graph. Every spanning forest of $G$ contains all the bridges in $G$.

Proof

We will prove this theorem for a special case, where $G$ is connected. Then applying this theorem to each connected component of $G$ will prove the general form of the theorem.

Let $(u, v)$ be a bridge in $G$ and $T$ be a spanning tree of $G$ such that $(u, v) \not\in T$.

Since there is a unique simple path between any 2 vertices in a tree, there is a path $p$ from $u$ to $v$ in $T$.

Therefore, there are 2 paths from $u$ to $v$ in $G$: $[u, v]$ and $p$. Deleting $(u, v)$ will not disconnect any vertices in $G$, since any path through $(u, v)$ can be re-routed through $p$. This is a contradiction, since $(u, v)$ is a bridge, which means that deleting it disconnects $G$.

Therefore, it is not possible for a bridge to not belong to a spanning tree.

Dependency for: None

Info:

• Depth: 5
• Number of transitive dependencies: 10

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Path in Graph
6. Tree
7. Spanning tree
8. Forest
9. Spanning forest
10. Bridge in graph