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!
 A: 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!} \neq 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.
A: If you google on "almost all graphs are asymmetric" you will find a lot of information. At the top is http://www.fields.utoronto.ca/programs/scientific/11-12/constraint/summerschool/nesetril.pdf, which offers a nice proof of the claim.
The proofs that I am familiar with do not usually start from Polya's lemma, since proving that will of of the same order of difficulty as proving the claim from scratch.
