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"].
