Is it true that for any integer $k\geq 3$ there are $\aleph_0$ many connected countably infinite, pairwise non-isomorphic $k$-regular graphs?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ For each $k\ge 3$ there are $2^{\aleph_0}$ non-isomorphic graphs of valency $k$ (necessarily countable), obtained as Cayley graphs of the same number of pairwise non-quasi-isometric finitely generated groups. But of course without transitivity assumption it's much easier. $\endgroup$– YCorMar 6, 2019 at 17:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Take an $n$-cycle, add an infinite tree of the right degree at each vertex of the cycle (the vertex on the cycle having degree 2 less in the tree than the other vertices of the tree). This has only one cycle and it is of length $n$. So the graphs you get for two different values of $n$ are non-isomorphic.
-
5$\begingroup$ Start with a "chain of cycles", i.e. cycles $(C_n)_{n \in \mathbb N}$, with an edge from $C_n$ to $C_{n+1}$, and adapt the attached trees accordingly. Then altering the cycle lengths even gives you $2^{\aleph_0}$ many non-isomorphic such graphs. $\endgroup$ Jul 7, 2018 at 18:11
-