Graph Theory37 sections · 1633 units
Open in Course

Why Back Edges Prevent Bridges

Cycles provide alternate paths

A back edge creates a cycle. Any edge in a cycle has an alternate path around the cycle. If tree edge (u,v)(u, v) has a back edge from the subtree of vv to an ancestor of uu, then (u,v)(u, v) is not a bridge.

The back edge provides an alternate route. If no such back edge exists, (u,v)(u, v) is a bridge. Removing it disconnects the subtree of vv from the rest of the graph. The subtree has no escape route.