# Does index 2 subgroup imply bipartite Cayley graph?

Let $G$ be a finitely generated group and let $\Gamma=Cay(G, S)$ be the Cayley graph of $G$ with respect to some generating set $S$.

If there exists $S$ such that $\Gamma$ is bipartite, then $G$ has an index $2$ subgroup (e.g. generated by all words of even length). Does the converse hold? (I'd guess not, but I don't know generic invariants allowing to show that a group does not admit a bipartite Cayley graph)

• If $S=G$, then $\Gamma$ is a clique; hence not bipartite, regardless of whether $G$ has index-$2$ subgroups.
– Seva
Mar 20, 2014 at 11:51
• If $H$ has index $2$ in $G$, then just take $S$ to be any (finite) generating set of $G$ none of whose elements lie in $H$. Mar 20, 2014 at 11:56

Is bipartite or admits bipartite? To the first question the answer is obviously "no", to the second, obviously "yes". Let $H\subset G$ be an index $2$ subgroup; take generators $h_1,h_2,\ldots$ for $H$ and one more generator $g\notin H$. In this generating set, the Cayley graph is not bipartite (with a few possible exceptions). However, if you switch to $g, h_1g, h_2g,\ldots$, this is also a generating set and all generators have "odd degree", so the graph is obviously bipartite.
• Sorry, how come all the elements $g, h_1g, h_2g, \ldots$ have 'odd degree'. Could you elaborate? May 8, 2022 at 17:47