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.