The question is exactly as in the title. To be more precise, let $G$ be a fin. gen. group and let $C(G,S)$ be its Cayley graph (where $S$ is a set of generators of $G$ such that $S^{-1}=S$). Obviously to different $S$ can correspond different graphs: for example, $C(\mathbb{Z}^2,\{\pm(1,0),\pm(0,1)\})$ and $C(\mathbb{Z}^2,\{\pm(1,0),\pm(0,1),\pm(1,1)\})$; the first is bipartite and the second is not. My question is whether this phenomenon is general, i.e. if we can always find a nonbipartite Cayley graph.
My attempt:
It's not difficult to prove that $C(G,S)$ is nonbipartite iff there is no subgroup $B$ of index $2$ of $G$ which does not intersect $S$. However, this does not really help me as it translates the problem to a group-theoretic one that I don't really see how to approach.
Suggestions would be very much appreciated.