  We study the problem of detecting the edge correlation between two random
graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing
problem, where under the null hypothesis, the two graphs are independently
generated; under the alternative, the two graphs are edge-correlated under some
latent node correspondence, but have the same marginal distributions as the
null. For both Gaussian-weighted complete graphs and dense Erd\H{o}s-R\'enyi
graphs (with edge probability $n^{-o(1)}$), we determine the sharp threshold at
which the optimal testing error probability exhibits a phase transition from
zero to one as $n\to \infty$. For sparse Erd\H{o}s-R\'enyi graphs with edge
probability $n^{-\Omega(1)}$, we determine the threshold within a constant
factor.
  The proof of the impossibility results is an application of the conditional
second-moment method, where we bound the truncated second moment of the
likelihood ratio by carefully conditioning on the typical behavior of the
intersection graph (consisting of edges in both observed graphs) and taking
into account the cycle structure of the induced random permutation on the
edges. Notably, in the sparse regime, this is accomplished by leveraging the
pseudoforest structure of subcritical Erd\H{o}s-R\'enyi graphs and a careful
enumeration of subpseudoforests that can be assembled from short orbits of the
edge permutation.
