Approximate Itai–Zehavi conjecture for random graphs 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. 69 2 Wiley application/pdf