The Erdos-Renyi random graph model G(N,p) describes a way to generate a network with N nodes, the probability that there is a link between any two nodes is p. I am wondering about the probability of generating a ring graph. Based on my understanding, the probability is N!*(p^N)*(1-p)^(N(N-3)). Is it correct?



The probability of generating a ring graph by following the Erdos-Renyi model G(N,p)
Generating precisely a cycle?


There are $(N-1)!$ ways to order the vertices to be in a cycle; a permutation is considered equivalent to another if they generate the same cycle, and each permutation is equivalent to $N$ permutations total including itself. [e.g., on 5 vertices the permutation 12345 is equivalent to 34512 because they both generate the same cycle 12345 = 34512.]


Then once given a way to order the vertices, you want there to be $N$ edges all in the cycle, and you want the remaining ${N \choose 2} -N$ pairs to not form an edge. This gives:


$$\mathbb{P}[G(n,p) {\text{ forms a cycle }}] = (N-1)!p^N(1-p)^{{N \choose 2} -N}.$$


