The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 votes

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 in Graph Theory by Veteran (59.5k points)
retagged by | 1.8k 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 Active (2.3k points)
edited by
–2 votes
Dont u think option D is giving answer 2 only!! Bcoz 2(n/2) will give n as ans n-n+2 =2??
answered by (89 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 :)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,110 questions
44,694 answers
43,753 users