How many countable graphs are there? Even though there are uncountably many subsets of $\mathbb{N}$ there are only countably many isomorphism classes of countably infinite - or countable, for short - models of the empty theory (with no axioms) over one unary relation.

How many isomorphism classes of
  countable models of the empty theory
  over one binary relation (a.k.a.
  graph theory) are there? I.e.: How many countable unlabeled graphs are there?

A handwaving argument might be: Since the number of unlabeled graphs with $n$ nodes grows (faster than) exponentially (as opposed to growing linearly in the case of a unary relation), there must be uncountably many countable unlabeled graphs. (Analogously to the case of subsets: the number of subsets of finite sets grows exponentially, thus (?) there are uncountably many subsets of a countably infinite set.) 
How is this argument to be made rigorous?

You might be interested in a related, but quite different, question. Suppose we choose the edges of a countable graph randomly, according to some probability $p$. How many different graphs do we expect to get, if we repeat the experiment several times?
You might think that every time we'll get a different graph, but in fact, with probability $1$ the graph generated will be isomorphic to the so-called Rado graph. This is the same graph immaterial of the probability $p$, and you even get the same graphs if the probabilities decay not too fast (under some arbitrary $\omega$-ordering of the edges).
The charming proof is an illustration of the back-and-forth argument - check it out.
