7,057 views

The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is

1. $2$
2. $3$
3. $4$
4. $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$

plz someone explain clearly.....
We need 3 colors to color a odd cycle and 2 colors to color an even cycle.

### Subscribe to GO Classes for GATE CSE 2022

Chromatic number will be $3$ for when $n$ is odd and will be $2$ when $n$ is even. Option (D) is a representation for this, hence the correct answer

by

I know that Chromatic number will be 3  when n is odd and will be 2 when n is even. But how both of them together give option D. How I will deduce that expression.

@Gupta731 just substitute n = 3 and n = 4 in given equation. You will get the desired answer.

Looking for the answer we got on paper in the list of options and directly ticking the answer can be fatal at times. Its usually a good practice to consider the scenario like, why this can’t be the answer as well.

A graph is said to be ‘n’ colorable if there exist a vertex coloring that used maximum ‘n’ color.

chromatic no=2 , n=even

chromatic no=3,n=odd

n-2 floor n/2 will always give 0 when n=even +2=2

similarly n-2 floor n/2 will give 1 when n=odd +2=3
Dont u think option D is giving answer 2 only!! Bcoz 2(n/2) will give n as ans only..so n-n+2 =2??
by

$2 \left \lfloor \dfrac n2 \right \rfloor = \begin{cases}n & \text{iff$n$is even}\\n-1 & \text{iff$n$is odd}\end{cases}$

So, $n - 2 \left \lfloor \dfrac n2 \right \rfloor = \begin{cases}0 & \text{iff$n$is even}\\1 & \text{iff$n$is odd}\end{cases}$

PS: The question has a typo. It says $\left [\dfrac n2 \right ]$ instead of $\left \lfloor \dfrac n2 \right \rfloor$. Let me fix it. :)
Got it..thnx :)