K-vertex-connected graph


In graph theory, a connected graph G is said to be k-vertex-connected if it has more than k vertices 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.

Definitions

A graph has connectivity k if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them. Complete graphs are not included in this version of the definition since they cannot be disconnected by deleting vertices. The complete graph with n vertices has connectivity n − 1, as implied by the first definition.
An equivalent definition is that a graph with at least two vertices is k-connected if, for every pair of its vertices, it is possible to find k vertex-independent paths connecting these vertices; see Menger's theorem. This definition produces the same answer, n − 1, for the connectivity of the complete graph Kn.
A 1-connected graph is called connected; a 2-connected graph is called biconnected. A 3-connected graph is called triconnected.

Applications

Polyhedral combinatorics

The 1-skeleton of any k-dimensional convex polytope forms a k-vertex-connected graph. As a partial converse, Steinitz's theorem states that any 3-vertex-connected planar graph forms the skeleton of a convex polyhedron.
More generally, the 3-sphere regular cellulation conjecture claims that every 2-connected graph is the
one-dimensional skeleton of a regular CW-complex on the three-dimensional sphere.

Computational complexity

The vertex-connectivity of an input graph G can be computed in polynomial time in the following way consider all possible pairs of nonadjacent nodes to disconnect, using Menger's theorem to justify that the minimal-size separator for is the number of pairwise vertex-independent paths between them, encode the input by doubling each vertex as an edge to reduce to a computation of the number of pairwise edge-independent paths, and compute the maximum number of such paths by computing the maximum flow in the graph between and with capacity 1 to each edge, noting that a flow of in this graph corresponds, by the integral flow theorem, to pairwise edge-independent paths from to.