Arc-disjoint strongly connected spanning subdigraphs

Arc-disjoint strongly connected spanning subdigraphs

Definitions and mathematical statement

Let $D=(V,A)$ be a finite loopless digraph with at least two vertices; opposite arcs are allowed. It is strongly connected if for every ordered pair of distinct vertices $u,v$ there is a directed path from $u$ to $v$. For a positive integer $k$, call it $k$-arc-strong if deleting any set of fewer than $k$ arcs leaves a strongly connected digraph. Equivalently, each nonempty proper subset $X\subset V$ has at least $k$ arcs directed from $X$ to $V\setminus X$. Applying this to the complement also ensures at least $k$ arcs entering $X$.

The conjecture asks for one absolute integer $k\ge1$ such that every $k$-arc-strong digraph contains arc sets $A_1,A_2\subseteq A$ with \[ A_1\cap A_2=\varnothing,\qquad (V,A_1)\text{ and }(V,A_2)\text{ both strongly connected}. \] Both subdigraphs must span all vertices. They can share vertices, as they necessarily do; only their arcs must be disjoint. The constant must be independent of the number of vertices and all other features of $D$.

Unused arcs may be assigned to either subdigraph without destroying strong connectivity, so the conclusion is equivalently a partition of all arcs into two strongly connected spanning subdigraphs. Merely finding two directed spanning trees, or high undirected edge-connectivity, is insufficient. The source's term "$k$-arc-connected" is interpreted in this directed strong-connectivity sense.

Short English statement

Is there an absolute arc-connectivity threshold forcing two arc-disjoint strongly connected spanning subdigraphs?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. This attempt keeps the catalogue statement above, checks primary literature, and develops a restricted argument with an adversarial gap audit. The proofs below are the mathematical output of this attempt, not a claim of novelty or external certification.

Literature and attack plan.

The original Garden entry [S2] records Bang-Jensen and Yeo's conjecture and its established special classes. It also distinguishes this question from packing branchings. The route here is a direct construction for symmetric digraphs, where each arc comes with its reverse. We prove the needed orientation statement rather than assume that high undirected connectivity alone supplies the directed conclusion.

Restricted theorem.

Let $G$ be a finite connected simple undirected graph on at least two vertices with no bridge, and let $\overleftrightarrow{G}$ contain both directed arcs for each edge of $G$. Then $\overleftrightarrow{G}$ is the arc-disjoint union of two strongly connected spanning subdigraphs.

We first construct a strong orientation of $G$, a standard form of Robbins' theorem. Choose a cycle and orient it cyclically. Such a cycle exists since $G$ is connected, nontrivial, and bridgeless. Maintain a strongly connected oriented subgraph on a vertex set $U$.

If $U\ne V(G)$, choose a connected component $C$ of $G-U$. At least two distinct edges join $C$ to $U$: zero would contradict connectedness, and one would be a bridge. Choose two such edges $ua$ and $bv$ with $u,v\in U$ and $a,b\in C$. A simple path inside $C$ joins $a$ to $b$; when $a=b$ this path has length zero. The resulting sequence from $u$ through $C$ to $v$ has internal vertices outside $U$ and is either a simple path or, when $u=v$, a cycle meeting $U$ just at its endpoint. Its edges have not been oriented previously.

Orient this entire sequence from $u$ toward $v$. Every new vertex is reachable from $u$ along the prefix and can reach $v$ along the suffix. Existing vertices already reach $u$ and are reachable from $v$. Thus the enlarged oriented subgraph is strongly connected. It contains at least one more vertex. Repeat until all vertices are included, then orient unused edges arbitrarily. Adding arcs cannot destroy strong connectivity.

Splitting the symmetric digraph.

Put in $A_1$ the single oriented arc chosen above for every undirected edge; put its reverse in $A_2$. The sets are disjoint and together equal all arcs of $\overleftrightarrow{G}$. The first subdigraph is strong by construction. Reversing every arc of a strong digraph preserves strong connectivity, since a path from $v$ to $u$ reverses to a path from $u$ to $v$. Hence the second subdigraph is also strong.

For a nonempty proper vertex set $X$, the number of arcs leaving $X$ in $\overleftrightarrow{G}$ equals the number of undirected edges across its cut. Thus a symmetric digraph is 2-arc-strong exactly when its underlying graph is connected and bridgeless. The theorem proves the conjectured conclusion with threshold two within this entire subclass.

Boundary tests.

A symmetric cycle splits into its two opposite directed cycles, a direct instance of the construction. Articulation vertices are allowed: two cycles meeting at one vertex are bridgeless but not 2-vertex-connected, and the successive closed-ear construction still works. This verifies that the proof needs edge-connectivity, not vertex-connectivity.

Conversely, if $G$ has a bridge, its corresponding cut in $\overleftrightarrow{G}$ has only one outgoing arc. Every strong spanning subdigraph must contain that arc, so two arc-disjoint ones are impossible. This makes the threshold exact for symmetric digraphs. For unrestricted digraphs even 1-arc-strength is plainly insufficient: a directed cycle has only one outgoing arc at each vertex, needed by any strong spanning subdigraph.

Why the proof does not extend automatically.

For a general directed graph the reverse of an available arc may not be present. The split $A_2=\{vu:uv\in A_1\}$ can therefore demand nonexistent arcs. Nor does separately packing out-branchings ensure strong connectivity: an out-branching has no directed return route from its leaves to its root. A valid proof must control both directions of every cut in each of the two parts, using the same arc allocation throughout.

Final status and first gap.

The symmetric subclass is completely handled by an explicit orientation construction and exact cut obstruction. The missing step is a simultaneous arc allocation for arbitrary high-arc-connectivity digraphs without reverse symmetry, with a threshold independent of their order. The general conjecture is UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3124 (OPG-46496), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Arc-disjoint strongly connected spanning subdigraphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/arc_disjoint_strongly_connected_spanning_subdigraphs.