# Chapter 49. Bridges and Articulation Points

# Chapter 49. Bridges and Articulation Points

Bridges and articulation points are the simplest local causes of disconnection in a graph.

A bridge is a single edge whose removal disconnects a graph. An articulation point is a single vertex whose removal disconnects a graph. These objects identify the places where a connected graph depends on one edge or one vertex to hold two regions together.

They are also called cut edges and cut vertices. These terms emphasize their role as minimal separators. A bridge is an edge cut of size \(1\). An articulation point is a vertex cut of size \(1\). Standard definitions state that a bridge is an edge whose deletion increases the number of connected components, and an articulation point is a vertex whose deletion increases the number of connected components.

## 49.1 Bridges

Let

$$
G=(V,E)
$$

be an undirected graph.

An edge \(e\in E\) is called a bridge if

$$
G-e
$$

has more connected components than \(G\).

If \(G\) is connected, then \(e\) is a bridge precisely when \(G-e\) is disconnected.

For example, in the path graph

$$
v_1v_2v_3v_4,
$$

every edge is a bridge. Removing any edge breaks the path into two smaller components.

In a cycle graph

$$
C_n,
$$

no edge is a bridge. Removing one edge leaves a path through all vertices, so the graph remains connected.

This contrast is fundamental. A path has no redundant route. A cycle has an alternate route around every edge.

## 49.2 Cut Edges and Cycles

An edge of a connected graph is a bridge if and only if it belongs to no cycle.

This gives the most useful structural test for bridges.

Suppose \(e=uv\) lies on a cycle. Then the rest of the cycle gives another path from \(u\) to \(v\). If \(e\) is removed, \(u\) and \(v\) remain connected through that alternate path. Therefore removing \(e\) cannot disconnect the graph.

Conversely, suppose \(e=uv\) lies on no cycle. If there were another path from \(u\) to \(v\), then that path together with \(e\) would form a cycle. Hence no such alternate path exists. Removing \(e\) separates \(u\) from \(v\), so \(e\) is a bridge.

Thus bridges are exactly the edges outside all cycles. This characterization is standard in graph theory.

## 49.3 Articulation Points

A vertex \(v\in V\) is called an articulation point if

$$
G-v
$$

has more connected components than \(G\).

The graph \(G-v\) is obtained by deleting \(v\) and all edges incident with \(v\).

If \(G\) is connected, then \(v\) is an articulation point precisely when deleting \(v\) disconnects the graph.

For example, in the path graph

$$
v_1v_2v_3v_4,
$$

the vertices \(v_2\) and \(v_3\) are articulation points. Removing \(v_2\) separates \(v_1\) from \(v_3\) and \(v_4\). Removing \(v_3\) separates \(v_4\) from \(v_1\) and \(v_2\).

The endpoints \(v_1\) and \(v_4\) are not articulation points. Removing an endpoint leaves a smaller connected path.

In a cycle graph \(C_n\), no vertex is an articulation point. Removing any one vertex leaves a path, and a path is connected.

## 49.4 Comparison

Bridges and articulation points measure different kinds of fragility.

| Object | Removed item | Effect |
|---|---|---|
| Bridge | One edge | Increases the number of connected components |
| Articulation point | One vertex | Increases the number of connected components |
| Edge connectivity \(1\) | Some bridge exists | One edge can disconnect the graph |
| Vertex connectivity \(1\) | Some articulation point exists | One vertex can disconnect the graph |

A graph may have articulation points but no bridges. For example, two cycles sharing a single vertex have no bridge, since every edge lies on a cycle. However, the shared vertex is an articulation point.

A graph may also have bridges whose endpoints behave differently. If a bridge is incident with a leaf, then the leaf endpoint is not an articulation point. The other endpoint may be an articulation point if it remains connected to the rest of the graph.

## 49.5 Trees

Trees provide the clearest examples.

Let \(T\) be a tree with at least two vertices. Every edge of \(T\) is a bridge.

This follows because a tree has exactly one path between any two vertices. If an edge is removed, there is no alternate path between its endpoints.

The articulation points of a tree are exactly the non-leaf vertices.

A leaf has degree \(1\). Removing a leaf does not disconnect the remaining tree. But removing a non-leaf vertex separates its incident branches into different components.

Thus, for a tree:

| Item | Condition |
|---|---|
| Edge | Every edge is a bridge |
| Vertex | A vertex is an articulation point exactly when it is not a leaf |

