Condition for an Edge to be a Bridge

Theorem

Let $G = \left({V, E}\right)$ be a connected graph.

Let $e \in E$ be an edge of $G$.

Then $e$ is a bridge iff $e$ does not lie on any circuit of $G$.

Proof

Necessary Condition

Let $e$ be a bridge of $G$.

Let $G \setminus e$ denote the set difference of $G$ with $e$, that is, $G$ with $e$ removed.

Suppose, in the hope of generating a contradiction, that $e = uv$ and $e$ lies on a circuit, say $C = \left({u, v, w, \ldots, x, u}\right)$.

Thus $G \setminus e$ contains a $u-v$ path, that is, $\left({v, x, \ldots, w, u}\right)$.

So $u$ is connected to $v$ in $G \setminus e$.

Now we need to show that $G \setminus e$ is connected.

Let $u_1, v_1 \in V$.

Since $G$ is connected, there is a $u_1-v_1$ path $P$ in $G$.

If $e \notin P$, then $P$ is also a path in $G \setminus e$ and $u_1$ is connected to $v_1$ in $G \setminus e$.

On the other hand, suppose $e \notin P$.

Then $P$ can be expressed as $\left({u_1, \ldots, u, v, \ldots, v_1}\right)$ or $\left({u_1, \ldots, v, u, \ldots, v_1}\right)$.

In the first case, $u_1$ is connected to $u$ and $v$ is connected to $v_1$ in $G \setminus e$.

In the second case, $u_1$ is connected to $v$ and $u$ is connected to $v_1$ in $G \setminus e$.

But we have already established that $u$ is connected to $v$ in $G \setminus e$.

But Graph Connectedness is an Equivalence Relation, and hence $u_1$ is connected to $v_1$.

So, if $e$ lies on a circuit, then $G \setminus e$ is connected.

This contradicts the stipulation that $e$ is a bridge.

Hence $e$ can not lie on a circuit.

Sufficient Condition

Let $e = uv$ be an edge which does not lie on a circuit of $G$.

Suppose, in the hope of generating a contradiction, that $e$ is not a bridge.

Then $G \setminus e$ is connected, and thus there is a $u-v$ path $P$ in $G \setminus e$.

But $P$ together with $e = uv$ produces a circuit containing $e$.

This contradicts the stipulation that $e$ does not lie on a circuit of $G$.

Hence $e$ is a bridge.

$\blacksquare$

Note

This result is usually given that:

$e$ is a bridge iff $e$ does not lie on any cycle of $G$.

As a cycle is by definition a circuit, the result as given in this entry is slightly stronger.

Sources

• Gary Chartrand: Introductory Graph Theory (1977): $\S 2.4$: Theorem $2.5$