k-vertex-connected graph

In graph theory, a graph G with vertex set V(G) is said to be k-vertex-connected (or k-connected) if the graph remains connected when you delete fewer than k vertices from the graph. Alternatively, a graph is k-connected if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them.

An equivalent definition for graphs that are not complete is that a graph is k-connected if any two of its vertices can be joined by k independent paths; see Menger's theorem (Diestel 2005, p. 55). However, for complete graphs the two definitions differ: the n-vertex complete graph has unbounded connectivity according to the definition based on deleting vertices, but connectivity n − 1 according to the definition based on independent paths, and some authors use alternative definitions according to which its connectivity is n..

A 1-vertex-connected graph is called connected, while a 2-vertex-connected graph is said to be biconnected.

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

The 1-skeleton of any k-dimensional convex polytope forms a k-vertex-connected graph (Balinski's theorem, Balinski 1961). As a partial converse, Steinitz's theorem states that any 3-vertex-connected planar graph forms the skeleton of a convex polyhedron.

See also

• k-edge-connected graph
• Connectivity (graph theory)
• Menger's theorem
• Structural cohesion

References

• Balinski, M. L. (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics 11 (2): 431–434, http://www.projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103037323 .
• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ .