Is the set of trees over countably infinite vertices countable or uncountable?

Question

Suppose we consider two graphs to be the equivalent if they are isomorphic. The idea is that if we relabel the vertices of a graph, it is still the same graph. Using this definition of “being the same graph”, can you conclude that the set of trees over countably infinite vertices is countable?
I know that for any isomorphism $f$ and any vertex $v$, $v$ and $f(v)$ have the same degree.

Answer 1

Suppose the binary expansion of a real number $r\in[0,1]$ is given by $0.b_1b_2b_3\dots$. Based on this real number, define a tree with countable-infinitely many vertices as follows:

• There are four special vertices $a,b,c,d$ such that $a$ is connected to $b,c,d$
• $a$ is also connected to $v_0$, one end of a semi-infinite path $v_0v_1v_2\dots$
• $b_i=1\iff$there is an extra edge and vertex coming out of $v_i$

This construction is a bijection between the set of real numbers and a subset of the trees with countable-infinite vertices. Therefore, the latter subset as a whole is uncountably infinite.

Answer 2

There are as many isomorphism classes as the cardinality of $\Bbb R$. To see a family of $\beth_1$ non-isomorphic trees on $\aleph_0$ vertices, start by considering $$0- 1- 2- 3- 4- 5- \cdots$$

Then, consider $S\subseteq \Bbb N$ and, for all $x\in S$, attach to the node $[x]$ other $x+2$ brand new vertices all at distance $1$ from $x$. For each $S$, you obtain a countable tree. No two of these trees are isomorphic, because $n\in S$ if and only if either $n=0$ and the corresponding tree has a vertex of degree $3$, or $n>0$ and the corresponding tree has exactly one node of degree $n+4$. This is an invariant.

The other bound comes from set-theoretic considerations.

Answer 3

Probably the simplest way to do this is to just look at the set of degrees of the tree. This is an isomorphism invariant. It is a subset of the positive integers, and apart from $\varnothing$ and $\{1\}$, any subset is possible.

To see this, order your set $d_1< d_2<\cdots$. If it is finite, with $r$ elements, set $d_n=d_r$ for $n>r$. Now grow a tree starting from a single root vertex. Give the root vertex $d_1$ offspring, all vertices in the next layer $d_2-1$ offspring, the next layer $d_3-1$ offspring, and so on. Since the set is not $\{1\}$, we have $d_1\geq 1$ and $d_n\geq 2$ for all $n\geq 2$, so this gives an infinite tree. The $n$th layer vertices have degree $d_n$.

Answer 4

In fact, for any infinite cardinal $\kappa$, there are $2^\kappa$ nonisomorphic asymmetric trees of order $\kappa$. (A graph is asymmetric if it has no nontrivial automorphism,) For a proof see my answer (not the accepted answer) to this Math Overflow question.