How Cheenta works to ensure student success?

Explore the Back-Storycan colour the elements of G with two colours in such a way that x and

gx have different colours for each x ∈ G.

One needs to know the basics of Graph Theory to understand the solution.

- As noted Colouring is a fundamental topic in Graph Theory,so we need to convert the problem into a graph theory problem.
- Consider the elements of the group G as the vertices and consider edges between two elements say x and y if x=gy or . Call graph G*.
- Check that x---y---z (x is adjacent to y and y is adjacent to z) iff or .We will assume left multiplication by g ( the proof for is exactly the same.)

- Now observe that we need to answer whether this graph G* is 2-colourable.
- There is an elementary result in graph theory characterizing the 2-colourable graphs.

Theorem 1 : A graph is 2-colourable iff it is bipartite.

Theorem 2: A graph is bipartite iff it has no odd-cycle.

Hint 3 :
- Thus Theorem 1 and Theorem 2 ⇒ G* is 2 -colourable iff it has no odd cycle.
- Now what does odd cycle mean in here in terms of group.
- A path of odd length means that in odd number of steps i.e. k is odd.

- A cycle of odd length means that .
- We are given that g is even ordered so it can only happen if k is even.
- Hence an odd cycle cannot exist and we can colour G* with 2 colours.

The answer is therefore True.

can colour the elements of G with two colours in such a way that x and

gx have different colours for each x ∈ G.

One needs to know the basics of Graph Theory to understand the solution.

- As noted Colouring is a fundamental topic in Graph Theory,so we need to convert the problem into a graph theory problem.
- Consider the elements of the group G as the vertices and consider edges between two elements say x and y if x=gy or . Call graph G*.
- Check that x---y---z (x is adjacent to y and y is adjacent to z) iff or .We will assume left multiplication by g ( the proof for is exactly the same.)

- Now observe that we need to answer whether this graph G* is 2-colourable.
- There is an elementary result in graph theory characterizing the 2-colourable graphs.

Theorem 1 : A graph is 2-colourable iff it is bipartite.

Theorem 2: A graph is bipartite iff it has no odd-cycle.

Hint 3 :
- Thus Theorem 1 and Theorem 2 ⇒ G* is 2 -colourable iff it has no odd cycle.
- Now what does odd cycle mean in here in terms of group.
- A path of odd length means that in odd number of steps i.e. k is odd.

- A cycle of odd length means that .
- We are given that g is even ordered so it can only happen if k is even.
- Hence an odd cycle cannot exist and we can colour G* with 2 colours.

The answer is therefore True.

Cheenta is a knowledge partner of Aditya Birla Education Academy

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.

JOIN TRIALAcademic Programs

Free Resources

Why Cheenta?