# Clear up definition of cayley graph

I have come across two definitions of Cayley graphs, both very similar but one being more general.

I have been working with the more general definition which is:

A Cayley graph of a group 􏰎$X$ with a subset􏰐 $S \subset X$ 􏰏, is defined by taking X to be the vertex set of the Cayley graph, with directed edges $(g,h)$ whenever $gh^{-1} \in S$.

However in other texts i have read that $S$ needs to be a generating set of $X$, this stronger version implies that the Cayley graph will be connected.

I understand that the cayley graph depends on the choice of $S$ as this defines the edges and intuitively get why the graph would be connected if the set generates the group, however i am struggling to prove it formally. I want to be able to link the two definitions in my notes by proving the graph is connected.

any help on providing a proof as to why the graph would be connected would be much appreciated, thank you.

• There are some characters in the question that I cannot read, but your observation is correct. If $S$ can be an arbitrary subset of $X$, then the resulting graph may not be connected. In the other case, the graph will always be connected. There are also (sometimes) definitions that require that if $g\in S$ then $g^{-1}\in S$. Commented Apr 8, 2015 at 21:00
• @TravisJ how can i formally show that it is also connected, as the text i have read it in just states it without proving Commented Apr 8, 2015 at 21:07
• I agree with @TravisJ your observations seem very correct. Well done Commented Apr 8, 2015 at 21:12
• I wrote up the details. A note, connected here means strongly connected (i.e. a directed path from any $u$ to any $v$). Commented Apr 8, 2015 at 21:20
• @TravisJ perfect, very clear thank you ! Commented Apr 8, 2015 at 21:50

To show that $\Gamma(G)$ is connected, you need to be able to generate a path from $v$ to $u$ for any $v, u\in G$. Think of a step from $v$ as a multiplication of $v$ by some element in $S$. If you end up at vertex $w_1$ then you multiplied $v$ by $v^{-1}w_{1}\in S$. A path that takes you from $v$ to $u$ will look like: $v, w_1, w_2, ..., w_k, u$ and the multiplications that you did, in sequence were $$(v^{-1}w_{1})(w_{1}^{-1}w_{2})...(w_{k}^{-1}u)=v^{-1}u$$ The question then is, can you write $v^{-1}u$ as a product of elements in $S$? If $S$ generates $G$ then you can (for any $v^{-1}u\in G$). If there is any pair for which you cannot write such a product, i.e. a $v, u\in G$ so that there is no finite product of elements in $S$ that make $v^{-1}u$ then $S$ cannot generate $G$ since it cannot generate the element $v^{-1}u$.

• would the distinction of left and right multiplication by elements in S dictate the direction of the edge, as in this proof you have used right multiplication with an element in S, and in my definition used $gh^{−1} \in S$. which would imply that the directed edge (g,h) occurs if $g =sh$ Commented Apr 9, 2015 at 0:25
• @PeterA, Left multiplying (as you suggest) just creates the edges pointed in the other direction, a path from $u$ to $v$ instead of from $v$ to $u$. Commented Apr 9, 2015 at 1:26
• Is it true that if $\Gamma(G)$ is not connected then each connected component corresponds to cosets of $\langle S \rangle$ in $G$?
– old
Commented Aug 22, 2018 at 18:01

I believe that the consensus among graph theorists working with Cayley graphs is that the connection set is not required to be a generating set; thus a Cayley graph does not have to be connected. So we have Sabidussi's theorem that a graph $X$ is a Cayley graph if and only if there is a subgroup of its automorphism group that acts regularly on $V(X)$.

Note that this theorem is stated in this form on the wikipedia page, even though they offer the "wrong" definition of Cayley graph.

If you're trying to formally prove that the graph is connected if and only if $S$ forms a generating set for $G$, you should try to directly prove the following:

• Two vertices $g,h$ are connected by a path if and only if $gh^{-1}$ is in the subgroup generated by elements of $S$.

Here I am interpreting a path as a finite chain of edges, not necessarily pointing in the same direction. (This may very well be nonstandard.)