How dense is the set of asymmetric graphs?

Almost all non-asymmetric graphs have exactly one non-trivial automorphism, namely a transposition swapping two vertices. So, an accurate estimate of their number is obtained by taking an arbitrary graph with one vertex less, choosing a vertex $v$, adding a new vertex $w$ with the same neighbours as $v$, then either joining or not joining $v$ to $w$. For labelled graphs, if $g_n=2^{\binom n2}$ is the number of them we have asymptotically $2ng_{n-1}$ non-asymmetric graphs. This is a small fraction. For unlabelled graphs, divide the total by $n!$ and the non-asymmetric ones by $n!/2$.

I don't have a reference, but I suspect that the most natural way to prove that almost all finite graphs are asymmetric is by giving a good estimate on how few symmetric graphs there are, so check where you got the result that almost all finite graphs are asymmetric.

The union bound works: Add up the counts of graphs fixed by each permutation. For any nontrivial permutation $\pi \in S_n$, consider the action on the $n \choose 2$ edges. If there are $r$ orbits on the edges, then the number of graphs fixed by $\pi$ is $2^r$ because there is one independent binary choice per orbit.

For example, if $\pi = (1~2)$, then there are $(n-2)$ orbits of size $2$, and one edge switched by $\pi$, and $n-2 \choose 2$ edges which are not moved at all by $\pi$. So, the number of graphs fixed by $\pi$ is smaller than the total number of graphs by a factor of $2^{n-2}$. There are $n \choose 2$ transpositions, so out of all graphs, at most ${n \choose 2} 2^{-(n-2)}$ of the graphs are fixed by a transposition. These are the most common symmetries.

To bound the number of symmetric graphs, filter permutations by the number of moved points $k$. There aren't many permutations with many fixed points, at most ${n\choose k} k! \le n^k$. Permutations with few fixed points move many edges (even when both endpoints move, this can only reverse at most $n/2$ edges), hence many edges are contained in orbits of size at least $2$, hence there are at most ${n\choose 2} + n/2 - {k \choose 2}/2$ orbits.

$$\frac{\text{# symmetric}}{2^{n \choose 2}} \le \sum_{k \lt n/2} \frac{n^k}{2^{k(n-k)/2}} + \sum_{k\ge n/2} \frac{n!}{2^{{k\choose 2}/2 - n/2}}$$

After that, routine estimates show that when $n$ is large, the term from transpositions is small but dominates the others.

There are some references and some more information in the entry on the number of asymmetric graphs on n nodes in the OEIS (Online Encyclopedia of Integer Sequences):

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 220, Section P3.4.

P. Steinbach, Field Guide to Simple Graphs. Design Lab, Albuquerque NM, 1990.

The number of such graphs goes in the surprising sequence 1, 0, 0, 0, 0, 8, 152, 3696, 135004, 7971848, 805364776, ...