kedgeconnected

Kedgeconnected, typically written as k-edge-connected, is a property of graphs in graph theory. A connected graph is k-edge-connected if it remains connected after the removal of any set of fewer than k edges. Equivalently, the edge connectivity of the graph, denoted lambda(G), is at least k. This means every edge cut (a partition of the vertices into two nonempty sets) has at least k crossing edges.

Formally, for a connected graph G, lambda(G) is the minimum number of edges whose removal disconnects G. If lambda(G) >= k, then G is k-edge-connected. Important consequences include that no single edge is a bridge in a k-edge-connected graph with k >= 2, and that the minimum degree delta(G) is at least k (for simple graphs). In general, lambda(G) <= delta(G).

Common examples illustrate the concept: a cycle with at least three vertices is 2-edge-connected, since removing any single edge leaves the graph connected. A complete graph K_n is (n-1)-edge-connected, as removing fewer than n-1 edges cannot disconnect the graph. A tree, by contrast, has lambda(G) = 1 and is not 2-edge-connected.

Computation of k-edge-connectivity can be approached through global minimum cut algorithms, such as Stoer–Wagner, which find the smallest edge cut and thus determine lambda(G). Verifying k-edge-connectivity requires checking that all edge cuts have size at least k; in practice this is done via min-cut computations or specialized network reliability methods.

Applications of k-edge-connected graphs appear in network design, reliability analysis, and redundancy planning, where higher edge-connectivity implies greater resilience to edge failures. See also edge connectivity, vertex connectivity, and Menger’s theorem.