This reflects the absence of cycles in trees. Trees are connected with the fewest possible edges, so they have no edge redundancy.

## 49.6 Blocks and Local Robustness

Articulation points divide a graph into blocks.

A block is a maximal connected subgraph with no articulation point. Blocks are the parts of a graph that remain internally connected under deletion of a single vertex, subject to the convention used for small blocks.

If two cycles share one vertex, each cycle is a block. The shared vertex belongs to both blocks and is an articulation point of the whole graph.

This shows how local robustness and global fragility can coexist. Each cycle has no internal articulation point, but the graph as a whole depends on one shared vertex.

The block structure of a graph is often represented by a block-cut tree. In this tree, one type of node represents blocks and another type represents articulation points. An articulation point is adjacent to each block that contains it.

## 49.7 Bridges and 2-Edge-Connectivity

A connected graph is \(2\)-edge-connected if it has no bridge.

Equivalently, deleting any one edge leaves the graph connected.

This condition is weaker than \(2\)-vertex-connectivity. A graph can have no bridges but still have articulation points.

For example, two cycles sharing one vertex are \(2\)-edge-connected, because every edge lies on a cycle. But the shared vertex is an articulation point, so the graph is not \(2\)-vertex-connected.

This distinction is important:

| Property | Meaning |
|---|---|
| No bridges | No single edge failure disconnects the graph |
| No articulation points | No single vertex failure disconnects the graph |
| \(2\)-edge-connected | Robust against one edge deletion |
| \(2\)-vertex-connected | Robust against one vertex deletion |

Vertex robustness is usually stronger than edge robustness, because deleting a vertex also deletes all incident edges.

## 49.8 DFS Trees

Depth-first search gives an efficient way to find all bridges and articulation points.

Run DFS on an undirected graph. The traversal produces a DFS forest. In a connected graph, it produces a DFS tree.

Each vertex \(v\) receives a discovery time

$$
\operatorname{disc}(v).
$$

This is the time at which DFS first visits \(v\).

The algorithm also computes a low value

$$
\operatorname{low}(v).
$$

Informally, \(\operatorname{low}(v)\) is the earliest discovery time reachable from \(v\) or from a descendant of \(v\) using zero or more tree edges followed by at most one back edge. DFS low values are commonly used to detect both bridges and articulation points.

The low value records whether a subtree has an alternate connection back to an ancestor.

## 49.9 Bridge Criterion

Let \(uv\) be a tree edge in a DFS tree, where \(u\) is the parent of \(v\).

Then \(uv\) is a bridge if and only if

$$
\operatorname{low}(v) > \operatorname{disc}(u).
$$

The meaning is direct.

The subtree rooted at \(v\) cannot reach \(u\) or any ancestor of \(u\) by a back edge. Therefore the only connection between that subtree and the rest of the graph is the edge \(uv\). Removing \(uv\) disconnects the graph.

If

$$
\operatorname{low}(v) \le \operatorname{disc}(u),
$$

then the subtree rooted at \(v\) has a back edge to \(u\) or to an ancestor of \(u\). In that case, \(uv\) lies on a cycle and is not a bridge.

This criterion gives a linear-time bridge algorithm.

## 49.10 Articulation Point Criterion

The DFS criterion for articulation points has two cases.

First, suppose \(u\) is the root of a DFS tree. Then \(u\) is an articulation point if and only if it has at least two DFS children.

Indeed, two different DFS child subtrees of the root cannot be connected by a back edge. If they were connected, DFS would have discovered them in the same subtree. Removing the root separates these child subtrees.

Second, suppose \(u\) is not the root. Then \(u\) is an articulation point if it has a child \(v\) such that

$$
\operatorname{low}(v) \ge \operatorname{disc}(u).
$$

This condition means that the subtree rooted at \(v\) cannot reach any proper ancestor of \(u\) without passing through \(u\). Removing \(u\) therefore separates that subtree from the earlier part of the DFS tree.

The two standard rules are: a DFS root is an articulation point when it has more than one child; a non-root vertex is an articulation point when some child subtree has no back edge to an ancestor of that vertex.

## 49.11 Algorithm Outline

The following algorithm finds bridges and articulation points in an undirected graph.

1. Initialize all vertices as unvisited.
2. Run DFS from every unvisited vertex.
3. Assign each vertex a discovery time.
4. Compute low values during recursion.
5. For each DFS tree edge \(uv\), test whether

$$
\operatorname{low}(v) > \operatorname{disc}(u).
$$

