In other words, is there a bijective correspondence between the natural numbers and unlabeled, undirected (and connected) graphs?

Considering there is a finite number of connected graphs of such type for $n$ vertices (See sequence A001349 on the OEIS), this is trivially true. However, is there a "natural" way to enumerate such, where given the $n^{th}$ graph, one could deduce exactly how the vertices and edges connect?

connected graphs

This is perhaps analogous to the "natural" way of enumerating rooted identity trees, where given, say the $5^{th}$ rooted identity tree, the graph of which can be deduced by the binary expansion: Since $5=2^2+2^0$, then the $5^{th}$ rooted identity tree has 2 main branches, which by themselves are the $2^{nd}$ and $0^{th}$ rooteed identity trees.

rooted identity tree


There are at least two ways to enumerate the set of unlabeled graphs applying a suitable labeling algorithm. Suppose we have a graph $G$ with $n$ vertices. Then one of the following labelings can be used.

  1. There are $n!$ ways to label the vertices using $\{1,...,n\}$. For all such labelings build the adjacency matrix choosing the lexicographically minimal matrix $M$. Choose the labeling corresponding to $M$.

  2. Draw $n$ vertices $\{1,...,n\}$ adding each time the lexicographically minimal edge and checking if the obtained graph is a subgraph of $G$ (if not, return to the previous step and choose the next edge).

In both cases we can build a bijection from the unlabeled graphs to some naturally ordered set.

We will also manage to enumerate separate classes of unlabeled graphs using the labelings that satisfy additional conditions. For example, if the graceful labeling conjecture holds we can enumerate trees using graceful labelings.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.