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).
