edgeconnectivity

Edge connectivity is a graph-theoretic measure of a network’s resilience to edge failures. In an undirected graph, the edge connectivity, denoted λ(G), is the minimum number of edges whose removal disconnects the graph or reduces it to a single vertex. A graph is said to be k-edge-connected if λ(G) ≥ k. For a connected graph with at least two vertices, λ(G) equals the size of a smallest edge cut—the smallest set of edges that, if removed, would disconnect the graph.

Edge connectivity relates to other graph invariants through simple inequalities. Let κ(G) be the vertex connectivity (the minimum number of vertices whose removal disconnects the graph). Then κ(G) ≤ λ(G) ≤ δ(G), where δ(G) is the minimum degree of G. In complete graphs K_n, all three values equal n−1. The theory also aligns with Menger’s theorem: the minimum number of edges whose removal separates two vertices equals the maximum number of edge-disjoint u–v paths between those vertices, and λ(G) is the minimum of these values over all vertex pairs.

Computing edge connectivity involves finding a global minimum cut. The Stoer–Wagner algorithm determines λ(G) in time roughly O(n^3) for an n-vertex graph. Alternatively, λ(G) can be derived by solving a family of max-flow problems between vertex pairs, though this is typically more computationally intensive.

Applications of edge connectivity include assessing network reliability, guiding the design of fault-tolerant infrastructure, and analyzing the robustness of communication and transportation systems. Simple graphs illustrate the concept: cycles have λ = 2, trees have λ = 1, and complete graphs have λ = n−1. Edge connectivity provides a precise, scalable measure of how vulnerable a network is to random or targeted link failures.