On Independent Spanning Trees in Random and Pseudorandom Graphs

In 1989, Zehavi and Itai conjectured that every k-connected graph contains k independent spanning trees rooted at any prescribed vertex r. That is, for each vertex v, the unique r-v paths within these k spanning trees are internally disjoint. This fundamental problem has received much attention, in part motivated by its applications to network reliability, but despite that has only been resolved for k ≤ 4 and certain restricted graph families. We establish the conjecture for almost all graphs of essentially any relevant density. Specifically, we prove that there exists a constant $C > 1$ such that, with high probability, the random graph $G(n,p)$ contains $δ(G)$ independent spanning trees rooted at any vertex whenever C log n/n ≤ p < 0.99. Since the lower bound on p coincides (up to the constant C) with the connectivity threshold of $G(n,p)$, this result is essentially optimal. In addition, we show that $(n,d,λ)$-graphs with fairly mild bounds on the spectral ratio $d/λ$ contain $(1-o(1))d$ independent spanning trees rooted at each vertex, thereby settling the conjecture asymptotically for random d-regular graphs as well.