edgeconnected

Edge-connected, in graph theory, describes a property of an undirected graph G = (V,E). The edge-connectivity λ(G) is defined as the minimum number of edges whose removal disconnects G or leaves it with a single vertex. If G is already disconnected, λ(G)=0. A graph is called k-edge-connected when λ(G) ≥ k; equivalently, removal of any set of fewer than k edges leaves G connected.

Fundamental relations: κ(G) ≤ λ(G) ≤ δ(G), where κ is vertex connectivity and δ is minimum degree. λ(G) equals the minimum size of an edge cut, i.e., a minimum set of edges whose removal separates the vertex set into two nonempty parts. By Menger's theorem, between any two vertices there exist at least λ(G) edge-disjoint paths.

Examples: Cycle C_n (n≥3) is 2-edge-connected since removing a single edge yields a path; A tree has λ(G)=1; Complete graph K_n has λ(G)=n-1.

Computation and applications: λ(G) can be computed via minimum s-t cut algorithms; max-flow/min-cut theorem yields polynomial-time; the Gomory-Hu tree encodes all pairwise minimum cuts; used in network design and reliability.

Variants: for directed graphs, the analogous concept is strong edge-connectivity or the minimum number of edges to remove to destroy strong connectivity; in weighted graphs, edge-connectivity is defined with respect to minimum total weight of an edge cut.