Here we assume \(p=1/n\)  for convenience; all our results regarding noisy trees also hold when the perturbation probability \(p\)  satisfies \(p=\epsilon /n\)  for \(\epsilon <1\) . Noisy trees are related to small world models of random networks [1]}, [2]}, where adding a few random edges to a graph of high diameter such as a path results with a graph of logarithmic diameter w.h.p. [3]}. Sparse connected graphs that are perturbed with a small number of random edges have received attention in various domains [1]}.
