The vertex connectivity of a graph , also called "point connectivity" or simply "connectivity," is the minimum size of a vertex cut, i.e., a vertex subset such that is disconnected or has only one vertex.
Because complete graphs have no vertex cuts (i.e., there is no subset of vertices whose removal disconnects them), a convention is needed to assign them a vertex connectivity. The convention of letting allows most general results about connectivity to remain valid on complete graphs (West 2001, p. 149). Though as noted by West (2001, p. 150), the singleton graph , "is annoyingly inconsistent" since it is connected, but for consistency in discussing connectivity, it is considered to have . The path graph is also problematic, since it has no articulation vertices and for the purpose of theorems such as those involving unit-distance graphs, it is convenient to regard it as biconnected, yet it has vertex connectivity of .
A graph with or on a single vertex is said to be connected, a graph with is said to be biconnected (as well as connected), and in general, a graph with vertex connectivity is said to be -connected. For example, the utility graph has vertex connectivity , so it is 1-, 2-, and 3-connected, but not 4-connected.
The vertex connectivity of a graph can be computed in polynomial time (Skiena 1990, p. 506; Pemmaraju and Skiena 2003, pp. 290-291).
Let be the edge connectivity of a graph and its minimum degree, then for any graph,
(Whitney 1932, Harary 1994, p. 43).
For a connected strongly regular graph or distance-regular graph with vertex degree , (A. E. Brouwer, pers. comm., Dec. 17, 2012).
The vertex connectivity of a graph can be determined in the Wolfram Language using VertexConnectivity[g]. Precomputed vertex connectivities are available for many named graphs via GraphData[graph, "VertexConnecitivity"].