What is an example of a bijection from unlabeled graphs to the positive integers? Suppose $f$ is a bijection from the set of unlabeled graphs--i.e. isomorphism classes of graphs -- to the positive integers $\mathbb{N}$. Due to the isomorphism graph problem, I understand that trying to compute $f(G)$ or $f^{-1}(n)$, where $G$ is a graph, would require a lot of computations, maybe on the order of $O(2^{n^2})$. I was wondering if someone could give me an example of such a function. Clearly such a function exists since there are countably many unlabeled graphs.
 A: Writing such a thing out in full detail will be very annoying, since as you say if you could compute such a thing then you could solve graph isomorphism. Here is a sketch: it's a lot easier to write down such a thing for labeled graphs, since a labeled graph on the vertex set $\{ 1, 2, \dots n \}$ is completely specified by specifying its edges. So we can encode a labeled graph on $\{ 1, 2, \dots n \}$ by writing down a binary string of length ${n \choose 2}$ indicating which edges exist in the graph, where the positions of the characters in the string correspond to the edges in lexicographic order; that is, the edges are indicated in the order $(12), (13), (14), \dots (23), (24), \dots$.
Then we can write down all labeled graphs on $\{ 1, 2, \dots n \}$ by writing down all $2^{ {n \choose 2} }$ such binary strings in lexicographic order. And we can write down all labeled graphs by writing down the strings describing labeled graphs on $0$ vertices, then on $1$ vertex, etc. Writing down the elements of a countable set in a fixed order is equivalent to finding a bijection with $\mathbb{N}$; the bijection sends $n \in \mathbb{N}$ to the $n^{th}$ element in the order.
This bijection begins
$$\emptyset, \emptyset, 0, 1, 000, 001, 010, \dots, 000000, 000001, 000010, \dots$$
where $\emptyset$ denotes the empty string and we need two of them corresponding to the empty graph and the unique graph on $1$ vertex (so the binary string encoding is very slightly non-unique which is annoying but doesn't affect whether this is a bijection).
This bijection can be computed efficiently by subtracting $2^{ {n \choose 2} }$ repeatedly until you can't anymore, then writing down the result in binary.
Given the bijection for labeled graphs, we can construct a bijection for unlabeled graphs as follows: start writing down all labeled graphs in the same order as above, but ignore a graph if it's isomorphic to one you've written down already. Naturally, as expected, this bijection is very hard to compute. It begins
$$\emptyset, \emptyset, 0, 1, 000, 001, 011, 111, 000000, \dots$$
where the $2^3 = 8$ binary strings of length $3$ describe $8$ labeled graphs but only $4$ unlabeled graphs on $3$ vertices, namely the empty graph $000$, the single edge $001$ (isomorphic to $010$ and $100$), the double edge $011$ (isomorphic to $101$ and $110$), and the triangle / complete graph / cycle $111$. So given all binary strings corresponding to different labelings of the same unlabeled graph we write down the first one in lexicographic order only and discard the rest.
A: Here's another way of thinking about it: with orderings, rather than encodings.
First, define a well-ordering of all labeled graphs on vertex sets of the form $\{1, 2, \dots, n\}$. This well-ordering will say that $G \prec H$ if

*

*$G$ has fewer vertices than $H$, or

*$G$ has the same number of vertices as $H$, and if we sort the edges in $E(G) \mathbin{\Delta} E(H)$ in lexicographic order, the first edge will be an edge of $G$.

Second, use $\prec$ to get another well-ordering of unlabeled graphs, which we'll also call $\prec$. To compare two unlabeled graphs $G$ and $H$:

*

*Let $\mathcal G$ be the set of all labeled graphs on vertex set $\{1, 2, \dots, |V(G)|\}$ isomorphic to $G$; let $\mathcal H$ be the corresponding set for $H$.

*Let $\min \mathcal G$ be the minimum element of $\mathcal G$ with respect to $\prec$, and the same for $\min \mathcal H$.

*We say $G \prec H$ if $\min \mathcal G \prec \min \mathcal H$.

Finally, define a map $f$ from the set of all unlabeled graphs to $\mathbb Z^+$ by letting $f(G)$ be the number of unlabeled graphs that precede $G$ with respect to $\prec$, plus $1$.
