Approximate Itai–Zehavi Conjecture for Random Graphs

ABSTRACT 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 and for random regular graphs when . 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.