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