Return to Answer

Let's call a graph asymmetric if it has no nontrivial automorphism. It is stated as Lemma 5 on p. 165 of F. Galvin, G. Hesse, and K. Steffens, On the number of automorphisms of structures, Discrete Math. 24 (1978), 161–166 that for each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$. Concerning the proof the authors say only that it "can be proved by induction on $\kappa$". I guess their construction is something like the following.

Lemma. There are infinitely many nonisomorphic asymmetric finite trees.

Proof. For each integer $n\ge7$, the star $K_{1,3}$ has an asymmetric subdivision with $n$ vertices.

Theorem. For each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$.

Proof. We use induction on $\kappa$. Let $\kappa$ be an infinite cardinal. It follows from the lemma if $\kappa=\aleph_0$, or from the inductive hypothesis if $\kappa\gt\aleph_0$, that there are (at least) $\kappa$ nonisomorphic asymmetric trees of cardinality less than $\kappa$. Choose a set $\mathcal T$ of $\kappa$ nonisomorphic asymmetric trees, each of cardinality less than $\kappa$. Given any set $\mathcal S\subseteq\mathcal T$ with $|\mathcal S|=\kappa$ we construct an asymmetric tree $T_\mathcal S$ of cardinality $\kappa$ by taking a new vertex $v$ and edges joining $v$ to one vertex of each tree in $\mathcal S$. To recover $\mathcal S$ from $T_\mathcal S$ we simply delete the unique vertex of degree $\kappa$, and get a forest whose connected components are the elements of $\mathcal S$.

Let's call a graph asymmetric if it has no nontrivial automorphism. It is stated as Lemma 5 on p. 165 of F. Galvin, G. Hesse, and K. Steffens, On the number of automorphisms of structures, Discrete Math. 24 (1978), 161–166 that for each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$. Concerning the proof the authors say only that it "can be proved by induction on $\kappa$". I guess their construction is something like the following.

Lemma. There are infinitely many nonisomorphic asymmetric finite trees.

Proof. For each integer $n\ge7$ the star $K_{1,3}$ has an asymmetric subdivision with $n$ vertices.

Theorem. For each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$.

Proof. We use induction on $\kappa$. Let $\kappa$ be an infinite cardinal. It follows from the lemma if $\kappa=\aleph_0$, or from the inductive hypothesis if $\kappa\gt\aleph_0$, that there are (at least) $\kappa$ nonisomorphic asymmetric trees of cardinality less than $\kappa$. Choose a set $\mathcal T$ of $\kappa$ nonisomorphic asymmetric trees, each of cardinality less than $\kappa$. Given any set $\mathcal S\subseteq\mathcal T$ with $|\mathcal S|=\kappa$ we construct an asymmetric tree $T_\mathcal S$ of cardinality $\kappa$ by taking a new vertex $v$ and edges joining $v$ to one vertex of each tree in $\mathcal S$. To recover $\mathcal S$ from $T_\mathcal S$ we simply delete the unique vertex of degree $\kappa$, and get a forest whose connected components are the elements of $\mathcal S$.

Let's call a graph asymmetric if it has no nontrivial automorphism. It is stated as Lemma 5 on p. 165 of F. Galvin, G. Hesse, and K. Steffens, On the number of automorphisms of structures, Discrete Math. 24 (1978), 161–166 that for each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$. Concerning the proof the authors say only that it "can be proved by induction on $\kappa$". I guess their construction is something like the following.

Lemma. There are infinitely many nonisomorphic asymmetric finite trees.

Proof. For each integer $n\ge7$ there is an asymmetric subdivision of the star $K_{1,3}$.

Theorem. For each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$.

Proof. We use induction on $\kappa$. Let $\kappa$ be an infinite cardinal. It follows from the lemma if $\kappa=\aleph_0$, or from the inductive hypothesis if $\kappa\gt\aleph_0$, that there are (at least) $\kappa$ nonisomorphic asymmetric trees of cardinality less than $\kappa$. Choose a set $\mathcal T$ of $\kappa$ nonisomorphic asymmetric trees, each of cardinality less than $\kappa$. Given any set $\mathcal S\subseteq\mathcal T$ with $|\mathcal S|=\kappa$ we construct an asymmetric tree $T_\mathcal S$ of cardinality $\kappa$ by taking a new vertex $v$ and edges joining $v$ to one vertex of each tree in $\mathcal S$. To recover $\mathcal S$ from $T_\mathcal S$ we simply delete the unique vertex of degree $\kappa$, and get a forest whose connected components are the elements of $\mathcal S$.

