Clear up definition of cayley graph

Question

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.

Answer 1

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$.

Answer 2

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.)

Answer 3

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.