k-vertex-connected graph

A graph (other than a complete 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.[1] 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 (Diestel 2005, p. 55). This definition produces the same answer, n − 1, for the connectivity of the complete graph K_n.[1]

A 1-connected graph is called connected; a 2-connected graph is called biconnected. A 3-connected graph is called triconnected.

The vertex-connectivity of an input graph G can be computed in polynomial time in the following way[3] consider all possible pairs ${\displaystyle (s,t)}$ of nonadjacent nodes to disconnect, using Menger's theorem to justify that the minimal-size separator for ${\displaystyle (s,t)}$ 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 ${\displaystyle s}$ and ${\displaystyle t}$ with capacity 1 to each edge, noting that a flow of ${\displaystyle k}$ in this graph corresponds, by the integral flow theorem, to ${\displaystyle k}$ pairwise edge-independent paths from ${\displaystyle s}$ to ${\displaystyle t}$.

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

• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.