Edge-independent spanning trees

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless undirected graph and fix a root $r\in V$. A spanning tree is a connected acyclic subgraph on all of $V$. Denote its unique $r$--$v$ path by $P_T(r,v)$. A family $T_1,\ldots,T_k$ is edge-independent at $r$ if \[ E(P_{T_i}(r,v))\cap E(P_{T_j}(r,v))=\varnothing \quad(v\ne r,\ i\ne j). \] The graph is $k$-edge-connected when every nontrivial edge cut contains at least $k$ edges, equivalently when deleting fewer than $k$ edges cannot disconnect it.

Is every finite $k$-edge-connected graph equipped with $k$ spanning trees edge-independent at any specified root, for every integer $k\ge1$? If parallel edges are present, they are distinct in all path and cut counts.

The trees themselves are not required to have disjoint edge sets. An edge may occur in several trees, provided it never lies on two of the compared root-to-the-same-vertex paths. Consequently the usual criterion for packing edge-disjoint spanning trees is a different, stronger demand. Choosing $k$ disjoint paths separately for each target by a path-connectivity theorem does not suffice: the path choices for all targets must fit together into the same $k$ global spanning trees.

Short English statement

Does $k$-edge-connectivity guarantee $k$ spanning trees whose paths from a common root to each vertex are pairwise edge-disjoint?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000032 (AMR-029-0032), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Edge-independent spanning trees. Original source indexed by AMR-029-0032. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Edge-independent spanning trees. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Edge-independent_spanning_trees.