k-vertex-connected graph

Summary

A graph is $k$-vertex-connected, or $k$-connected, if it has more than $k$ vertices and stays connected after the removal of any fewer than $k$ vertices. The largest such $k$ is the vertex connectivity $\kappa(G)$, a measure of how robust a network is against the failure of nodes. Menger's theorem gives another view. A graph with more than $k$ vertices is $k$-connected if and only if every two vertices are joined by $k$ internally disjoint paths. The node k-vertex-connected graph gives the precise definition.