Graph enumeration

Remarks

Example: for the class of all graphs, $\ell(n) = 2^{\binom{n}{2}}$, since each of the $\binom{n}{2}$ pairs is an edge or not. For $n = 3$ this gives $8$, while $u(3) = 4$, one class for each number of edges $0, 1, 2, 3$.

Non-example: the class of graphs in which $1$ and $2$ are adjacent is not closed under isomorphism, so it has no unlabelled count.

Always $u_{\mathcal{P}}(n) \le \ell_{\mathcal{P}}(n) \le n! \, u_{\mathcal{P}}(n)$, because an isomorphism class contains at most $n!$ graphs on $\set{1, \ldots, n}$. For all graphs, $u(n)$ is asymptotic to $2^{\binom{n}{2}} / n!$, because almost all graphs have no nontrivial automorphism.