edgedisjoint

Edgedisjoint is a term used in graph theory to describe a condition in which subgraphs, paths, or edge sets do not share any edges. Two subgraphs H1 and H2 of a graph G are edge-disjoint if their edge sets are disjoint, E(H1) ∩ E(H2) = ∅. A collection of subgraphs is pairwise edge-disjoint when this holds for every pair in the collection.

A common focus is edge-disjoint s-t paths. These are s-to-t paths in a graph that do not share any edges. The maximum number of edge-disjoint s-t paths in a graph equals the size of a minimum s-t edge cut, by the max-flow min-cut theorem for graphs with unit-edge capacities. In directed graphs, the same principle holds with edges carrying unit capacity and the maximum s-t flow corresponding to the largest possible number of edge-disjoint paths.

Edge-disjointness is distinct from vertex-disjointness. Two edge-disjoint s-t paths may intersect at vertices other than s and t, as long as they do not use the same edge. Conversely, vertex-disjoint paths share no internal vertices.

Algorithmically, the problem of finding k edge-disjoint s-t paths can be solved by computing a maximum flow from s to t with unit capacities on edges; if the maximum flow value is at least k, such paths exist. The concept extends to families of subgraphs and to edge-disjoint path problems with multiple source–target pairs, which become more complex and have different computational properties depending on whether k is fixed or part of the input.

Applications include network reliability, parallel routing, and traffic engineering, where distributing load across edge-disjoint routes helps prevent single-edge failures from disrupting connectivity.