# Cut vertex
A **cut vertex** (also called an articulation point) is a vertex of a graph whose removal, together with all edges incident to it, increases the number of connected components of the graph[1](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.articulation_points.html). In a connected graph, removing a cut vertex disconnects the graph; in a graph that is not necessarily connected, the defining test is an increase in the component count[2](https://mathworld.wolfram.com/ArticulationVertex.html). The terms cut-vertex, cutpoint, and articulation point are used interchangeably in the literature[2](https://mathworld.wolfram.com/ArticulationVertex.html).
| Key fact | Detail |
|---|---|
| Definition | A vertex whose removal, along with all its incident edges, increases the number of connected components[1](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.articulation_points.html) |
| Biconnectivity | A graph on two or more vertices with no articulation vertices is called biconnected[1](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.articulation_points.html) • [2](https://mathworld.wolfram.com/ArticulationVertex.html) |
| Biconnected components | A vertex is a cut vertex if and only if it appears in more than one biconnected component[2](https://mathworld.wolfram.com/ArticulationVertex.html) • [3](https://544.graph.prtest3.cppalliance.org/libs/graph/doc/html/graph/algorithms/connected_components/biconnected_components.html) |
| Detection | A single depth-first search with discovery times and low-link values finds all cut vertices in O(V + E) time and O(V) space[4](https://learngraphtheory.org/algorithm/articulation-points) |
| Origin of the algorithm | Hopcroft and Tarjan, "Efficient algorithms for graph manipulation", Communications of the ACM 16: 372–378 (1973)[1](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.articulation_points.html) |
| Relation to bridges | The endpoints of a bridge are cut vertices unless both endpoints have degree 1; a non-bridge edge can still have both endpoints as cut vertices[2](https://mathworld.wolfram.com/ArticulationVertex.html) |
| Connectivity meaning | A connected graph with at least three vertices and no cut vertices has vertex connectivity at least 2[5](https://igraph.org/r/html/1.2.6/articulation_points.html) • [15](https://mathworld.wolfram.com/VertexConnectivity.html) |
## Definition and examples
For a connected graph G, a vertex v is a cut vertex when G − v, the induced subgraph obtained by deleting v and every edge incident to it, is disconnected[6](https://www.mauriciopoppe.com/notes/computer-science/data-structures/graphs/cut-vertices/). The more general formulation, which covers disconnected graphs as well, compares component counts: v is a cut vertex when c(G − v) > c(G)[7](https://www.ime.usp.br/~pf/graph-exercises/text/ETG.pdf).
The intuition is that cut vertices are not restricted to chains, as they can also lie on a cycle, such as the shared vertex of two cycles that meet only at that vertex[16](https://brain.tamnd.com/write/book/graph/05/46/). In a path-shaped tail attached to a cycle, every internal vertex of the tail and the cycle vertex where the tail attaches are cut vertices, while the other vertices of the cycle and the free endpoint of the tail are not[4](https://learngraphtheory.org/algorithm/articulation-points) • [16](https://brain.tamnd.com/write/book/graph/05/46/). A concrete library example: the NetworkX barbell graph `barbell_graph(4, 2)` has articulation points 6, 5, 4, and 3 and is not biconnected; adding the single edge (2, 8) makes the graph biconnected, and the list of articulation points becomes empty[1](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.articulation_points.html).
## Relation to bridges and biconnected components
A **bridge** is the edge analog of a cut vertex: an edge whose removal disconnects the graph[8](https://neelmishra.github.io/blog/dsa/graphs/bridges-articulation-points/articulation-points.html). The two notions are related but distinct. If a vertex v is incident with a bridge and has degree at least 2, then v is a cut vertex; if its degree is 1, it is an end-vertex and G − v remains connected[6](https://www.mauriciopoppe.com/notes/computer-science/data-structures/graphs/cut-vertices/). For a graph of order at least 3, the presence of a bridge implies the presence of a cut vertex[6](https://www.mauriciopoppe.com/notes/computer-science/data-structures/graphs/cut-vertices/). The converse direction fails: an articulation point does not necessarily lie on a bridge[8](https://neelmishra.github.io/blog/dsa/graphs/bridges-articulation-points/articulation-points.html), and a non-bridge edge can have both endpoints as articulation vertices[2](https://mathworld.wolfram.com/ArticulationVertex.html).
**Biconnected components** (blocks) are the maximal subgraphs that cannot be disconnected by removing a single vertex, with single-edge and isolated-node components handled as degenerate cases[9](https://algorithms.alexli.ca/articulation-points-biconnected-components-block-cut-forest/). Unlike connected components, vertices may belong to several biconnected components, while each edge belongs to exactly one[3](https://544.graph.prtest3.cppalliance.org/libs/graph/doc/html/graph/algorithms/connected_components/biconnected_components.html). The vertices shared between components are precisely the cut vertices[2](https://mathworld.wolfram.com/ArticulationVertex.html). This structure is summarized in the block-cut forest, a bipartite forest with one node for each biconnected component and one node for each articulation point, with an edge whenever an articulation point belongs to a component[9](https://algorithms.alexli.ca/articulation-points-biconnected-components-block-cut-forest/).
## Finding cut vertices
The standard algorithm runs a single depth-first search (DFS) and records two integers per vertex: the discovery time, the order in which the vertex is visited, and the low-link value, the earliest discovery time reachable from the vertex's subtree using back edges[4](https://learngraphtheory.org/algorithm/articulation-points) • [9](https://algorithms.alexli.ca/articulation-points-biconnected-components-block-cut-forest/). A back edge is an edge of the original graph that joins a vertex to an ancestor in the DFS tree without being part of the tree[10](https://www.baeldung.com/cs/graph-articulation-points).
The criterion can be stated as follows: n qualifies as an articulation point exactly when some subtree rooted at n has no back edge, from any of n's successors, connecting to a predecessor of n within the DFS tree[1](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.articulation_points.html). In low-link terms, a non-root vertex u is a cut vertex exactly when some child v satisfies low[v] ≥ disc[u], meaning v's subtree cannot reach above u[4](https://learngraphtheory.org/algorithm/articulation-points) • [9](https://algorithms.alexli.ca/articulation-points-biconnected-components-block-cut-forest/). The root of the DFS tree needs a separate rule: it is an articulation point if and only if it has more than one child in the tree[10](https://www.baeldung.com/cs/graph-articulation-points).
The same DFS also yields the biconnected components, because all edges of a component are traversed consecutively between articulation points; implementations typically collect component edges on a stack popped when a cut vertex is detected[1](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.articulation_points.html) • [9](https://algorithms.alexli.ca/articulation-points-biconnected-components-block-cut-forest/).
**Cost.** The algorithm costs the same as the traversal itself, O(V + E) time with O(V) extra space, since every vertex is visited once and every edge examined twice[4](https://learngraphtheory.org/algorithm/articulation-points). The naive alternative, deleting each vertex in turn and testing connectivity, costs O(V(V + E)), so the low-link method turns a quadratic check into a linear one[4](https://learngraphtheory.org/algorithm/articulation-points). The underlying linear-time framework for biconnected components goes back to Hopcroft and Tarjan's 1973 work on efficient graph manipulation algorithms[1](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.articulation_points.html).
## Applications and extensions
In a network, a cut vertex is a single point whose failure partitions the graph, so the presence of articulation points in a connected network indicates vulnerability to single-point failure[10](https://www.baeldung.com/cs/graph-articulation-points). If a router is an articulation point, losing it partitions the network[8](https://neelmishra.github.io/blog/dsa/graphs/bridges-articulation-points/articulation-points.html).
The concept connects to vertex connectivity, the size of a smallest vertex cut: a connected graph with at least three vertices and no articulation points has vertex connectivity at least 2[5](https://igraph.org/r/html/1.2.6/articulation_points.html) • [15](https://mathworld.wolfram.com/VertexConnectivity.html). An articulation point is the special case of a vertex cut containing a single vertex[11](https://u.cs.biu.ac.il/~agmon/RoiAAMAS15a.pdf).
Research has extended the basic notion in several directions. For directed graphs, a vertex w is a b-articulation point of a strongly biconnected directed graph G if G with w removed is not strongly biconnected[12](https://arxiv.org/abs/2007.01897). For measuring damage, the impact of an articulation point is defined as the number of vertices disconnected from the largest surviving connected component after its removal; a linear-time algorithm, O(m + n) for n vertices and m edges, computes the impact of all articulation points, improving on the naive O(a(m + n)) for a graph with a articulation points[13](https://arxiv.org/abs/1504.00341). Streaming-model algorithms have also been developed to characterize articulation points, bridges, and connected and biconnected components of undirected networks under stricter memory and per-item processing requirements[14](https://arxiv.org/abs/1202.0319).
## References
1. [articulation_points, NetworkX documentation](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.articulation_points.html)
2. [Articulation Vertex, Wolfram MathWorld](https://mathworld.wolfram.com/ArticulationVertex.html)
3. [biconnected_components / articulation_points, Boost.Graph Documentation](https://544.graph.prtest3.cppalliance.org/libs/graph/doc/html/graph/algorithms/connected_components/biconnected_components.html)
4. [Articulation Points Finder: Cut Vertices Online, learngraphtheory.org](https://learngraphtheory.org/algorithm/articulation-points)
5. [igraph R manual: articulation_points](https://igraph.org/r/html/1.2.6/articulation_points.html)
6. [Cut-vertices (articulation points) in Graph Theory, Mauricio Poppe](https://www.mauriciopoppe.com/notes/computer-science/data-structures/graphs/cut-vertices/)
7. [Graph Theory Exercises, Institute of Mathematics and Statistics, University of São Paulo](https://www.ime.usp.br/~pf/graph-exercises/text/ETG.pdf)
8. [Finding Articulation Points, Neel Mishra](https://neelmishra.github.io/blog/dsa/graphs/bridges-articulation-points/articulation-points.html)
9. [Articulation Points, Biconnected Components, Block-Cut Forest, algorithms.alexli.ca](https://algorithms.alexli.ca/articulation-points-biconnected-components-block-cut-forest/)
10. [Finding Articulation Points of a Graph, Baeldung on Computer Science](https://www.baeldung.com/cs/graph-articulation-points)
11. [Connectivity and articulation points in multi-agent network monitoring, Bar-Ilan University](https://u.cs.biu.ac.il/~agmon/RoiAAMAS15a.pdf)
12. [Jaberi, R. (2020). b-articulation points and b-bridges in strongly biconnected directed graphs. arXiv:2007.01897](https://arxiv.org/abs/2007.01897)
13. [A linear time algorithm to compute the impact of all the articulation points. arXiv:1504.00341](https://arxiv.org/abs/1504.00341)
14. [Real-Time Monitoring of Undirected Networks: Articulation Points, Bridges, and Connected and Biconnected Components. arXiv:1202.0319](https://arxiv.org/abs/1202.0319)
15. [Vertex Connectivity -- from Wolfram MathWorld](https://mathworld.wolfram.com/VertexConnectivity.html)
16. [Chapter 46. Vertex Connectivity, brain](https://brain.tamnd.com/write/book/graph/05/46/)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph theory overview and basic objects*
*Initially written Oct 15, 2026 · Edited: Oct 25, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license