Asymmetry of random graphs By a well known result of Pólya we know that the number $g_n$ of isomorphism classes of simple graphs on $n$ vertices is asymptotically equivalent to $\frac{2^{\binom{n}{2}}}{n!}$. In this paper the author claims that from Pólya's theorem it follows that almost all graphs are asymmetric (i.e. have only one automorphism). How does that follow? I see that by Burnside's lemma $\frac{n!}{2^{\binom{n}{2}}} g_n$ equals the excepted value of the number of automorphisms of a random graph on $n$ vertices, and from the asymptotic equivalence we can conclude that this excepted value is bounded from above. But doesn't that only mean that a random graph will not have “too many” automorphisms? How does it follow that a random graph is asymmetric if $n$ is sufficiently large? Thank you in advance!

Let $\tilde{G}$ be a random graph chosen uniformly at random among all graphs on $n$ vertices (i.e. $\tilde{G}=G(n,p=1/2)$). Let $P_k$ be the probability that $\tilde{G}$ has exactly $k$ isomorphisms. Note that $P_1+\ldots +P_{n!/2}+P_{n!}=1$ and $2^{{n \choose 2}}P_{\ell}/\ell$ is the number of isomorphism classes with size $\ell$. So \begin{align*} g_n = \sum_\ell \frac{2^{{n \choose 2}}P_\ell}{\ell} \geq 2^{{n \choose 2}}\frac{(1-P_{n!})}{n!/2}+\frac{2^{{n \choose 2}}P_{n!}}{n!}=\frac{2^{{n \choose 2}}}{n!} \left(2-P_{n!}\right). \end{align*}

If $P_{n!} \
eq 1+o(1)$, then this lower bound on $g_n$ would be larger than $(1+o(1))\frac{2^{{n \choose 2}}}{n!}$ (infinitely often), contradicting Polya's result.

EDIT: I should be a little clearer. $P_k$ is the probability that $\tilde{G}$ has isomorphisms to exactly $k$ graphs on $n$ vertices.