Is it true that for any integer $k\geq 3$ there are $\aleph_0$ many connected countably infinite, pairwise non-isomorphic $k$-regular graphs?


closed as off-topic by user44191, Ben Barber, Chris Godsil, Pace Nielsen, Dima Pasechnik Mar 10 at 9:36

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – user44191, Ben Barber, Chris Godsil, Pace Nielsen, Dima Pasechnik
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$ – YCor Mar 6 at 17:38

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.

  • 4
    $\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$ – Florian Lehner Jul 7 '18 at 18:11
  • $\begingroup$ Nice! @FlorianLehner $\endgroup$ – David Roberson Jul 7 '18 at 18:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.