Probability of Erdös-Renyi graph being isomorphic Let $\mathcal{G}(n,p)$ be an Erdös renyi graph on $n$ vertices and edge probability $p$. Let $S$ be another fixed graph on $n$ vertices with $e$ edges. I am interested in the probability
$$\mathbb{P}(S \text{ is isomorphic to } \mathcal{G}(n,p) \,\vert\, \mathcal{G}(n,p) \text{ has } e \text{ edges}).$$
With insight from other questions (1/2), I think the answer should be
$$\mathbb{P}(S \text{ is isomorphic to } \mathcal{G}(n,p) \,\vert\, \mathcal{G}(n,p) \text{ has } e \text{ edges}) = \frac{\frac{n!}{|\text{Aut}(S)|}}{\binom{\binom{n}{2}}{e}}.$$
However, I can't really deduce why this should hold. I am especially intrigued by the connection to the number of elements in the automorphism group in $S$. The explanation in the first question linked was of no help to me.
 A: There are $\binom{\binom n2}e$ possible $e$-edge graphs that $\mathcal G(n,p)$ could be, and they are all equally likely. So to get the probability we want, it must be the case that $\frac{n!}{|\text{Aut}(S)|}$ of these graphs are isomorphic to $S$.
To be specific, suppose that the vertex set of $\mathcal G(n,p)$ is $v_1, v_2, \dots, v_n$, and let $S^*$ be any specific graph with vertices $v_1, v_2, \dots, v_n$ which is isomorphic to $S$. One way $\mathcal G(n,p)$ could be isomorphic to $S$ is is by being $S^*$.
For any permutation $\sigma$, let $\sigma(S^*)$ be the $e$-edge graph that has edge $v_{\sigma(i)} v_{\sigma(j)}$ for every edge $v_i v_j \in E(S^*)$. This graph $\sigma(S^*)$ is another possible graph isomorphic to $S$ that $\mathcal G(n,p)$ could be. So it seems like there are $n!$ possibilities: $\sigma(S^*)$ for each possible permutation $S^*$...
...except that this counts several outcomes multiple times. Specifically, $\sigma(S^*)$ and $\tau(S^*)$ are the same graph (not just isomorphic) if and only if $\sigma^{-1}(\tau(S^*))$ is the same graph as $S^*$, which is true if and only if $\sigma^{-1} \circ \tau \in \text{Aut}(S^*)$. Therefore each graph that appears as $\sigma(S^*)$ for some $\sigma$, appears exactly $|\text{Aut}(S^*)| = |\text{Aut}(S)|$ times.
Correcting the overcount, we get $\frac{n!}{|\text{Aut}(S)|}$ distinct outcomes that make $\mathcal G(n,p)$ isomorphic to $S$.