If so, \(uv\) is a bridge.

6. For each vertex \(u\), test the articulation point rules:
   - if \(u\) is a DFS root, it must have at least two DFS children;
   - if \(u\) is not a root, it must have a child \(v\) with \(\operatorname{low}(v)\ge \operatorname{disc}(u)\).

The running time is

$$
O(|V|+|E|),
$$

because DFS examines every vertex and every edge a constant number of times.

## 49.12 Pseudocode

The following pseudocode gives the standard structure.

```text
time = 0

DFS(u, parent):
    visited[u] = true
    disc[u] = time
    low[u] = time
    time = time + 1
    child_count = 0

    for each neighbor v of u:
        if v is not visited:
            child_count = child_count + 1
            DFS(v, u)
            low[u] = min(low[u], low[v])

            if low[v] > disc[u]:
                report edge uv as a bridge

            if parent is not null and low[v] >= disc[u]:
                report u as an articulation point

        else if v != parent:
            low[u] = min(low[u], disc[v])

    if parent is null and child_count >= 2:
        report u as an articulation point
```

This algorithm assumes a simple undirected graph. In a multigraph, parent-edge handling must distinguish edge identities, not just parent vertices, because parallel edges can create alternate routes.

## 49.13 Example

Consider the graph with edges

$$
12,\ 23,\ 31,\ 34,\ 45,\ 56,\ 64.
$$

The vertices \(1,2,3\) form a triangle. The vertices \(4,5,6\) form a triangle. The edge \(34\) joins the two triangles.

The edge \(34\) is a bridge. It lies on no cycle. Removing it separates the first triangle from the second triangle.

The vertices \(3\) and \(4\) are articulation points. Removing \(3\) separates vertices \(1,2\) from vertices \(4,5,6\). Removing \(4\) separates vertices \(5,6\) from vertices \(1,2,3\).

No edge inside either triangle is a bridge, because each such edge lies on a cycle. No other vertex is an articulation point, because deleting it leaves the graph connected.

This example shows that bridges and articulation points often occur at narrow connections between cyclic regions.

## 49.14 Common Mistakes

One common mistake is to assume that every endpoint of a bridge is an articulation point. This fails when the endpoint is a leaf. Removing a leaf does not disconnect the remaining graph.

Another mistake is to assume that every articulation point is incident with a bridge. This is false. In two cycles sharing one vertex, the shared vertex is an articulation point, but the graph has no bridge.

A third mistake is to confuse bridges with edges of low degree. An edge incident with a high-degree vertex may still be a bridge if it is the only connection between two regions.

A fourth mistake is to apply the DFS bridge condition to all edges. The condition

$$
\operatorname{low}(v) > \operatorname{disc}(u)
$$

applies to DFS tree edges where \(u\) is the parent of \(v\).

## 49.15 Applications

Bridges and articulation points identify single points of failure.

| Setting | Bridge | Articulation point |
|---|---|---|
| Road network | Road whose closure separates regions | Junction whose closure separates regions |
| Communication network | Link whose failure disconnects machines | Router whose failure disconnects machines |
| Social network | Relationship connecting communities | Person connecting communities |
| Dependency graph | Required connection between modules | Module whose removal separates subsystems |
| Circuit graph | Wire whose removal breaks connectivity | Terminal whose removal breaks connectivity |

They are useful in reliability analysis because they identify failures with immediate global consequences.

However, they measure only single failures. A graph with no bridges and no articulation points may still be vulnerable to the removal of two edges or two vertices. Higher connectivity studies these stronger forms of robustness.

## 49.16 Summary

Bridges and articulation points are the one-element separators of graph theory.

| Concept | Meaning |
|---|---|
| Bridge | Edge whose deletion increases connected components |
| Articulation point | Vertex whose deletion increases connected components |
| Cut edge | Another name for bridge |
| Cut vertex | Another name for articulation point |
| Bridge criterion | A tree edge \(uv\) is a bridge when \(\operatorname{low}(v)>\operatorname{disc}(u)\) |
| Articulation criterion | A non-root vertex \(u\) is critical when some child \(v\) has \(\operatorname{low}(v)\ge \operatorname{disc}(u)\) |
| DFS root criterion | A root is critical when it has at least two DFS children |

Bridges reveal edges with no alternate route. Articulation points reveal vertices through which separate regions must pass. Together they provide the first algorithmic and structural test for local fragility in a connected graph.