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
Examples help illustrate the concept. The cycle graph C_n for n ≥ 3 is 2-connected, since removing
For k = 1, 1-connected graphs are typically understood as simply connected or connected graphs, depending on
K-connected graphs are central in areas such as network reliability, where higher connectivity indicates greater fault