# Graphs in groups or Groups in graphs : TIFR GS 2018

## Understand the problem

[/et_pb_text][et_pb_text _builder_version="3.27.4" text_font="Raleway||||||||" background_color="#f4f4f4" custom_margin="10px||10px" custom_padding="10px|20px|10px|20px" box_shadow_style="preset2"]Let G be a finite group and g ∈ G an element of even order. Then we
can colour the elements of G with two colours in such a way that x and
gx have different colours for each x ∈ G.[/et_pb_text][/et_pb_column][/et_pb_row][et_pb_row _builder_version="3.25"][et_pb_column type="4_4" _builder_version="3.25" custom_padding="|||" custom_padding__hover="|||"][et_pb_accordion open_toggle_text_color="#0c71c3" _builder_version="3.27" toggle_font="||||||||" body_font="Raleway||||||||" text_orientation="center" custom_margin="10px||10px"][et_pb_accordion_item title="Source of the problem" open="on" _builder_version="3.27"]TIFR GS 2018 Part A Problem 24[/et_pb_accordion_item][et_pb_accordion_item title="Topic" _builder_version="3.27" open="off"]Abstract Algebra[/et_pb_accordion_item][et_pb_accordion_item title="Difficulty Level" _builder_version="3.27" open="off"]Hard[/et_pb_accordion_item][et_pb_accordion_item title="Suggested Book" _builder_version="3.27" open="off"]Abstract Algebra, Dummit and Foote[/et_pb_accordion_item][/et_pb_accordion][et_pb_text _builder_version="3.27.4" text_font="Raleway|300|||||||" text_text_color="#ffffff" header_font="Raleway|300|||||||" header_text_color="#e2e2e2" background_color="#0c71c3" custom_margin="48px||48px" custom_padding="20px|20px|20px|20px" border_radii="on|5px|5px|5px|5px" box_shadow_style="preset3" inline_fonts="Aclonica"]

[/et_pb_text][et_pb_tabs active_tab_background_color="#0c71c3" inactive_tab_background_color="#000000" _builder_version="3.27" tab_text_color="#ffffff" tab_font="||||||||" background_color="#ffffff"][et_pb_tab title="Hint 0" _builder_version="3.22.4"]Do you really need a hint? Try it first!

[/et_pb_tab][et_pb_tab title="Hint 1" _builder_version="3.27"]
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 $x=(g^{-1})x$. Call graph G*.
• Check that x---y---z (x is adjacent to y and y is adjacent to z) iff $y = (g^{-1})x , z = (g^{-1})y = (g^{-2})x$ or $y = x , z = (g)y = (g^2)x$.We will assume left multiplication by g ( the proof for $g^{-1}$ is exactly the same.)
[/et_pb_tab][et_pb_tab title="Hint 2" _builder_version="3.27"]
• 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.
[/et_pb_tab][et_pb_tab title="Hint 3" _builder_version="3.27"]
• 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 $x---gx---(g^2)x---...---(g^k)x$ in odd number of steps i.e. k is odd.
[/et_pb_tab][et_pb_tab title="Hint 4" _builder_version="3.27"]
• A cycle of odd length means that $(g^k)x=x ⇒ g^k=1$.
• 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.

## Watch the video

[/et_pb_text][et_pb_code _builder_version="3.26.4"]

## Similar Problems

[/et_pb_text][et_pb_text _builder_version="4.3.2" hover_enabled="0"]

https://www.cheenta.com/checking-injectivity-tifr-2013-problem-36/

https://www.cheenta.com/sequence-boundedunbounded-tifr-2013-problem-35/

[/et_pb_text][et_pb_post_slider include_categories="12" _builder_version="3.23.3"][/et_pb_post_slider][et_pb_divider _builder_version="3.22.4" background_color="#0c71c3"][/et_pb_divider][/et_pb_column][/et_pb_row][/et_pb_section]

This site uses Akismet to reduce spam. Learn how your comment data is processed.

### Cheenta. Passion for Mathematics

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