0
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • 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
  • $\begingroup$ Nice! @FlorianLehner $\endgroup$ Jul 7, 2018 at 18:12

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