Prove that an edge e is a bridge of G if and only if e lies

Prove that an edge e is a bridge of G if and only if e lies on no cycle of G.

Solution

Suppose that e = v1v2 is on a cycle, with vertices v1, v2, . . . , vK.

Any walk containing e can be replaced by a walk which uses v1, vK, . . . , v2 instead,

so if e is on a cycle, its removal will not change the number of connected components, that is e is not a bridge. Suppose that e = v1v2 is on no cycle.

Then v1 and v2, which are in the same component of G, are in different components of G e, since any path between them in G e allows us to build a cycle containing e. Thus e is a bridge.