Is the Set of all Graphs Countable?

I am taking an elementary level set theory, and was doing an exercise. The question is "Is the set of all graphs countable?"

My intuition tells me it is not but I am not sure how I can use Cantor's diagonalization argument to prove it. And I don't even know what other methods can be used here.

P.S A graph means a graph in the sense of Graph Theory.

-
What is a "graph"? (There are many meanings of the word, so whatever the answer is may turn on exactly what you mean by "graph"; for example, the "graph of a function" is one thing, but a "graph" in the sense of Graph Theory is another). –  Arturo Magidin Dec 1 '11 at 20:24
in the sense of Graph Theory –  geraldgreen Dec 1 '11 at 20:32
@John.Mathew: But why can't you take a discrete graph in any cardinality whatsoever? Do you perhaps mean finite graphs? Or even countable graphs? –  Asaf Karagila Dec 1 '11 at 20:35
In any event, none of the categories on this problem are right, other than "elementary set theory." Maybe graph theory, but not really much. –  Thomas Andrews Dec 1 '11 at 20:35
The collection of all graphs (e.g. in ZFC), even all finite graphs, is not even a set. The collection of all isomorphism classes of graphs is still not a set. So you need to be more precise. –  Qiaochu Yuan Dec 1 '11 at 20:51
show 3 more comments

4 Answers

One possible approach via Cantor's diagonalisation argument would be as follows. (We will show that there are uncountably many (undirected) graphs with vertex set $\mathbb{N}$.) Hopefully you have seen that $\mathbb{N} \times \mathbb{N}$ is countable, and subsets of countable sets are countable. Therefore the set $A = \{ (m,n) \in \mathbb{N} \times \mathbb{N} : m < n \}$ is countably infinite. We then take some bijection $f : A \to \mathbb{N}$. (Note that you can actually define such a thing, but that is somewhat unimportant.)

We now assume that there are only countably many graphs with vertex set $\mathbb{N}$, and so we take another bijection $g$ from $\mathbb{N}$ onto this set of graphs. For ease of notation, for every $i \in \mathbb{N}$ we will denote by $E_i$ the edge relation of the graph $g(i)$.

I now define a new graph on $\mathbb{N}$ as follows: The edge relation $E_*$ is defined so that given natural numbers $m < n$ we have that $( m , n ) \in E_*$ iff $( m , n ) \notin E_{f(m,n)}$. Since we have a total list of all graphs on $\mathbb{N}$, then $E_*$ must be $E_j$ for some natural number $j$. Note that if $f^{-1} (j) = (m,n)$ then $(m,n) \in E_*$ iff $(m,n) \notin E_{f(m,n)} = E_j = E_*$: a contradiction!

-
Note that I could have instead opted to pick a bijection $G$ from $A$ onto the set of all graphs on $\mathbb{N}$. The literal conclusion from the contradiction would be that there is no bijection from $A$ onto this set of graphs, but since $A$ is countably infinite, the actual conclusion would remain the same: that this set of graphs is uncountable. –  Arthur Fischer Dec 1 '11 at 21:05
add comment

You still haven't specified the question in a rigorous way. If you are talking about graphs $(V,E)$ with $V$ at most countable and $E\subset V\times V$ then the sketch of the proof is the following. Consider any infinite sequence $(x_k)_{k=1}^n$ of zeros and ones. To this sequence you assign the unique graph with $V = \mathbb N\cup\{0\}$ such that $(0,k)\in E$ iff $x_k =1$.

Since the set of such sequences is uncountable, the set of countable graphs is uncountable as well. The set of all finite graphs is countable though since the set of all graphs with #$V = n$ is finite.

-
add comment

The collection of all graphs is not even a set. And there are uncountably many graphs on one vertex.

-
Can you explain this a bit more? Are you saying this because we can label the vertex with uncountably many labels? If we're talking graphs (no multiple edges, no loops, nondirected), and only counting equivalence classes under isomorphism, there is just one, right, the empty graph? And, with this definition, we'd have countably many finite graphs overall, right? Back to the one vertex case, if we allow loops, there could be countably many, because we could have 0 loops, 1 loop, 2 loops, 3 loops, and so on. Where do uncountably many come from? –  Graphth Dec 2 '11 at 21:58
A graph is a pair consisting of a vertex set, $V$ say, and an edge set $E$, where the elements of $E$ are unordered pairs of vertices. The collection of all possible vertex sets is a proper class, not a set. This is because the vertices can be anything at all, there are uncountably many vertices available and two graphs are equal only if they have the same vertex set and the same edge set. In practice we do not want the number of graphs, but the number of isomorphism classes of graphs. The number of isomorphism classes is countable. –  Chris Godsil Dec 3 '11 at 3:13
Cool, that makes more sense. Thanks for the help. –  Graphth Dec 3 '11 at 16:30
add comment

Even if you want the set of all graphs on countable sets up to isomorphism, you can take any subset $S\subset\mathbb N$ and write it ordered as $a_1<a_2...$ then create a graph with cliques of size $\{2+a_1, 2+a_2,..\}$ and the resulting graphs are not isomorphic for distinct $S,S'$.

-
add comment