The condition of Beineke and Harary on edge-disjoint paths some of which are openly disjoint (Q1346794)

Connectivity pairs were introduced by Beineke and Harary and provide some measure of the ``connectivity'' between a given pair of vertices in a graph \(G\). The precise definition is as follows: A pair \((t, s)\) of nonnegative integers is a connectivity pair for the pair of distinct vertices \(x, y\in V(G)\) if (i) for each pair of subsets \(T\subseteq V(G)- \{x, y\}\) and \(S\subseteq E(G)\), with \(|T|\leq t\), \(|S|\leq s\) and \(|S|+ |T|< s+ t\), \(x\) and \(y\) are joined by a path in \(G- S- T\); and (ii) there exist subsets \(T'\subseteq V(G)- \{x, y\}\) and \(S'\subseteq E(G)\), with \(|T'|= t\), \(|S'|= s\) such that \(x\) and \(y\) lie in different components of \(G- S'- T'\). In this paper it is shown that for integers \(q\), \(r\), \(s\), \(t\) with \(t\geq 0\), \(s\geq 1\) and \(t+ s= q(t+ 1)+ r\), \(1\leq r\leq t+ 1\), if \(q+ r> t\) and if \((t, s)\) is a connectivity pair for \(x\) and \(y\), then \(G\) contains \(t+ s\) edge-disjoint \(x\)--\(y\) paths, \(t+ 1\) of which are openly disjoint.