Edgedisjointness

Edge disjointness, sometimes written as edgedisjointness, is a property of a graph or a collection of subgraphs in which the involved edges do not overlap between components. If G=(V,E) contains subgraphs G1=(V1,E1), G2=(V2,E2), then Gi and Gj are edge-disjoint when E1 ∩ E2 = ∅. A collection {G1,...,Gk} is pairwise edge-disjoint if all pairs satisfy this condition. The concept is central in path problems: a set of s–t paths is edge-disjoint if no two paths use the same edge; edges may incident to the same vertex.

In a network context with unit edge capacities, the maximum number of edge-disjoint s–t paths equals the capacity of a minimum s–t cut, by the max-flow min-cut theorem. This equivalence underpins the edge-disjoint paths problem and allows algorithmic solutions via max-flow techniques.

Edge disjointness also extends to directed graphs, where disjointness refers to directed edges and a path uses edges in their specified directions. It contrasts with vertex disjointness, where paths are allowed to share vertices but not edges; a stronger variant prohibits shared vertices as well.

Applications include routing in communication networks, parallel computation, and VLSI design, where avoiding shared edges reduces interference or contention. In graph theory, edge-connectivity, the minimum number of edges whose removal disconnects the graph, is closely related to the existence of multiple edge-disjoint paths between vertex pairs.

See also: edge-disjoint paths problem, max-flow min-cut theorem, Menger's theorem, edge-connectivity, vertex-disjointness. References to standard texts on graph theory provide formal proofs and algorithmic approaches.