+17 votes
1.4k 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$
asked | 1.4k views
plz someone explain clearly.....

## 2 Answers

+24 votes
Best answer
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
answered by Loyal (2.8k points)
selected
–2 votes
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??
answered by (109 points)
$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 :)
Answer:

+20 votes
2 answers
1
+16 votes
5 answers
2
+26 votes
3 answers
3