4.1. Vertex-cut and vertex-connectivity
Let W be a set of
vertices. If G is connected and is disconnected, then we say that W separates G, or that W is a vertex-cut.
If in
two vertices s and t belong to
different components then W separates
s from t.
A graph G is k-vertex-connected if
- G is either
.
- or G
has at least
vertices and no set of
vertices separate G.
A connected graph is also said to be 1-connected.
We give two equivalent definitions for k-vertex-connectivity:
- The maximal value of k for which a connected graph G
is k-vertex-connected is the vertex-connectivity of G,
denoted by
. If G is disconnected, we put
.
- The vertex-connectivity -
- of a graph G is the minimum cardinality of a vertex-cut if G is not complete, and it is
if
for some positive integer n.

Statement 4.1. If a graph G is k-vertex-connected then .
Examples:
- A nontrivial graph has vertex-connectivity 0 iff it is disconnected.
- A graph G has vertex-connectivity 1 iff
or G is connected with cut-vertices.