neurips_Graphs_supp.pdf

And if they are too close to each other, it is also quite clear that spectral methods will not work. However, we highlight these statements in Figure 1. Then we will proceed to prove technical statements made in Section 1. Let us first consider a preliminary remark on the connectivity of the random graph. Then one has that P ( 9 an isolated vertex i, 1 i N)! 0 as N!1 .