Our analysis exploits the locally tree-like property of random \(\Delta \) -regular graphs, meaning that these graphs contain a small number of short cycles.
Our method might be applicable to other locally tree-like graphs, such as Erdös-Rényi random graphs and scale-free graphs.
In particular, many real world networks, such as Internet networks, social networks, and peer-to-peer networks, are believed to have scale-free properties [1]}, [2]}, [3]}.
We defer the reconstruction of those networks for future work.
