**Figure:** An articulation vertex is the weakest point in the graph

Suppose you are a terrorist seeking to disrupt the telephone network.
Which station in Figure should you choose to blow up
to cause the maximum amount of damage?
An *articulation vertex* is a vertex of a connected graph
whose deletion disconnects the graph.
Any graph that contains an articulation vertex is inherently fragile,
because deleting that single vertex causes a loss of connectivity.

In general, the *connectivity* of a graph is the smallest number of
vertices whose deletion will disconnect the graph.
For graphs with an articulation vertex, the connectivity is one.
Connectivity is an important measure of robustness
in network design, as discussed
in catalog Section .

A simple application of either depth-first or breadth-first search suffices
to find all the articulation vertices in a graph in *O*(*n* (*m*+*n*)).
For each vertex *v*, delete it and then
do a BFS traversal of the remaining graph
to establish whether it is still connected.
In fact, there is a clever *O*(*n*+*m*) algorithm that tests all the vertices
using only a single depth-first search.
Additional information on edge and vertex connectivity testing appears in
Section .

Mon Jun 2 23:33:50 EDT 1997