Arc-disjoint, edge-disjoint and internally vertex-disjoint path families and their local separators

For the following definitions, a directed path occurrence in a finite labelled directed graph $(V,A,\mathrm{tail},\mathrm{head})$, where $V,A$ are finite and $\mathrm{tail},\mathrm{head}:A\to V$, is an alternating list $v_0,a_1,v_1,\dots ,a_{\mathrm{\ell }},v_{\mathrm{\ell }}$ with $a_i\in A$, $\mathrm{tail}(a_i)=v_{i-1}$, and $\mathrm{head}(a_i)=v_i$ for every $i$, whose displayed vertices are distinct. An undirected path occurrence in a finite undirected multigraph (Multigraphs, loops and directed graphs as variants distinct from the default finite simple graph) is an alternating list $v_0,e_1,v_1,\dots ,e_{\mathrm{\ell }},v_{\mathrm{\ell }}$ whose displayed vertices are distinct and whose displayed edge $e_i$ has endpoint set $\{v_{i-1},v_i\}$ for every $i$. Thus each path records its arc or edge labels, including when parallel labels have the same endpoints. An ordinary graph uses each edge $e\in E$ as its own label with endpoint set $e$, while an ordinary digraph uses each ordered-pair arc $(u,v)$ as its own label with $\mathrm{tail}(u,v)=u$ and $\mathrm{head}(u,v)=v$.

For distinct $s,t\in V$, a family of directed $s$-$t$ path occurrences is arc-disjoint if no arc label occurs in two paths; an arc separator is a set of arc labels whose deletion leaves no directed $s$-$t$ path occurrence. For an undirected multigraph, replace arc labels by edge labels to obtain edge-disjoint paths and edge separators. Deleting labels means removing exactly those labels while retaining the other incidence data.

An $s$-$t$ path family is internally vertex-disjoint if no vertex other than $s,t$ occurs in two paths. A vertex separator is a set $S\subseteq V\setminus \{s,t\}$ for which deleting $S$, together with every incident arc or edge label, leaves no $s$-$t$ path occurrence. The local vertex comparison is used only when the terminals are nonadjacent (or, in the directed case, when no arc label has tail $s$ and head $t$), so that such a separator can exist.