in Graph Theory retagged by
8,325 views
37 votes
37 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$
in Graph Theory retagged by
8.3k views

3 Comments

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

4 Answers

35 votes
35 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

edited by
by

3 Comments

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
0

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

1
1

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.

0
0
4 votes
4 votes

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

 

0 votes
0 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??
by

2 Comments

$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. :)
27
27
Got it..thnx :)
0
0
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
edited by
Answer:

Related questions