Combinatorics – How Many Countable Graphs Exist?

combinatoricsgraph theory

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?

Best Answer

Here is one explicit way of producing continuum-many pairwise nonisomorphic (simple, undirected, loopless) graphs.

Start with a $3$-cycle among vertices labelled $-2,-1,0$. To the vertex $-1$ attach a tail (= path) of length $1$ and to the vertex $-2$ attach a tail of length $2$. Now, for each positive integer $n$, attach a tail of length $n$ to the vertex $0$, and label the terminal vertex in this tail $n$. (So we have some vertices that we have not labelled, but certainly only countably many of them.)

Now focus on the vertices marked $1,2,3,\ldots$: color the odd numbered ones red and the even numbered ones green. Consider the set of all possible bipartite graphs on this vertex set -- i.e., in which all edges connect red to green. There are clearly continuum-many: for instance even the independent choices of including / not including the edges $1--2$, $1--4$, $1--6$, and so forth gives a set of continuum cardinality. I claim that all of these graphs are pairwise nonisomorphic. Indeed, the only three cycle in any of them is formed by the vertices $-2,-1,0$, and it follows easily from this that any isomorphism between any two of these graphs carries $0$ to $0$, $-1$ to $-1$ and $-2$ to $-2$. From this it follows that for all $n \in \mathbb{Z}^+$, an isomorphism takes the vertex labelled $n$ to the vertex labelled $n$ and thus every vertex is fixed.

(By the way, I don't find the argument you suggest to be at all valid. I strongly suspect there are first order theories such that the number of nonisomorphic models of finite size $n$ grows at least exponentially with $n$ but for which there are only countably many isomorphism classes of countable models.)

Added: I want to make sure that the paths from $0$ to $n$ stay pairwise nonisomorphic when edges are added, so it's best to modify the construction slightly. For instance, call the penultimate vertex in the path $p_n$ and attach one more length one tail at $p_n$, so that now $p_n$ has degree $3$.

Related Question