On Independent Spanning Trees in Random Graphs

A central challenge in network design is ensuring resilience: how can we guarantee multiple, independent, communication pathways between nodes, even when some connections fail in a network? In 1989, Zehavi and Itai formulated a graph-theoretic conjecture that captures the essence of this problem. They proposed that any $k$-vertex-connected graph contains $k$ independent spanning trees rooted at any given root $r$, which means that for every vertex $v$ in the graph, the unique $r-v$ paths within these $k$ spanning trees are entirely disjoint, apart from their endpoints $r$ and $v$. Despite decades of effort, this conjecture has only been proven for $k \le 4$ and for specific graph families using their underlying topological structure, leaving the general case as an open problem in graph theory with substantial consequences in the field of distributed algorithms.