Vertexdisjoint

Vertex-disjoint describes a relationship among subgraphs or paths in a graph where the involved objects do not share any vertices. A collection of paths is vertex-disjoint if no two paths contain a common vertex. When considering two fixed vertices s and t, a common convention is to speak of internally vertex-disjoint s–t paths: the paths may share the endpoints s and t but do not share any other vertices. In contrast, two paths that share even a single vertex are not vertex-disjoint.

This concept is distinct from edge-disjoint paths, which may share vertices but not edges. Vertex-disjointness is often more restrictive than edge-disjointness because a shared vertex can block the disjointness of multiple paths even if their edges are separate.

Computationally, determining the maximum number of internally vertex-disjoint s–t paths can be treated as a maximum flow problem using a vertex-splitting transformation. Each vertex v is split into v_in and v_out with a capacity-1 edge from v_in to v_out; original directed edges are replaced by edges from u_out to v_in. A maximum s–t flow in this transformed network equals the maximum number of internally vertex-disjoint s–t paths in the original graph. This approach generalizes to finding vertex-disjoint paths among several terminals and underpins related algorithms for disjoint paths problems.

The concept relates to fundamental results such as Menger's theorem, which connects the maximum number of internally vertex-disjoint s–t paths to the minimum s–t vertex cut. Vertex-disjoint path properties have applications in network reliability, routing, VLSI design, and graph connectivity analyses.

See also: vertex cut, connectivity, disjoint paths problem, Menger's theorem.