Can two non-isomorphic groups have the same Cayley graphs?

Question

The question I was originally thinking about was:

Can $T_3$, the three-regular tree (the infinite tree with each vertex having valency 3) be the Cayley graph of some group with some generating set?

Since $T_2$ is $\text{Cay}(\mathbb Z, \{1\})$, and $T_4$ is $\text{Cay}(F_2=\langle a,b \rangle,\{a,b\})$, I thought for $T_3$ I could let $a,b,c$ be the three edges coming out of each vertex (in the case of $F_2$ the edges were $a,a^{-1},b,b^{-1}$ but here we can't get $3 $ edges if we allow inverses of the generators to be different from themselves).

So I think $T_3=\text{Cay}(\mathbb Z_2 * \mathbb Z_2 * \mathbb Z_2 , \{a,b,c\})$.

But now I could use the same logic and say $T_4= \text{Cay}(\mathbb Z_2 * \mathbb Z_2 * \mathbb Z_2 * \mathbb Z_2 , \{a,b,c,d\}) = \text{Cay}(F_2, \{s,t\})$.

Firstly, whatever I've written so far, is it at least correct?

If it is, can two non-isomorphic groups have the same Cayley graph?

(I think they can, because I really doubt $F_2 \cong \mathbb Z_2 * \mathbb Z_2 * \mathbb Z_2 * \mathbb Z_2$).

Answer 1

This answer assumes that by the Cayley graph $\operatorname{Cay}(G, S)$ you mean the directed and labelled graph with vertex set $G$ and where we can think of the edge set as the set of ordered triples $$\{(g,h,a)\in G\times G\times S\mid ga=h\}.$$ The fact that the triples are ordered corresponds to directed edges. The third component corresponds to a label on the edge.

This definition is the one I am most familiar with, and for example is used in Wikipedia.

It also assumes that by "graph" you allow multiple edges between any given two vertices (some texts call this a "multigraph"). If your definition of graph does not allow this, this your situation essentially reduces to my other answer.

By "removing labels" I mean forgetting the third component of each triple, and also the direction of each arrow, so the unlabelled Cayley graph is the multiset $$\{\{g,h\}\in G\times G\mid \exists\:a\in S\text{ s.t. }ga=h\}.$$ Being a multiset simply means we may have multiple edges between any two given vertices.

---

There are a few questions here. So lets answer them one-by-one.

Can two non-isomorphic groups have the same Cayley graphs?

If we remove the labels on edges, yes. The simplest family of examples is basically that pointed out by Sean Eberhard in the comments: For any group $G$, the Cayley graph $\operatorname{Cay}(G,G\setminus\{1\})$ is a complete graph but where every edge is replaced by two directed edges pointing in opposite directions. As there can be a great many groups of a given order (finite or infinite), this gives non-isomorphic groups with the same unlabelled Cayley graphs.

So I think $T_3=\text{Cay}(\mathbb Z_2 * \mathbb Z_2 * \mathbb Z_2 , \{a,b,c\})$.

No. The Cayley graph looks like $T_3$, if you squint a little, but every edge $e=(u, v)$ has a "reversed" sibling $\bar{e}=(v, u)$ with the same label. The first edge means that $u\cdot a=v$ while the second means that $v\cdot a=u$, so in particular $u\cdot a^2=u$, which is what we'd expect as $a^2=1$.

Can $T_3$, the three-regular tree (the infinite tree with each vertex having valency 3) be the Cayley graph of some group with some generating set?

Again, no. This is because a Cayley graph must have as many incoming edges as outgoing edges; in particular every vertex of $\operatorname{Cay}(G, S)$ has $|S|$ outgoing edges and $|S|$ incoming edges (why?). Hence, every vertex must have even degree. As vertices of $T_3$ have odd degree, it cannot be a Cayley graph.

[Fun fact: If a group acts freely on a tree then it is free. As groups act freely on their Cayley graphs, any group with a tree as its Cayley graph must actually be free. This wasn't used above, but is nice to know anyway :-) ]

Answer 2

There are plenty of interesting examples of this happening! A classical infinite example is $\mathbb Z^2 = \langle a, b | ba = ab \rangle $ and the fundamental group of the Klein bottle $\pi_1(K) = \langle a, b | ba = ab^{-1} \rangle $.

The standard (unlabelled) Cayley graph of both of these groups is a grid, but in the Klein bottle the orientations of edges will alternate in a certain way - see below:

Of course, it is worth noting that $\mathbb Z^2$ is an index-2 subgroup of $\pi_1(K)$, so it makes sense that their structures would appear similar.

Answer 3

This answer assumes that by the Cayley graph $\operatorname{Cay}(G, S)$ you mean the undirected and unlabelled graph with vertex set $G$ and edge set $$\{\{g,h\}\in G\times G\mid \exists \: a\in S\text{ s.t. }ga=h\}.$$ This definition is used in Löh's book Geometric Group Theory: An Introduction, although it seems uncommon.

---

Can two non-isomorphic groups have the same Cayley graphs?

Yes. As Dietrich Burde points out in the comments, under this definition $C_2\times C_2$ and $C_4$ both have the same Cayley graph (a square).

So I think $T_3=\text{Cay}(\mathbb Z_2 * \mathbb Z_2 * \mathbb Z_2 , \{a,b,c\})$.

Yes. A rough argument is that every vertex of this Cayley graph has degree $3$, and as it is a free product the only loops in the Cayley graph correspond to products of $a^2$, $b^2$, $c^2$ and their conjugates, but none of these actually give loops in the graph. Hence, your graph is actually a tree. (For a more formal proof, I'd look to Bass-Serre theory as this tree is the Bass-Serre tree of this group.)