46 votes 46 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 $2$ $3$ $4$ $n-2 \left \lfloor \frac{n}{2} \right \rfloor+2$ Graph Theory gatecse-2002 graph-theory graph-coloring normal + – Kathleen asked Sep 15, 2014 • retagged May 25, 2018 by kenzou Kathleen 11.2k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply rajoramanoj commented Oct 28, 2017 reply Follow Share plz someone explain clearly..... 0 votes 0 votes HeadShot commented Jan 3, 2019 reply Follow Share Thanx @Pragy Agarwal 16 votes 16 votes harypotter0 commented Jul 13, 2020 reply Follow Share We need 3 colors to color a odd cycle and 2 colors to color an even cycle. 0 votes 0 votes Psy Duck commented May 11, 2023 reply Follow Share If we consider a C3, we need min 3 colors to color it as per mentioned criteria. Similarly for C4 we need min 2 colors to color it and as we changes with that of the value of n in Cn the chromatic or coloring number increase so it can’t be constant.Clearly options 1,2 and 3 are ruled out. 2*floor(n/2)= n if n is even and = n-1 if n is odd [Place n=3 → 2*floor(n/2)=2*floor (1.5)=2*1=2] If n is even n-2*floor(n/2)+2 = n-n+2 = 2 which implies for any cycle graph with even no of vertices we need only two colors to color them properly(minimally).We start with a any color say Red and alternatively color the vertices and finally we will reach the start vertex,the remaining ones are filled with the other color. If n is odd n-2ceil(m/2)+2= n-(n-1)+2= n-n+1+2=3 which implies we need minimum three colors to color a cycle graph with odd no of vertices.This can be validated like the even one.There will be one vertex which cannot be given any of the two colors we used in the even case as both will be adjacent. So we need a new color to color it. Correct answer is option D. 0 votes 0 votes Please log in or register to add a comment.
Best answer 41 votes 41 votes 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 mdrwt answered Nov 7, 2014 • edited May 25, 2018 by kenzou mdrwt comment Share Follow See all 3 Comments See all 3 3 Comments reply Gupta731 commented Oct 18, 2018 reply Follow Share 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. 0 votes 0 votes tusharp commented Dec 5, 2018 reply Follow Share @Gupta731 just substitute n = 3 and n = 4 in given equation. You will get the desired answer. 1 votes 1 votes taurus05 commented Apr 3, 2021 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.
5 votes 5 votes A graph is said to be ‘n’ colorable if there exist a vertex coloring that used maximum ‘n’ color. Nishisahu answered Sep 14, 2020 Nishisahu comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 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?? Nilam answered Oct 21, 2015 Nilam comment Share Follow See all 2 Comments See all 2 2 Comments reply Pragy Agarwal commented Oct 21, 2015 reply Follow Share $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. :) 28 votes 28 votes Nilam commented Oct 21, 2015 reply Follow Share Got it..thnx :) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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 vivekgatecs2020 answered Mar 6, 2020 • edited Mar 7, 2020 by vivekgatecs2020 vivekgatecs2020 comment Share Follow See all 0 reply Please log in or register to add a comment.