biconnected

Biconnected, also called 2-vertex-connected, is a property of simple undirected graphs. A graph is biconnected if it is connected and remains connected after the removal of any single vertex. Equivalently, for every pair of vertices there exist two internally vertex-disjoint paths between them. This implies the graph has at least three vertices.

Biconnected components and blocks. A maximal subgraph that is biconnected is called a biconnected component or a block. A connected graph can be decomposed into blocks joined at articulation points (cut vertices). An articulation point is a vertex whose removal increases the number of connected components. A graph is biconnected exactly when it consists of a single block.

Examples and non-examples. Cycle graphs Cn with n at least 3 are biconnected, as removing any vertex leaves a path that remains connected. Complete graphs Kn for n ≥ 3 are biconnected because there are multiple vertex-disjoint routes between any two vertices. Trees and paths fail to be biconnected, since removing a central vertex often disconnects the graph and creates separate components.

Algorithms and recognition. A connected graph is biconnected if and only if it has no articulation points. This can be tested with a depth-first search (DFS) using discovery times and low values (Tarjan’s algorithm). A root of the DFS tree is an articulation point if it has more than one child. To extract biconnected components, one can maintain a stack of edges during DFS and, when a condition like low[v] ≥ disc[u] is met, pop edges to form a block. These methods yield both the presence of biconnectivity and the set of blocks.