Graph Bridge — Definition, Formula & Examples

A graph bridge is an edge in a connected graph that, if removed, causes the graph to become disconnected. In other words, it is the only path between some pair of vertices.

Given a connected graph $G = (V, E)$ , an edge $e \in E$ is a bridge if the graph $G' = (V, E \setminus \{e\})$ is disconnected. Equivalently, $e = \{u, v\}$ is a bridge if and only if $e$ does not lie on any cycle in $G$ .

How It Works

To determine whether an edge is a bridge, check if removing it splits the graph into two or more components. A practical method is to verify whether the edge belongs to any cycle: if it does not, it is a bridge. Tarjan's bridge-finding algorithm identifies all bridges in

O(|V| + |E|)

time using a depth-first search and tracking discovery times. In a tree, every edge is a bridge because trees contain no cycles.

Worked Example

Problem: Consider a graph with vertices

\{A, B, C, D\}

and edges

\{A{-}B,\ B{-}C,\ C{-}A,\ C{-}D\}

. Identify all bridges.

Step 1: Check edge

A{-}B

. Removing it leaves edges

\{B{-}C, C{-}A, C{-}D\}

. You can still reach

A

from

B

via

B \to C \to A

. The graph stays connected, so

A{-}B

is not a bridge.

Step 2: By the same reasoning,

B{-}C

and

C{-}A

each lie on the cycle

A{-}B{-}C{-}A

, so neither is a bridge.

Step 3: Check edge

C{-}D

. Removing it isolates vertex

D

from the rest of the graph because

C{-}D

is the only edge incident to

D

. This edge does not belong to any cycle.

Answer: The only bridge is edge

C{-}D

Why It Matters

Bridges identify critical links in networks — a single failed connection that can partition a communication or transportation network. Network reliability analysis, circuit design, and algorithms on biconnected components all depend on efficiently finding bridges.

Common Mistakes

Mistake: Confusing a bridge (an edge) with a cut vertex (a vertex whose removal disconnects the graph).

Correction: A bridge is always an edge, while a cut vertex is always a vertex. An endpoint of a bridge is not necessarily a cut vertex (for example, if it has degree 1).