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) for k < |V(G)| if is connected for all with . In plain English, a graph is k-connected if the graph remains connected when you delete fewer than k vertices from the graph.

In accordance with the definition, the complete graph K_n is (n-1)-connected for n≥2. As a special case that doesn't match the definition, K₁ is regarded as 1-connected.

An equivalent definition for graphs with two or more vertices 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).

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.

Except for the case of K₁, the connectivity of a graph cannot be greater than the minimum degree. This fact is clear for connectivity less than |V(G)|-1 since deleting all neighbors of a vertex of minimum degree will disconnect that vertex from the rest of the graph.

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)
• 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/ .

This combinatorics-related article is a stub. You can help Wikipedia by expanding it. v • d • e