Cut vertex

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (June 2008)

An undirected graph with n=5 vertices and n-2=3 cut vertices; the cut vertices (in red) are those not on either end

An undirected graph with no cut vertices

In mathematics and computer science, a cut vertex or articulation point is a vertex of a graph such that removal of the vertex causes an increase in the number of connected components. If the graph was connected before the removal of the vertex, it will be disconnected afterwards. Any connected graph with a cut vertex has a connectivity of 1.

While well-defined even for directed graphs, cut vertices are primarily used in undirected graphs. In general, a connected, undirected graph with n vertices can have no more than n-2 cut vertices. Naturally, a graph may have no cut vertices at all.

A bridge is an edge analogous to a cut vertex; that is, the removal of a bridge increases the number of connected components of the graph.

Finding Cut vertices

A trivial O(nm) algorithm is as follows:

C = empty set (at the end of the algorithm it will contain the cut vertices)
a = number of components in G (found using DFS/BFS)
for each i in V with incident edges
    b = number of components in G with i removed
    if b > a
        i is a cut vertex
        C = C + {i}
    endif
endfor

An algorithm with the much better running time O(n + m) is known using depth-first search.

Cut vertices in trees

A vertex v of a tree G is a cut vertex of G if and only if the degree of the vertex is greater than 1.

See also

• Cut edge
• Slides with presentation of the O(n+m) algorithm
• Connectivity (graph theory)

Cut verices are also defined for directed graphs ^[1]

Resources

• Wolfram Mathworld [1] "Cut-Vertex"

References

• Nirmala, K.; Ramachandra Rao, A. The number of cut vertices in a regular graph. (English), Cah. Cent. Étud. Rech. Opér. 17, 295-299 (1975).

This computer science article is a stub. You can help Wikipedia by expanding it. v • d • e

This combinatorics-related article is a stub. You can help Wikipedia by expanding it. v • d • e