Let's call a graph asymmetric if it has no nontrivial automorphism. It is stated as Lemma 5 on p. 165 of F. Galvin, G. Hesse, and K. Steffens, On the number of automorphisms of structures, Discrete Math. 24 (1978), 161–166 that for each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$. Concerning the proof the authors say only that it "can be proved by induction on $\kappa$". I guess their construction is something like the following.

Lemma. There are infinitely many nonisomorphic asymmetric finite trees.

Proof. For each integer $n\ge7$, the star $K_{1,3}$ has an asymmetric subdivision with $n$ vertices.

Theorem. For each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$.

Proof. We use induction on $\kappa$. Let $\kappa$ be an infinite cardinal. It follows from the lemma if $\kappa=\aleph_0$, or from the inductive hypothesis if $\kappa\gt\aleph_0$, that there are (at least) $\kappa$ nonisomorphic asymmetric trees of cardinality less than $\kappa$. Choose a set $\mathcal T$ of $\kappa$ nonisomorphic asymmetric trees, each of cardinality less than $\kappa$. Given any set $\mathcal S\subseteq\mathcal T$ with $|\mathcal S|=\kappa$ we construct an asymmetric tree $T_\mathcal S$ of cardinality $\kappa$ by taking a new vertex $v$ and edges joining $v$ to one vertex of each tree in $\mathcal S$. To recover $\mathcal S$ from $T_\mathcal S$ we simply delete the unique vertex of degree $\kappa$, and get a forest whose connected components are the elements of $\mathcal S$.

In fact, for each infinite cardinal $\kappa$, there are $2^\kappa$ nonisomorphic trees of cardinality $\kappa$. The proof is by induction on $\kappa$.

Let $\kappa$ be an infinite cardinal. It follows from the inductive hypothesis if $\kappa\gt\aleph_0$, and is also true for $\kappa=\aleph_0$, that there are (at least) $\kappa$ nonisomorphic trees of cardinality less than $\kappa$. Choose a set $\mathcal T$ of $\kappa$ nonisomorphic trees, each of cardinality less than $\kappa$. Given any set $\mathcal S\subseteq\mathcal T$ with $|\mathcal S|=\kappa$ we construct a tree $T_\mathcal S$ of cardinality $\kappa$ by taking a new vertex $v$ and edges joining $v$ to one vertex of each tree in $\mathcal S$. To recover $\mathcal S$ from $T_\mathcal S$ we simply delete the unique vertex of degree $\kappa$, and get a forest whose connected components are the elements of $\mathcal S$.

P.S. It is stated as Lemma 5 on p. 165 of F. Galvin, G. Hesse, and K. Steffens, On the number of automorphisms of structures, Discrete Math. 24 (1978), 161–166 that for every infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic trees of cardinality $\kappa$ with no nontrivial automorphisms. Concerning the proof the authors say only that it "can be proved by induction on $\kappa$". Presumably their construction is similar to the one presented here, which still goes through if "tree" is replaced everywhere by "tree with no nontrivial automorphisms". To initiallize the construction we need infinitely many nonisomorphic asymmetric trees; these are easily obtained as subdivisions of $K_{1,3}$.

Let's call a graph asymmetric if it has no nontrivial automorphism. It is stated as Lemma 5 on p. 165 of F. Galvin, G. Hesse, and K. Steffens, On the number of automorphisms of structures, Discrete Math. 24 (1978), 161–166 that for each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$. Concerning the proof the authors say only that it "can be proved by induction on $\kappa$". I guess their construction is something like the following.

Lemma. There are infinitely many nonisomorphic asymmetric finite trees.

Proof. For each integer $n\ge7$ there is an asymmetric subdivision of the star $K_{1,3}$.

Theorem. For each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$.

Proof. We use induction on $\kappa$. Let $\kappa$ be an infinite cardinal. It follows from the lemma if $\kappa=\aleph_0$, or from the inductive hypothesis if $\kappa\gt\aleph_0$, that there are (at least) $\kappa$ nonisomorphic asymmetric trees of cardinality less than $\kappa$. Choose a set $\mathcal T$ of $\kappa$ nonisomorphic asymmetric trees, each of cardinality less than $\kappa$. Given any set $\mathcal S\subseteq\mathcal T$ with $|\mathcal S|=\kappa$ we construct an asymmetric tree $T_\mathcal S$ of cardinality $\kappa$ by taking a new vertex $v$ and edges joining $v$ to one vertex of each tree in $\mathcal S$. To recover $\mathcal S$ from $T_\mathcal S$ we simply delete the unique vertex of degree $\kappa$, and get a forest whose connected components are the elements of $\mathcal S$.