Arc-disjoint out-branching and in-branching

Arc-disjoint out-branching and in-branching

Definitions and mathematical statement

A finite loopless digraph $D=(V,A)$ is $k$-arc-strong if deleting any set of fewer than $k$ arcs leaves a strongly connected digraph. Strong connectivity means a directed path exists from each vertex to each other vertex. Equivalently, every nonempty proper subset $X\subset V$ has at least $k$ arcs leaving it. Arcs are counted individually.

An out-branching rooted at $u\in V$ is a spanning directed tree in which $u$ has indegree zero, every other vertex has indegree one, and every vertex is reachable from $u$. An in-branching rooted at $v\in V$ is the reverse notion: every vertex can reach $v$, which has outdegree zero, and every other vertex has outdegree one. Each branching uses exactly $|V|-1$ arcs.

The conjecture asks whether some absolute integer $k\ge1$ has the following property: for every finite $k$-arc-strong digraph $D$ and every prescribed ordered pair $u,v\in V$, there exist an out-branching $B^+$ rooted at $u$ and an in-branching $B^-$ rooted at $v$ such that \[ A(B^+)\cap A(B^-)=\varnothing. \] The roots may coincide. Both branchings necessarily use every vertex, so the disjointness requirement concerns arcs only. The constant must be independent of the order of $D$ and of the selected roots. Separate existence of the two branchings does not settle the simultaneous arc-disjoint requirement.

Short English statement

Does sufficiently high arc-connectivity guarantee arc-disjoint spanning outward and inward trees at any two prescribed roots?

Research attempt: symmetric digraphs and prescribed-root certificates

Scope and literature check.

GPT-6 Astra Ultra, 2 October 2026. Both branchings must be spanning, their roots are prescribed, and only arcs must be disjoint. Opposite arcs are distinct resources. Bang-Jensen and Wang [S3] characterize prescribed-root pairs in semicomplete digraphs. That structured class does not exhaust the arbitrary digraphs in this question. The work below proves several symmetric subclasses and isolates the distinction between separate reachability and simultaneous arc allocation.

1. The first connectivity level cannot suffice.

On a directed cycle with $n\ge3$ vertices, each ordered pair is connected by a directed path, so the digraph is one-arc-strong. Two disjoint spanning branchings would require $2n-2$ distinct arcs, but the cycle has only $n<2n-2$. Thus no choice of the absolute constant equal to one can answer the question.

There is also a local obstruction. If a set $X$ contains the in-root $v$ and excludes the out-root $u$, an out-branching at $u$ must enter $X$. An in-branching at $v$ must also enter $X$, since vertices outside $X$ must reach $v$. Their entry arcs must be different. Every such cut therefore requires at least two incoming arcs. This necessary condition follows from two-arc-strength, but by itself does not construct compatible branchings on all cuts at once.

2. Equal roots in a bidirected graph.

Let $H$ be a connected undirected graph and replace each edge by both opposite arcs, obtaining its symmetric digraph. Choose any undirected spanning tree $R$ and root it at $u=v$. Direct each tree edge away from the root for $B^+$ and toward the root for $B^-$. Both directions are available. The two branchings use opposite arcs of every edge and are therefore arc-disjoint. This proves the statement in the equal-root symmetric subclass under mere connectivity, despite the failure for general one-arc-strong digraphs. The orientation symmetry is doing essential work.

3. Distinct prescribed roots from two spanning trees.

If $H$ has two edge-disjoint undirected spanning trees, orient the first away from $u$ and the second toward $v$. Disjoint undirected edge sets guarantee disjoint directed arc sets, regardless of the root choices. Every four-edge-connected undirected graph supplies such trees by the Nash-Williams spanning-tree packing theorem [S4]. Indeed, for a partition into $q\ge2$ nonempty parts, summing the at-least-four edges leaving each part and dividing by two shows that at least $2q\ge2(q-1)$ edges cross between parts. This is the packing theorem's condition for two spanning trees. The one-part partition is automatic.

Thus a symmetric digraph whose underlying graph is four-edge-connected has the required pair for every prescribed ordered pair of roots. This is a sufficient condition for a specific class, not a proposed universal constant for nonsymmetric digraphs.

4. Explicit certificates in complete symmetric digraphs.

For distinct roots $u,v$ and at least three vertices, select $w\notin\{u,v\}$. Take \[ A(B^+)=\{u\to x:x\ne u,w\}\cup\{v\to w\}, \] \[ A(B^-)=\{x\to v:x\ne v,u\}\cup\{u\to w\}. \] The first reaches $w$ through $u,v,w$ and every other vertex directly. The second sends $u$ through $u,w,v$ and every other non-root directly to $v$. Both have $n-1$ arcs and the appropriate unique parent at each non-root. Inspection of tails and heads shows that their arc sets are disjoint. With two vertices and distinct roots, the single arc $u\to v$ is forced into both branchings, so the lower order restriction in this explicit construction is necessary.

Verification, gap and final status.

The script [S9] verifies the explicit constructions for orders three through twelve and every root pair, checking degrees, reachability, and disjointness. The first general gap is that an arbitrary out-branching may consume many arcs of a cut, leaving no route for the prescribed in-root. The symmetric tree argument cannot choose directions freely when only one arc direction exists. Full arbitrary-digraph target: UNRESOLVED. The stated symmetric subclasses are established with their precise root conditions.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3267 (OPG-46495), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Arc-disjoint out-branching and in-branching. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/arc_disjoint_out_branching_and_in_branching.
• S3 Jørgen Bang-Jensen and Yun Wang, Arc-disjoint out-branchings and in-branchings in semicomplete digraphs $2023$. https://arxiv.org/abs/2302.06177.
• S4 C. St. J. A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, Journal of the London Mathematical Society 36 $1961$, 445--450. https://doi.org/10.1112/jlms/s1-36.1.445.
• S9 GPT-6 Astra Ultra, exact finite checks accompanying this attempt (2 October 2026). Repository script, Python standard library only. scripts/check_attempt_batch03_digraphs_2026_10_02.py.