# Colouring the elements of a group such that $x$ and $gx$ have different colours.

$$\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.

• Comments are not for extended discussion; this conversation has been moved to chat. Commented Sep 7, 2019 at 16:14

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.

• I have realized what I skipped over Commented Sep 7, 2019 at 5:47
• A small doubt: Why can't we have $g^ix_j=g^mx_n$ where $i$ is even and $m$ is odd ($j$ and $n$ can be anything)? Is this because cosets form a partition? Is this why we can't have it when $n \neq j$ ? ( Evident when $n=j$) Commented Sep 7, 2019 at 6:05
• Because $x_n$ and $x_j$ are not in the same coset of $\langle g \rangle$; there is no $i$ s.t. $g^ix_j = x_n$ which implies that there is no $i$ and $m$ s.t. $g^ix_j=g^mx_n$. So yes, the cosets form a partition.
– Mike
Commented Sep 7, 2019 at 12:29
• Got it. Would revise this answer. Thanks a lot for your time :) I learned something. Commented Sep 7, 2019 at 12:33
– Mike
Commented Sep 7, 2019 at 12:33

Well done! It's a good proof, but it could be improved.

Let's go line-by-line.

By Lagrange's theorem, $$G$$ is of even order, say $$2n$$.

Correct. It might be best to specify that this is due to $$|g|$$ being even.

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$$.

I'm not sure of the terminology but, yes, this is okay.

So, $$y_1=g$$ , $$A\cup B=G$$ and $$A\cap B=\emptyset$$

Yep.

Clearly, $$\phi_1:A \to B$$ defined by $$\phi_1(x_i)=gx_i$$ is an injection, consequently, it is a bijection.

This is fine.

Again, $$\phi_2:B \to A$$ defined by $$\phi_2(y_i)=gy_i=g^2x_i$$ sends $$x_i's$$ back to $$A$$.

I'm not sure why this is necessary, but okay.

If we give the elements of $$A$$ the same colour and the elements of $$B$$ another, the colouring is done.

Yes, that'll do.

• Lovely! I really appreciate your answer :) Commented Sep 5, 2019 at 3:00