# Group Presentations and Cayley graphs

I am trying to understand group presentations and Cayley graphs, and have a few questions I am confused about.

Let $G=(V,E)$ be a finite $d$-regular graph that is known to be a Cayley graph for the group $\Gamma$ and a symmetric generating set $S=\{s_1,s_2,\dots,s_d\} \subset \Gamma$. Now it is clear that any cycle (or a closed walk) in the graph can be expressed as a word over $S$ that evaluates to the identity in the group $\Gamma$. The converse is also true: any word over $S$ that evaluates to the identity element in $\Gamma$ can be used to construct a cycle in the graph $G$.

Let $R$ be the set of all words over $S$ that evaluate to the identity (in other words, $R$ is the set of all cycles in $G$). The set $R$ is closed under concatenation of words, and is a subgroup of the free group $Free(S)$.

Is it necessarily true that $$\Gamma \cong Free(S)/R$$ that is, is the quotient of the free group by the subgroup of relations formed using cycles in the Cayley graph isomorphic to the group $\Gamma$? Intuitively, it seems reasonable to think so. Almost obvious, (UPDATE: it is obvious!) which brings me to the main question.

Suppose $G=(V,E)$ is again an $n$-vertex $d$-regular graph. But now we do not know if it is a Cayley graph. Choose an arbitrary orientation of each edge and trivially use a larger label set $S=\{s_1,s_2,\dots,s_{|E|}\}$ to associate each oriented edge with a corresponding symbol, and its reverse orientation with an inverse of that symbol. That is, we associate each edge with two (oppositely) oriented (or directed) edges and associate them with a symbol $s$ and $s^{-1}$.

Now again we can consider the free group $Free(S)$ and a subgroup $R$ generated by words over $S$ that correspond to cycles in the graph.

Is $R$ normal? Are there combinatorial conditions on the graph that make $R$ normal?

Suppose $R$ is normal. What can we say about the group $Free(S)/R$? Is there any connection between the graph $G$ and the group $Free(S)/R$?

Suppose, as before, $G$ is a Cayley graph of a group $\Gamma$. Then is the above quotient group isomorphic to $\Gamma$?

I apologize if this question is too broad. I'll try to make it more precise in updates based on feedback. But I'll be happy even with relevant references.

• Thanks. I did realize it soon after posting the question, but left it to serve as a teaser to motivate the actual question after that. Maybe I'll edit it now. – BharatRam Aug 2 '17 at 16:57
• If $c\in R$ is any cycle and $e$ any edge then $e^2ce^{-2}$ will not be a cycle, because the target and source of $e$ are different (unless you're allowing loops in your graph). You could define $R$ to be the normal subgroup generated by the cycles. – anon Aug 2 '17 at 17:16
• Yes, I had initially written it wrongly having the Cayley picture in mind, but noticed that during my last edit itself where I changed "the subgroup of cycles" to "subgroup generated by cycles". Writing the question itself clears up many confusions :) but the core concept is still unclear. – BharatRam Aug 2 '17 at 17:38

Let $R$ be the normal subgroup generated by cycles in $G$. If you take $\Gamma \subset G$ to be a spanning tree, then the generators corresponding to edges in $\Gamma$ will generate all of $\text{Free}(S)/R$. I'm pretty sure that, since there are no cycles in $\Gamma$, there are no extra relations among those generators$^{1}$, which would mean you have $\text{Free}(S)/R \cong F_{|V(G)| - 1}$, the free group on $|V(G)| - 1$ generators (Assuming $G$ is connected).
$^{1}$: If $C$ is the set of cycles, $\langle \cdot \rangle$ denotes normal subgroup generated by a set (so $\langle C \rangle = R$), and $H$ the subgroup of $\text{Free}(S)$ generated by edges in $\Gamma$, I want to say that $H \cap \langle C \rangle = \langle H \cap C \rangle$. I know this isn't true in general, but perhaps in this case it's easy to show?