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.