Articulation Points

Which vertex holds the network together?

A network can be connected yet depend on one vulnerable vertex. Remove that vertex and every edge touching it: if the number of connected components increases, the vertex is an articulation point, also called a cut vertex. The question concerns vertex failure, rather than which path is shortest or which edges form the cheapest spanning tree.

Count components before and after

Let k(G) be the number of connected components of an undirected graph. Write G − v for the graph after deleting vertex v and all its incident edges. The exact test is k(G − v) > k(G). This definition works even when G is already disconnected: a cut vertex splits its own component and increases the total. Removing an isolated vertex instead decreases the count by one.

Degree alone does not decide the answer. Every vertex of a triangle has two neighbors, but a route remains between the other two when one disappears. The center of a three-leaf star has no such alternative route; deleting it leaves three separate components.

Worked example: two cycles with one connection

Take six vertices and seven undirected edges: 0–1, 1–2, 0–2, 2–3, 3–4, 4–5 and 3–5. Vertices 0, 1 and 2 form one triangle; 3, 4 and 5 form another. The edge 2–3 joins them, so k(G) = 1. Enumerating the remaining components after each possible vertex failure gives an independent check.

Removed vertex	Remaining groups	k(G − v)	Increase
0	{1, 2, 3, 4, 5}	1	0
1	{0, 2, 3, 4, 5}	1	0
2	{0, 1}; {3, 4, 5}	2	1
3	{0, 1, 2}; {4, 5}	2	1
4	{0, 1, 2, 3, 5}	1	0
5	{0, 1, 2, 3, 4}	1	0

Exactly vertices 2 and 3 are articulation points. Add the edge 1–4: now deleting 2 still permits the route 0–1–4–3, and deleting 3 still permits 2–1–4–5. The other deletions also leave a connected graph. The articulation set becomes empty, although the number of vertices is unchanged.

Predict the DFS certificate

Start DFS at the smallest unvisited vertex, examine neighbors in ascending order, and number discoveries from zero. In the original example the DFS tree is 0–1–2–3–4–5; non-tree edges 2–0 and 5–3 provide return routes to ancestors. Discovery values are 0, 1, 2, 3, 4, 5. The final low values are 0, 0, 0, 3, 3, 3.

Vertex 5 returns first with low[5] = 3. Since 3 is below discovery[4] = 4, this child does not establish that 4 is a cut vertex.
Vertex 4 returns next with low[4] = 3. It cannot escape above its non-root parent 3, because low[4] = discovery[3]. Confirm cut vertex 3.
Vertex 3 returns with low[3] = 3, at least discovery[2] = 2. Confirm cut vertex 2.
The remaining returns are 2, 1 and 0. The first two have low value 0. Root 0 has only one DFS child, so it is not a cut vertex.

The full return order is 5, 4, 3, 2, 1, 0. At return step 2 the replay has confirmed only 3, while the separately labelled complete analysis already knows the final set 2, 3. These displays answer different questions.

Why low values reveal a failed connection

For a vertex v, low[v] is the smallest discovery number reachable from its DFS subtree by descending tree edges and then taking at most one back edge to an ancestor. Initialize low[v] to its own discovery number. An edge to an already visited non-parent neighbor can lower it to that neighbor's discovery number. A returned tree child w can lower it to low[w]. The parent edge is excluded because traversing the same undirected edge backward is not an alternative connection.

A non-root vertex u is an articulation point if some child v satisfies low[v] ≥ discovery[u]. Equality matters: reaching u itself does not provide a route around u after it is deleted. If every child subtree can reach a proper ancestor of u, those subtrees still have a way into the rest of the component.

A root has no parent side to separate from. Test it differently: it is a cut vertex exactly when it has more than one DFS child. These are children in the DFS tree, not all adjacent vertices. In a triangle the root has degree two but only one DFS child. A three-leaf star rooted at its center has three DFS children and really does split into three components.

Experiment: remove a vertex, then explain the split

Open the Articulation Points explorer. All inputs below are supported native controls. The complete graph analysis is immediate; the return replay separately reveals its DFS certificate.

