Graph enumeration

In some graphical enumeration problems, the vertices of the graph are considered to be labeled in such a way as to be distinguishable from each other, while in other problems any permutation of the vertices is considered to form the same graph, so the vertices are considered identical or unlabeled. In general, labeled problems tend to be easier. As with combinatorial enumeration more generally, the Pólya enumeration theorem is an important tool for reducing unlabeled problems to labeled ones: each unlabeled class is considered as a symmetry class of labeled objects.

The number of unlabelled graphs with vertices is still not known in a closed-form solution, but as almost all graphs are asymmetric this number is asymptotic to

Some important results in this area include the following.

• The number of labeled n-vertex simple undirected graphs is 2^n(n−1)/2.
• The number of labeled n-vertex simple directed graphs is 2ⁿ⁽ⁿ⁻¹⁾.
• The number C_n of connected labeled n-vertex undirected graphs satisfies the recurrence relation

from which one may easily calculate, for n = 1, 2, 3, ..., that the values for C_n are

1, 1, 4, 38, 728, 26704, 1866256, ...(sequence A001187 in the OEIS)

• The number of labeled n-vertex free trees is nⁿ⁻² (Cayley's formula).
• The number of unlabeled n-vertex caterpillars is

Various research groups have provided searchable database that lists graphs with certain properties of a small sizes. For example

• The House of Graphs
• Small Graph Database