I am searching now for the most explicative and easy understand in this level (I am a second year student) proof of the following result:
A Cayley graph is connected iff S generates G
where G is a group and $S \subset G$ is a set of group of elements such that the identity $1_G \notin S$ .
Can someone post the proof or where do I can get it please :). Thanks a lot in advance :)
If the cayley graph $\Gamma=(G, S)$ is connected, then there exists a directed path between any two vertices. We want to show that the set $S$ generates $G$. To generate $G$ means that we can write any element of $G$ as a product of elements in $S$.
Let $g$ be any element of $G$. Then there is a path from $1$ (the identity in $G$) to $g$. An edge in $\Gamma$ from $u$ to $v$ means that there is an element $s\in S$ so that $us=v$. So the path from $1$ to $g$ corresponds to a sequence of steps (obtained by multiplication of elements in $S$). $1s_{1}s_{2}...s_{n}=g$ is the path from $1$ to $g$. Hence $g$ can be written as a product of elements in $S$, specifically $s_1 s_2 ... s_{n}$.
For the other direction. Suppose that $S$ generates $G$. We need to show that there is a directed path from any $u$ to any other $v$ in $\Gamma$. Note that $u^{-1}v\in G$ so $u^{-1}v$ can be written as a product of elements in $S$, say $u^{-1}v = s_1 s_2 ... s_{n}$. Then, that product describes the path from $u$ to $v$ in the Cayley digraph. Specifically, $u (s_1 ... s_n)=u(u^{-1}v)=v$, a path from $u$ to $v$.