Number of Components after Removal of Bridge

Theorem

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

Let $e \in E$ be a bridge.

Let $m$ be the number of components of $G$.

Then when $e$ is removed from $G$, the number of components in the remaining graph is $m+1$.

Proof

It is clear that, by definition of a bridge that removing $e$ increases the number of components.

So after $e$ is removed from $G$, the number of components in the remaining graph is at least $m+1$.

Suppose that removing $e$ disconnects $G$ into more than $m+1$ components.

Since $e$ joins only two vertices of $G$, it can link at most two of these components.

So there is at least one extra component when $e$ is put back into $G$, and so $G$ has more than $m$ components.

This contradicts the fact that $G$ has $m$ components.

Hence the result.

$\blacksquare$