Approximate Itai–Zehavi conjecture for random graphs Hollom, Lawrence Lichev, Lyuben Mond, Adva Portier, Julien Wang, Yiting ddc:500 A famous conjecture by Itai and Zehavi states that, for every 𝑑 -vertex-connected graph 𝐺 and every vertex 𝑟 in 𝐺 , there are 𝑑 spanning trees of 𝐺 such that, for every vertex 𝑣 in 𝐺 ∖{𝑟} , the paths between 𝑟 and 𝑣 in different trees are internally vertex-disjoint. We show that with high probability the Itai–Zehavi conjecture holds asymptotically for the Erdős–Rényi random graph 𝐺⁡(𝑛,𝑝) when 𝑛⁢𝑝 =𝜔⁡(log⁡𝑛) and for random regular graphs 𝐺⁡(𝑛,𝑑) when 𝑑 =𝜔⁡(log⁡𝑛) . Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers a question of Draganić and Krivelevich positively. Our proof makes use of recent developments on sprinkling techniques in random regular graphs. Wiley 2026 info:eu-repo/semantics/article doc-type:Article Article http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/23001 https://research-explorer.ista.ac.at/download/23001/23068 Hollom L, Lichev L, Mond A, Portier J, Wang Y. Approximate Itai–Zehavi conjecture for random graphs. <i>Random Structures and Algorithms</i>. 2026;69(2). doi:<a href="https://doi.org/10.1002/rsa.70095">10.1002/rsa.70095</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1002/rsa.70095 info:eu-repo/semantics/altIdentifier/issn/1042-9832 info:eu-repo/semantics/altIdentifier/e-issn/1098-2418 info:eu-repo/semantics/altIdentifier/arxiv/2506.23970 https://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess