A Bridge, also called a Cut Edge, is an edge in an undirected graph whose removal increases the number of connected components.

In practical terms, it is a critical connection: if that link fails, part of the network becomes separated from the rest.

Example

A -- B -- C
     |
     D

Every edge in this graph is a bridge.

Removing A -- B, for example, isolates A.

Bridge vs Articulation Point

A bridge is a critical edge.

An articulation point is a critical vertex.

Bridge             → remove edge
Articulation Point → remove vertex

Brute force

A simple method removes every edge one at a time and recomputes connectivity.

That can cost:

O(E × (V + E))

Tarjan-style DFS finds all bridges in linear time.

Discovery and low-link values

For each vertex u:

disc[u]

records when DFS first discovers it.

low[u]

is the earliest discovery time reachable from u's DFS subtree through tree edges and a back edge.

Low-link values capture whether a subtree has an alternate route back toward earlier ancestors.

Bridge condition

For a DFS tree edge:

u → v

if:

low[v] > disc[u]

then:

(u, v) is a bridge

The subtree rooted at v cannot reach u or any ancestor of u without using that edge.

Why the condition uses >

For bridges:

low[v] > disc[u]

For non-root articulation points:

low[v] >= disc[u]

If low[v] == disc[u], the subtree can return to u through another edge, so (u,v) is not a bridge.

JavaScript implementation

function findBridges(graph) {
  const nodes = new Set();

  for (const [u, neighbors] of Object.entries(graph)) {
    nodes.add(u);

    for (const v of neighbors) {
      nodes.add(v);
    }
  }

  const visited = new Set();
  const disc = new Map();
  const low = new Map();
  const parent = new Map();

  const bridges = [];

  let time = 0;

  function dfs(u) {
    visited.add(u);

    disc.set(u, ++time);
    low.set(u, disc.get(u));

    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        parent.set(v, u);

        dfs(v);

        low.set(
          u,
          Math.min(low.get(u), low.get(v))
        );

        if (low.get(v) > disc.get(u)) {
          bridges.push([u, v]);
        }
      } else if (v !== parent.get(u)) {
        low.set(
          u,
          Math.min(low.get(u), disc.get(v))
        );
      }
    }
  }

  for (const node of nodes) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return bridges;
}

Bridges and cycles

A fundamental theorem for undirected graphs is:

an edge is a bridge
iff
it belongs to no cycle

If an edge belongs to a cycle, another route exists between its endpoints.

Trees

Every edge in a tree is a bridge because trees have no cycles.

Complete graphs

A complete graph with at least three vertices has no bridges because many alternate paths exist.

Graph with a cycle and tail

A -- B
|    |
D -- C -- E -- F

The cycle edges are not bridges.

C -- E and E -- F are bridges.

Parent-edge handling

In an undirected adjacency list, traversing A -- B means that B naturally sees A as a neighbor.

That parent edge must not be treated as a back edge.

Multigraph caveat

If parallel edges exist between the same pair of vertices, tracking only the parent vertex is insufficient.

Use unique edge IDs and track the parent edge, not only the parent vertex.

2-edge-connected graphs

A connected undirected graph with no bridges is 2-edge-connected.

Removing any single edge does not disconnect it.

2-edge-connected components

Removing all bridges decomposes the graph into maximal regions that contain no bridge internally.

These are 2-edge-connected components.

Bridge tree

Compress each 2-edge-connected component into a single node and keep the bridges between them.

For a connected graph, the resulting structure is a tree, often called a Bridge Tree.

This representation is useful for structural connectivity queries.

Real-world applications

Computer networks

Routers or switches are vertices and links are edges.

Bridges reveal links whose failure partitions the network.

Data centers

A single inter-zone link may be a bridge and therefore a candidate for redundancy.

Transportation

Roads or rail links that provide the only connection between regions are structural bridges.

Telecom networks

Fiber connections can be analyzed for single-link failure risk.

Infrastructure

Bridges provide a first-order structural reliability measure for many network models.

Modeling caveat

Real systems may involve direction, capacity, failover, probabilistic failures, traffic engineering, and other constraints.

Graph bridges reflect structural connectivity only.

Bridges and MST

Every bridge in a connected graph must appear in every spanning tree.

However, not every edge of an MST is a bridge in the original graph.

An MST is itself a tree, but the original graph may contain alternative paths.

Self-loops

A self-loop is not a bridge because its removal does not disconnect distinct vertices.

Complexity

With adjacency lists:

Time:  O(V + E)
Space: O(V)

TypeScript

type Graph = Record<string, string[]>;

function findBridges(
  graph: Graph
): Array<[string, string]> {
  const nodes = new Set<string>();

  for (const [u, neighbors] of Object.entries(graph)) {
    nodes.add(u);

    for (const v of neighbors) {
      nodes.add(v);
    }
  }

  const visited = new Set<string>();
  const disc = new Map<string, number>();
  const low = new Map<string, number>();
  const parent = new Map<string, string>();

  const bridges: Array<[string, string]> = [];

  let time = 0;

  function dfs(u: string): void {
    visited.add(u);

    disc.set(u, ++time);
    low.set(u, disc.get(u)!);

    for (const v of graph[u] ?? []) {
      if (!visited.has(v)) {
        parent.set(v, u);

        dfs(v);

        low.set(
          u,
          Math.min(low.get(u)!, low.get(v)!)
        );

        if (low.get(v)! > disc.get(u)!) {
          bridges.push([u, v]);
        }
      } else if (v !== parent.get(u)) {
        low.set(
          u,
          Math.min(low.get(u)!, disc.get(v)!)
        );
      }
    }
  }

  for (const node of nodes) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return bridges;
}

Common mistakes

• using >= instead of > for the bridge condition,
• treating the parent edge as a back edge,
• running DFS from only one connected component,
• applying the undirected algorithm directly to directed graphs,
• ignoring parallel edges,
• assuming low degree automatically means bridge,
• forgetting destination-only vertices,
• ignoring recursion depth on very deep graphs.

Summary

A bridge is an edge whose removal increases the number of connected components.

Tarjan-style DFS uses:

disc[u]
low[u]

For a DFS tree edge (u,v):

low[v] > disc[u]

means the edge is a bridge.

The algorithm runs in:

O(V + E)

The most useful intuition is:

edge belongs to a cycle
→ not a bridge

edge belongs to no cycle
→ bridge

This makes bridge detection a fundamental tool for network reliability and redundancy analysis.