5
$\begingroup$

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.

  • 0
    @Araf Of course,we could be reasonably practical and work in NBG models of set theory instead of ZFC. But for some reason,a lot of mathematicians have a problem with this.Frankly,I've never understood why as long as we used a version of NBG that's a conservative extension of ZFC. Would make category theory a whole lot less mysterious,too.2011-12-01

5 Answers 5

2

Each of the existing answers proceeds based on more specific interpretations of the general "set of all graphs."

Consider this more specific version: is the set $G$ of all unweighted graphs on finite sets (each $g \in G$ has a finite set $V$) up to isomorphism a countable set? I'd like to show that this set is countably infinite via a bijection with a subset of all binary strings.

There is a finite number of unweighted isomorphic graphs with $n$ vertices, where $n \in ℕ$. The set of all possible edge permutations of an $n$-vertex graph, then, is $\wp M$, where $M$ is the set of all possible edges on an $n$-vertex graph. Because $|M|= n \times n$, $|\wp\ M| = 2^{n \times n}$, which is the number of unweighted isomorphic graphs with $n$ vertices.

This is finite, but because $n \in ℕ$, we can conclude that $G$ is infinite: $|G| = \sum \limits_{n=1}^ \infty 2^{n \times n}$.

To conclude that our set $G$ is countable, we can construct a bijection with another countable set. Because we're only considering finite graphs we can construct an adjacency matrix to uniquely represent each $g \in G$, which will contain some $n \times n$ permutation of weights 0 (no edge) and 1 (edge). If we catenate the rows of such an adjacency matrix, we get a finite binary string of length $n \times n$ for each $g \in G$.

Let's define $A$ as the set of adjacency strings for each $g \in G$. We know that $G\xrightarrow{\rm 1:1,onto}A$.

Because $A \subset$ the countable set of all finite binary strings, $A$ is countable. Because we've described a bijection between $G$ and $A$, we conclude $G$ is countably infinite.

What if we introduce weighted graphs? If we define a finite set of possible edge weights in graphs in $G$, the bijection holds (e.g. if a graph $g$ can have $w$ weights, we can describe it with a base-$(w+1)$ string).

9

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.

7

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

  • 0
    Cool, that makes more sense. Thanks for the help.2011-12-03
5

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!

  • 1
    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.2011-12-01
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 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'.