Is the Set of all Graphs Countable?

Question

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.

Answer 1

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!

Answer 2

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.

Answer 3

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

Answer 4

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'$.