A vertex cut, also called a vertex cut set or separating set (West 2000, p. 148), of a connected graph 
is a subset of the vertex set 
such that 
has more than one connected component. In other words, a
vertex cut is a subset of vertices of a connected
graph which, if removed (or "cut")--together with any incident edges--disconnects
the graph (i.e., forms a disconnected graph).
A vertex cut set of size 1 in a connected graph corresponds to an articulation vertex.
A vertex cut of smallest size in a given connected graph 
is called a minimum vertex
cut and can be found in the Wolfram
Language using the function FindVertexCut[G].
The size of a minimum vertex cut in a connected graph 
gives the vertex connectivity 
. However, because complete
graphs have no vertex cuts (i.e., there is no subset of vertices whose removal
disconnected a complete graph), a convention is
needed to assign them a vertex connectivity.
The convention of letting vertex connectivity 
for the complete
graph 
allows most general results about connectivity to remain valid on complete
graphs (West 2001, p. 149).
The number of vertex cuts in a connected graph 
with vertex
count 
is related to the number of connected (non-null) vertex-induced
subgraphs by
 |
For a not-necessarily-connected graph, a vertex cut of a graph 
is a vertex set 
such that 
has more connected components than 
(Gross and Yellen 2006, p. 81).
