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

be an undirected graph.

An edge $e\in E$ is called a bridge if

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

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

In a cycle graph

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

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

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.

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:

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:

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

This is the time at which DFS first visits $v$.

The algorithm also computes a low value

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

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

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

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

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

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

49.12 Pseudocode

The following pseudocode gives the standard structure.

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

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

applies to DFS tree edges where $u$ is the parent of $v$.

49.15 Applications

Bridges and articulation points identify single points of failure.

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.

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.