k-vertex-connected graph

A k-vertex-connected graph is often called simply k-connected.

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

A k-vertex-connected graph is a graph in which removing fewer than 'k' vertices always leaves the remaining graph connected.

In a k-vertex-connected graph, and edge is said k-contractible if the contraction of the edge results in a k-connected graph.

Chvátal observed that the square of a k-vertex-connected graph is necessarily k-tough, and conjectured that 2-tough graphs are Hamiltonian.

A k-vertex-connected graph is a graph that cannot be partitioned into more than one component by the removal of fewer than k vertices, or equivalently a graph in which each pair of vertices can be connected by k vertex-disjoint paths.

Since these paths must leave the two vertices of the pair via disjoint edges, a k-vertex-connected graph must have degeneracy at least k. Concepts related to k-cores but based on vertex connectivity have been studied in social network theory under the name of structural cohesion.