K-vertex-connected graph

From Wikipedia, the free encyclopedia

In graph theory, a graph $G$ with vertex set $V (G)$ is said to be $k$ -vertex-connected if $G \setminus X$ is connected for all $X \subseteq V(G)$ with $\left| X \right| < k$ . In plain english, a graph is $k$ -vertex-connected if the graph remains connected when you delete fewer than $k$ vertices from the graph.

A 1-vertex-connected graph is connected, while a 2-vertex-connected graph is said to be biconnected.

If a graph $G$ is $k$ -vertex-connected, and $k < | V (G) |$ , then $k \le \delta(G)$ , where $δ(G)$ is the minimum degree of any vertex $v \in V(G)$ . This fact is clear since deleting all neighbors of a vertex of minimum degree will disconnect that vertex from the rest of the graph.