Independent trees

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph with $|V|>k\ge1$. The graph is $k$-vertex-connected if deletion of fewer than $k$ vertices leaves it connected. Fix any root $r\in V$. For a spanning tree $T$, write $P_T(r,v)$ for the unique path from $r$ to $v$.

Spanning trees $T_1,\ldots,T_k$ are independent at $r$ if their paths to each common destination have disjoint interiors: \[ (V(P_{T_i}(r,v))\setminus\{r,v\})\cap (V(P_{T_j}(r,v))\setminus\{r,v\})=\varnothing \quad(v\ne r,\ i\ne j). \] Does every $k$-vertex-connected graph have such a family for every choice of root and every $k$?

The root and destination are permitted common endpoints. The trees are not required to be vertex-disjoint, since each spans all of $V$, and they need not be edge-disjoint as whole subgraphs. The comparison is between paths to the same destination from the one fixed root. Requiring analogous independence for paths between every pair of vertices is a stronger, different property. A separate collection of disjoint paths for each destination, supplied by vertex connectivity, does not guarantee consistency of those path collections as spanning trees. It is that simultaneous consistency the conjecture demands.

Short English statement

Does $k$-vertex-connectivity guarantee $k$ spanning trees whose paths from any prescribed common root have pairwise disjoint interiors at each destination?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000045 (AMR-029-0045), 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: Independent trees. Original source indexed by AMR-029-0045. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Independent trees. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Independent_trees.