KVertexConnectedGraph

A graph G on more than two vertices is said to be k-connected (or k-vertex connected, or k-point connected) if there does not exist a vertex cut of size k - 1 whose removal disconnects the graph, i.e., if the vertex connectivity κ(G)>=k. Therefore, a connected graph on more than one vertex is 1-connected and a biconnected graph on more than two vertices is 2-connected. The singleton graph is "annoyingly inconsistent" since it is connected (specifically, 1-connected), but by convention it is taken to have κ(K_1) = 0. The wheel graph is the "basic 3-connected graph". k-connectedness graph checking is implemented in the Wolfram Language as KVertexConnectedGraphQ[g, k].

Barnette's conjecture | biconnected graph | block | connected graph | disconnected graph | Harary graph | k-edge-connected graph | Menger's n-arc theorem | polyhedral graph | vertex connectivity | vertex cut