k-vertex-connected graph

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

Some sources modify the definition of connectivity to handle this case, by defining it as the size of the smallest subset of vertices whose deletion results in either a disconnected graph or a single vertex.

For this variation, the connectivity of a complete graph

[2] 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 (Diestel 2005, p. 55).

This definition produces the same answer, n − 1, for the connectivity of the complete graph Kn.

A 3-connected graph is called triconnected.

Every graph decomposes into a disjoint union of 1-connected components.

1-connected graphs decompose into a tree of biconnected components.

2-connected graphs decompose into a tree of triconnected components.

The 1-skeleton of any k-dimensional convex polytope forms a k-vertex-connected graph (Balinski's theorem).

[3] As a partial converse, Steinitz's theorem states that any 3-vertex-connected planar graph forms the skeleton of a convex polyhedron.

The vertex-connectivity of an input graph G can be computed in polynomial time in the following way[4] 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

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

-connected graph is generated by its non-separating induced cycles.

disjoint paths for any sequences