An indexing function for graphs
A graph $G$ whose nodes are numbered is uniquely described by its adjacency matrix. Concatenating the matrix's rows yields a natural number $\cal{G}$ in binary representation; in order to deal with leading $0$, prepend a $1$. This mapping is obviously injective. For easier decoding, you might want to use Cantor's pairing function on $(\cal{G}, |V|)$ and use the result as graph number.

Computing this mapping is easy, but the resulting number can be huge ($\approx 2^{|V|^2}$).

In the case nodes cannot be identified, the (conjectured) hardness of Graph Isomorphism (probably) prevents an efficient, real mapping from Graphs to the naturals; for now, we have to be satisfied  with a mapping from graph presentations to naturals---or show considerable genius.