Does the group growth rate limit the number of edges going out of a vertex in its Cayley graph?

Question

The growth rate of a group $B_n(G, T)$ is based on the number of vertices that can be reached from a given one by $n$ steps along an edge in the Cayley graph of the group, where $G$ is the group (or its graph) and $T$ is a set of generators of the group or the respective edges in the graph.

I learned here that $\mathbb{Z}^3$ has a growth rate of the order of $n^3$. Looking at graphs (not necessarily Cayley), I wonder if the following exists for an arbitrary but fixed $n_0\in\mathbb{N}$:

1. The graph is infinite.
2. The graph is symmetric.
3. The growth rate is of order $n^3$.
4. Each vertex has $m>=n_0$ edges.

This exists for $m=n_0=6$ per the tiling of three dimensional space with cubes.

Question: Is the following proof that I can find an $m$ for any $n_0$ correct? (Risking a yes/no question as per this meta post.)

Define a graph $G_1 = (V, E_1)$ such that $V=\mathbb{Z}^3$. The vertices can be considered centers of cubes that tile $\mathbb{R}^3$. Define an edge of the graph for each two cubes that "touch" directly, either on sides, edges or corners. Consider a Rubik's Cube, where center cube has an edge to all surrounding cubes. More formally, let $v, w\in V$ be connected, i.e. $\{v, w\}\in E_1$, if they are "direct neighbors" along any coordinate combination, i.e. $v-w \in \{-1,0,1\}^3$ and $v\neq w$.

The ball $B_n(G_1, v)\subset V$ shall be the set of nodes reachable from $v$ with a minimal path length of $\leq n$. For $n=1$ this is again like looking at Rubik's Cube and $|B_1(G_1, v)| = 3^3 = 27$. In general the number of elements in the ball $B_n$ is an ever bigger "Rubik's Cubes" albeit always with an odd number of cubes along one dimension: $$|B_n(G_1, v)| = (1+2n)^3$$ So the growth rate is of the order of $n^3$, but we don't yet have an arbitrary large number of neighbors for a given vertex.

Now we define the graph $G_k=(V,E_k)$ based on $G_1$ such that we add edges to $E_1$ from $v$ to every vertex $w\in B_k(G_1, v)\setminus E_1$, so that now all vertices of that ball are direct neighbors of $v$.

In the new graph, we have $$ |B_n(G_k, v)| = (1+kn)^3$$ which still is a growth rate of order $n^3$, but since we are free to choose $k$, we can create a symmetric graph of order $n^3$ were each vertex has arbitrary many edges going out.

Specific head-scratchers

1. Is $|B_n(G_k, v)|$ correct?
2. Is the constructed graph $G_k$ really symmetric?

Answer 1

Yes, this is a fine construction. (Or: no, the group growth rate doesn't limit the degree of vertices.) A generalization of this: if you find an infinite graph $G$ which is symmetric, connected, and has a growth rate $|B_n(G,v)| = O(f(n))$, then we can let $G^k$ be the graph with an edge $vw$ whenever $d(v,w) \le k$ in $G$. We can make $G^k$ have arbitrarily large minimum degree, and still have$ |B_n(G^k,v)| = O(f(n))$.

We can even find a Cayley graph that will have the property you want. Take the group $\mathbb Z^3 \times \mathbb Z_2^k$, and take $T$ to be a set of $3+k$ generators corresponding to each of the factors. Then each vertex of the Cayley graph will have degree $6+2k$, and the growth rate will be $O(n^3)$. (The idea is that after $n$ steps, there are $O(n^3)$ possibilities for the element of $\mathbb Z^3$ we have, and at most $2^k = O(1)$ possibilities for the element of $\mathbb Z_2^k$.)

Or, we could even take $\mathbb Z^3$, but with a different, larger generating set. The growth rate will still be $O(n^3)$, because if no generator lets you change any coordinate by more than $M$, then after $n$ steps we are limited to a cube with $(2Mn+1)^3$ vertices in it. The degree of each vertex is twice the number of generators.