The diameter of the uniform spanning tree of dense graphs

Noga Alon, Asaf Nachmias, Matan Shalev

We show that the diameter of a uniformly drawn spanning tree of a simple connected graph on $n$ vertices with minimal degree linear in $n$ is typically of order $\sqrt{n}$. A bypro…