# Cayley graph with minimal generating set?

The answer to this question could be trivial !

Definition:

Let $G$ be a group and $S$ a symmetric subset of $G$ (i.e., $s \in S$ iff $s^{ −1} \in S$), the Cayley graph $Cay(G; S)$ of $G$ w.r.t. $S$ is the graph whose vertex set is $G$ and $a \in G$ is connected to $\{sa| s \in S\}$. This is a $k$-regular graph with $k = |S|$. It is connected iff $S$ generates $G$.

Connected Components:

A graph $Cay(G,S)$ can be constructed even if the set $S$ does not generate the group $G$. However, it is disconnected graph. In this case, each connected component of the graph represents a coset of the subgroup generated by $S$. Thus by Lagrange theorem the number of connected components is $$\frac{|G|}{|\left<S\right>|}$$

Minimal Generating Set Case:

Let $S=\{s_1,\ldots,s_k\}$ be minimal generating set of $G$, and let $S'=S\setminus\{s_k, s^{-1}_k\}$. It is easy to see that $Cay(G,S')$ is spanning subgraph of $Cay(G,S)$, and that the number of connected components of $Cay(G,S')$ and $Cay(G,S)$ is respectively $\frac{|G|}{|\left<S'\right>|}$ and 1.

Question?

Let $S$ and $S'$ be defined as in the previous part. Let $\left<S'\right>x$, and $\left<S'\right>y$ be the vertices of two connected components of $Cay(G,S')$. I'm pretty sure that in $Cay(G,S)$ there exists edge between certain vertex $x'\in \left<S'\right>x$ and another vertex $y'\in \left<S'\right>x$, but I do not know how to prove it. In other words, how can we prove that between any two connected components of $Cay(G,S')$ there exists edge in $Cay(G,S)$?

Any idea will be useful!

• I think the answer is "no". For example, consider the cross product of the cyclic groups of order $2$ and $4$: $C_4\times C_2=\langle a, b; a^2, b^4, [a, b]\rangle$. Let $S=\{a, b\}$ and $S^{\prime}=\{a\}$. Then there are $4$ connected components corresponding to $S^{\prime}$, and the component containing the identity $1$ is of distance $2$ from the component containing $b^2$. (Think of the components lying at the vertices of a square.) – user1729 Mar 31 '16 at 10:24
• @user1729 Could you please tell me what does $[a,b]$ mean? – M.Badaoui Mar 31 '16 at 10:34
• I've addressed this in my answer, below. Short answer is: you can ignore it. Longer answer: it means $aba^{-1}b^{-1}$, so it implies $aba^{-1}b^{-1}=1$, and so $ab=ba$. So $a$ and $b$ commute ($[u, v]$ is called a "commutator"). – user1729 Mar 31 '16 at 10:39

For example, consider the cross product of the cyclic groups of order $2$ and $4$: $C_4\times C_2=\langle a, b; a^2, b^4, [a, b]\rangle$*. Let $S=\{a, b\}$ and $S^{\prime}=\{a\}$. Then there are $4$ connected components corresponding to $S^{\prime}$, and the component containing the identity $1$ is of distance $2$ from the component containing $b^2$. (Think of the components lying at the vertices of a square.)
I think this is made even clearer by considering the infinite group $H\times \mathbb{Z}$ with $S=\{X, b\}$ where $b$ is the generator of the $\mathbb{Z}$ factor. (Here $H$ is just any group.) Now look at the connected components associated to $H$. These components correspond to the cosets $Hb^i$, and the distance in the graph between the cosets $Hb^i$ and $Hb^j$ is simply $|i-j|$. These components lie in a "line", and we can loop the line round to give a homomorphism onto $H\times C_n$ where $C_n$ is the cyclic group of order $n$. This is what is going on in the first paragraph - $n=4$ is the minimum for the distance to be greater than $1$.
*(This $\langle -;-\rangle$ notation is called a presentation, and I am simply using it as a neat way of saying $a$ generates the $C_2$ factor and $b$ generated the $C_4$ factor. The notation $[a, b]$ means $aba^{-1}b^{-1}$, which implies that $a$ and $b$ commute (that is, $ab=ba$) so I have a cross product.)
• See the bottom paragraph. Short answer is: you can ignore it. Longer answer: it means $aba^{-1}b^{-1}$, so it implies $aba^{-1}b^{-1}=1$, and so $ab=ba$. So $a$ and $b$ commute ($[u, v]$ is called a "commutator"). – user1729 Mar 31 '16 at 10:41