On Independent Spanning Trees in Random and Pseudorandom Graphs

Nemanja Draganić, Keith Frankston, Michael Krivelevich +2

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 u…