kconnected

In graph theory, k-connected (or k-vertex-connected) is a graph property that describes a graph’s robustness to vertex removal. A graph G is k-connected if it has at least k+1 vertices and remains connected whenever fewer than k vertices are removed. Equivalently, for every pair of vertices in G there exist at least k internally vertex-disjoint paths between them, a statement guaranteed by Menger’s theorem.

Consequences of this definition include that the vertex-connectivity κ(G) of G is at least k, and the minimum degree δ(G) is at least k (since κ(G) ≤ δ(G)). Therefore, every k-connected graph has a minimum degree of at least k and cannot be disconnected by removing any set of fewer than k vertices.

Examples help illustrate the concept. The cycle graph C_n for n ≥ 3 is 2-connected, since removing any single vertex leaves a path that remains connected, and removing two vertices can disconnect the graph. The complete graph K_{k+1} is k-connected, as there are many disjoint paths between any two vertices. By contrast, graphs with articulation points are not 2-connected.

For k = 1, 1-connected graphs are typically understood as simply connected or connected graphs, depending on the convention used, but the standard emphasis in most literature is on k ≥ 2 for meaningful multi-vertex connectivity.

K-connected graphs are central in areas such as network reliability, where higher connectivity indicates greater fault tolerance, and in connectivity augmentation problems, where one seeks to increase a graph’s k-connectedness with minimal additions.