$\mathbf{Question:}$ Let $G$ be a finite group and $g\in G$ be an element of even order. Prove that the elements of the group can be coloured using two colours in such a way that $x$ and $gx$ have different colours $\forall x\in G$.
$\mathbf{Attempt:}$ By Lagrange's theorem, $G$ is of even order, say $2n$. We "bifurcate" $G$ into two equal halves, say $A= \{x_1,x_2,…,x_n\}$ and $B=\{y_1,y_2,…y_n\}$, where $x_1=e$ and $y_i=gx_i, \ 1\leq i \leq n$. So, $y_1=g$ , $A\cup B=G$ and $A\cap B=\emptyset$
Clearly, $\phi_1:A \to B$ defined by $\phi_1(x_i)=gx_i$ is an injection, consequently, it is a bijection.
Again, $\phi_2:B \to A$ defined by $\phi_2(y_i)=gy_i=g^2x_i$ sends $x_i's$ back to $A$.
If we give the elements of $A$ the same colour and the elements of $B$ another, the colouring is done.
Is this correct? Kindly Verify.
Best Answer
Well, but what if $g$ does not generate the whole group?
What is not a priori clear is whether what you give as the partitioning of $G$ into two sets is indeed well-defined. Indeed, you were asked to show that there is infact such a partition that is well-defined. There of course would NOT be well-defined parition if $g$ had odd order.
This is now I would do this: First partition $G$ into right cosets $X_1,X_2, \ldots X_r$ of $\langle g \rangle$ i.e., for each $j$ there is an $x_j \in G$ such that $X_j =\{g^ix_j; $ $i \in \mathbb{Z}\}$ [fix such an $x_j$ for each $j=1,2,\ldots, r$]. Next parition $G$ into two sets $G_1$ and $G_2$ as follows:
(A) For each $y \in X_j$, write $y=g^ix_j$ for some integer $i$, where $x_j$ is as specified above, and $i$ is a nonegqative integer no greater than ord$(g)-1$. Note that there is exactly one such way to respresent each $y \in G$ as above. Now writing $y=g^ix_j$ as above, let exp$(y)$ be the integer $i$. Then iff exp$(y)$ is odd then put $y$ into $G_1$ and if exp$(y)$ is even then put $y$ into $G_2$. As there is exactly one way to write each $y \in G$ as above, this partitioning of $G$ into $G_1$ and $G_2$ is well-defined.
[So what I said above is I think what you were trying to get at, but what was needed was for you to take care to specify the partitioning precisely.]
So now it suffices to show that $y \in G_1 \Leftrightarrow gy \in G_2$ for each $y \in G$, and then we are done.To this end, write $y=g^ix_j$ as specified above. Then exp$(g)=i$, and $gy=g^{i+1}x_j$ if $i < $ord$(g)-1$ and $g(y)=y^0x_j$ if $i=$ord$(g)-1$. So exp$(gy) = $exp$(y)+1$ if exp$(y) < $ ord$(g)-1$, and exp$(gy)= 0$ if exp$(y)=$ord$(g)-1$. But then as ord$(g)$ is even it follows that exp$(gy)$ is even iff exp$(y)$ is odd, and so $gy$ must be put into $G_2$ if $y$ is put into $G_1$ by (A) above.
If you are familiar with Cayley graphs then the Cayley graph where the vertices are elements of $G$ and where $x$ and $y$ form an edge iff $y \in \{gx, g^{-1}x\}$ is either a collection of vertex-disjoint cycles of length ord$(g)$ [if ord$(g) \ge 3$], or is a perfect matching [if ord$(g)=2$]. This graph is bipartite if ord$(g)$ is even. Then a proper-2-colouring of this graph corresponds to a coloring where $x$ and $gx$ are given different colors for each $x \in G$. Such a proper 2-colouring exists if ord($g$) is even, as we already observed, this graph is then bipartite.