Why the number of unlabeled graphs on $n$ vertices is not exactly $\frac{2^{n \choose 2}}{n!}$? OEIS A000088 sequence lists the number of unlabeled graphs on $n$ vertices.
Very naively, I would have expected it to be exactly (well, it can't be, at the least because it's not an integer):
$$\frac{2^{n \choose 2}}{n!}$$
thinking about the possible ${n \choose 2}$ edges present/not present, and then dividing by all the possible permutations of the vertices.
Can someone explain simply why, even if tending asymptotically to that value, there are more than that?
 A: Let's write out the argument for $2^{\binom n2}/n!$ carefully in order to see why it doesn't work.
If we fix a vertex set $\{v_1, v_2, \dots, v_n\}$, there are $\binom n2$ possible edges $v_i v_j$ between those vertices: $\{v_1 v_2, v_1 v_3, \dots, v_{n-1} v_n\}$. There are $2^{\binom n2}$ subsets of this set, and every one of these subsets specifies a graph.
However, if we list out all $2^{\binom n2}$ graphs we get in this way, an unlabeled graph (that is, an isomorphism class of graphs) can appear on this list multiple times. If you a graph from this list, and permute the labels on the vertices, you will get an isomorphic graph with a different edge set - another entry on this list! There are $n!$ ways to permute the vertices, so - you'd think - there are $n!$ entries on this list isomorphic to any given $n$-vertex graph.
If this were true, we could divide by $n!$ to correct for the overcount, and get the true number of graphs. Unfortunately, it is not true.
Consider a particular example: the complete graph $K_n$. There are still $n!$ ways to permute the labels on the vertices, but when you do that, you don't get a different entry on the list - you get the same entry! So $K_n$ only appears on the list once, not $n!$ times.
Or take the $n$-vertex path $P_n$. For $n\ge2$, this appears on the list $\frac12 n!$ times, because if your permutation reverses the vertices of the path, you get a graph with the same set of edges.
In general, a graph with automorphism group $H$ only appears on the list $\frac{n!}{|H|}$ times. So dividing by $n!$ gives an underestimate: we've assumed all graphs appear $n!$ times when in fact some appear less often.
(We could also see that $2^{\binom n2}/n!$ can't possibly be a correct answer because it's not an integer for $n\ge 3$, but that doesn't tell us why it's wrong.)