Choose Joined cycles under Graph example. With Inspect vertex set to 2, predict the two remaining groups. Read one component before, two after, increase one and selected cut Yes.
Change Graph view to Vertex removed. The selected vertex is a dashed ghost, its incident edges disappear, and the remaining colors distinguish {0, 1} from {3, 4, 5}. The ghost is excluded from all counts.
Return to Original graph. Set DFS return step to 2, or press Next return twice. The active vertex is 4, replay low[4] and low[5] are 3, and only 3 has been confirmed so far. Other replay low entries remain Pending.
Press Finish returns. Confirm final low values 0, 0, 0, 3, 3, 3 and confirmed cuts 2, 3. Previous return reverses one reveal; Rewind returns clears the replay. Play returns advances automatically and Pause returns stops it.
Choose Add a bypass. One extra edge, 1–4, removes both cut vertices. Inspect vertex 2 again: the graph remains connected. Compare the two removal pictures rather than inferring reliability from degree alone.
Choose Star root and inspect 0. The increase is two because one component becomes three. Finish the replay: root 0 is confirmed only at its own return, after all three children have returned. Inspect leaf 1 instead; that leaf is not a cut vertex.
Choose Disconnected graph. Inspect 1: three original components become four, with only vertex 1 a cut vertex. The isolated vertex 6 is counted both before and after this removal. Inspect 6 instead: deleting the isolate reduces the total from three to two and does not make it an articulation point.
Edit Undirected edges to include a self-loop such as 1 1. An error replaces the graph and old results. Reset experiment restores the original seven edges and query. Use Inspect vertex or click a node to select it. Pan the background, use arrow keys or Home, and compare Reset view: navigation changes no graph result. Narrow tables scroll horizontally.

A bounded model of vertex failure

The explorer uses an unweighted, simple undirected graph with zero through eight vertices. It measures connectivity after one vertex failure, not traffic capacity, failure probability, edge reliability or a minimum vertex cut. Crossing drawn edges do not create extra vertices. A directed network requires different connectivity definitions.

The count is exactly one ASCII digit from 0 to 8. Each nonblank edge line has two one-digit IDs separated by spaces or tabs. Surrounding spaces and blank lines in the edge list are accepted; duplicates and reversed pairs count once. Self-loops are rejected. Invalid text stays in its field while all stale analysis is removed.
The empty graph has zero components and no selected vertex. Removing the sole vertex of a singleton changes one component to zero, so the increase is −1 and it is not a cut vertex. Two connected vertices and complete graphs also have no articulation point under this definition.
Disconnected graphs use a separate DFS root in each component. The root exception applies separately to every such tree. Vertices inside different components cannot provide alternative routes around a failure.
The core adjacency-list DFS takes O(V + E) time and O(V) auxiliary space. This small teaching model also sorts neighbors, snapshots returns, computes a selected deletion witness and draws the graph. These extra costs are separate from the linear core algorithm.
The replay shows completed returns, not every edge examination. Discovery, parents and DFS child counts describe the whole already computed forest; replay low entries become visible only when their vertex returns. The complete articulation set remains labelled as complete analysis throughout.
Results use exact small integer graph operations, without a numerical approximation or random sampling. Node positions and colors have no graph-theoretic meaning. The dense eight-vertex graph can have crossing edges; consult the explicit edge list and DFS table when a drawing is ambiguous.
Graph edits and presets rewind the return replay, stop playback and restore the view. Inspecting a different vertex or changing the displayed removal view does not change the graph. Resizing or changing display density preserves experiment state. Reset view restores only navigation.

Primary course reference

The definition, DFS low-value recurrence and root exception are supported by the course notes below. The six-vertex graph, bypass edit, removal table and native-control experiment are original independently calculated examples for this module.

Victor Adamchik, Carnegie Mellon CS 15-451, Lecture 8: Graph Algorithms, February 9, 2015, pages 4–8: articulation points, repeated vertex-deletion testing, DFS discovery and low values, non-root separation and the special root rule. Apply the connected-component argument independently to each DFS tree when the graph is disconnected.

Articulation Points