Given a positive integer n, an unlabeled graph G on n vertices, and a vertex v of G, let \(N_G(v)\) be the subgraph of G induced by vertices of G of distance at most one from v. We show that there are universal constants \(C,c>0\) with the following property. Let the sequence \((p_n)_{n=1}^\infty \) satisfy \(n^{-1/2}\log ^C n\le p_n\le c\) . For each n, let \(\Gamma _n\) be an unlabeled \(G(n,p_n)\) Erdős–Rényi graph. Then with probability \(1-o_n(1)\) , any unlabeled graph \(\tilde{\Gamma }_n\) on n vertices with \(\{N_{\tilde{\Gamma }_n}(v)\}_{v}=\{N_{\Gamma _n}(v)\}_{v}\) must coincide with \(\Gamma _n\) . This establishes \(\tilde{\Theta }\left( n^{-1/2}\right) \) as the transition range for the density parameter \(p_n\) between reconstructability and non-reconstructability of Erdős–Rényi graphs from their 1–neighborhoods, and resolves a problem of Gaudio and Mossel from (Electron Commun Probab 27: 1–14, 2022)
