Vertex connectivity

In graph theory, a connected graphG is said to be k-vertex-connected (or k-connected) if it has more than kvertices and remains connected whenever fewer than k vertices are removed.

The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected.