Cut covers and small cases of Mader's local-connectivity conjecture

Definitions and mathematical statement

Let $D$ be a finite nonempty loopless digraph; parallel arcs are allowed and counted separately. The outdegree $d^+(v)$ counts all arcs with tail $v$, and $\delta^+(D)$ is their minimum over vertices. For distinct vertices $x,y$, define $\lambda_D(x,y)$ to be the largest number of pairwise edge-disjoint directed paths from $x$ to $y$. Paths may share internal vertices, but cannot use the same arc; parallel arcs are distinct edges for this purpose. Each path is directed consistently from $x$ to $y$.

The source's two assertions ask whether, for every integer $r\ge1$, \[ \delta^+(D)\ge r\quad\Longrightarrow\quad \exists x\ne y:\lambda_D(x,y)\ge r, \] and, more strongly, whether $x,y$ can always be chosen so that $x\to y$ is an arc of $D$. The stronger assertion includes the first. If an arc $x\to y$ is present, the one-edge path can be one member of the family, but all $r$ paths must still be mutually edge-disjoint. There is no prescribed pair of endpoints and no minimum-indegree condition. The direction in the conclusion is from the tail of the selected arc to its head, rather than in the reverse direction. This is edge connectivity, as denoted by $\lambda$ in the AIM source; replacing it by internally vertex-disjoint connectivity would give a different problem. Loops are excluded since they can raise outdegree without providing a path to a different vertex.

Short English statement

Does minimum outdegree r force r edge-disjoint directed paths between some pair of vertices, and even between the ends of an arc?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001067 (AIM-COMBINATORICS-0192), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, The Caccetta-Haggkvist conjecture, item 6. Original workshop question underlying AIM-COMBINATORICS-0192. https://aimath.org/WWN/caccetta/caccetta.pdf.