---
tag: 610F4NS6GD
kind: definition
name: Graph enumeration
msc: [05C30, 05A16]
defines: 4AVF0RN7HV
uses: [00C0BR7D7H, 0F7QKGJS6B]
sources:
  - url: https://en.wikipedia.org/wiki/Graph_enumeration
---

## Definition

Let $\mathcal{P}$ be a class of finite simple [[graphs|00C0BR7D7H]] that is closed under [[isomorphism|0F7QKGJS6B]].
For an integer $n \ge 1$:

1. The labelled count $\ell_{\mathcal{P}}(n)$ is the number of graphs in $\mathcal{P}$ with vertex set $\set{1, \ldots, n}$.
2. The unlabelled count $u_{\mathcal{P}}(n)$ is the number of isomorphism classes of graphs in $\mathcal{P}$ with $n$ vertices.

*Graph enumeration* is the study of the functions $\ell_{\mathcal{P}}$ and $u_{\mathcal{P}}$: exact formulas, generating functions and asymptotic behaviour as $n \to \infty$.

## 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.