Paths, Cycles, and Arc-Connectivity in Digraphs

NEW

Problem: Reconstructed statement: in a finite digraph $D$, if $D$ is $k$-arc-connected and $l\le k$, then for prescribed triples $(x_i,f_i,y_i)$, with $f_i\in E^+(x_i)$ (or respectively $f_i\in E^-(y_i)$), there exist arc-disjoint directed $x_i$-to-$y_i$ paths $P_i$ containing $f_i$, such that deleting all arcs of the $P_i$'s leaves a $(k-l)$-arc-connected digraph.

Here “$k$-arc-connected” is interpreted as $k$-arc-strong: every nonempty proper vertex set has at least $k$ outgoing and at least $k$ incoming arcs. A path is a simple directed path.

Result: The conjecture is false, even for $k=l=2$, with distinct prescribed arcs and distinct terminals.

Let $D$ be the bidirected 5-cycle on vertices

i.e. for each edge of the undirected cycle

both directed arcs are present.

This digraph is $2$-arc-connected: for every nonempty proper $S\subset V(D)$, the undirected cycle has at least two edges crossing the cut $(S,V\setminus S)$, and each crossing edge contributes exactly one arc leaving $S$ and one arc entering $S$.

Take $l=2$ and prescribe

Both prescribed arcs are distinct, and $f_i\in E^+(x_i)$.

Any directed path from $1$ to $2$ containing $f_2=1\to0$ must begin

From $0$, the only out-neighbours are $1$ and $4$. Since a path cannot revisit $1$, it must next use

Thus every admissible $P_2$ contains $f_1$.

But every admissible $P_1$ must also contain $f_1$ by prescription. Hence $P_1$ and $P_2$ cannot be arc-disjoint. Therefore the asserted paths do not exist.

This already falsifies the conjecture before the residual $(k-l)=0$-arc-connectivity condition becomes relevant.

Citation: No known resolution is being invoked here. The counterexample above is self-contained. The conjecture is attributed in the prompt to Xiang-Ying Su, “Paths, cycles, and arc-connectivity in digraphs,” J. Graph Theory 19 (1995).