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 (or $k$ -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. Or, equivalently (owing to Menger's theorem), a graph is $k$ -vertex-connected if any two of its vertices can be joined by $k$ independent paths (Diestel 2005, p. 55).

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.

The 1-skeleton of any $k$ -dimensional convex polytope forms a $k$ -vertex-connected graph (Balinski 1961). As a partial converse, Steinitz showed that any 3-vertex-connected planar graph forms the skeleton of a convex polyhedron.