retagged by
11,048 views
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

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

6 Answers

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

edited by
5 votes
5 votes

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

 

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??
Answer:

Related questions

39 votes
39 votes
8 answers
1
Kathleen asked Sep 15, 2014
17,665 views
The maximum number of edges in a $n$-node undirected graph without self loops is$n^2$$\frac{n(n-1)}{2}$$n-1$$\frac{(n+1)(n)}{2}$
43 votes
43 votes
4 answers
2
Akash Kanase asked Feb 12, 2016
15,320 views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
49 votes
49 votes
11 answers
3
gatecse asked Sep 15, 2014
13,010 views
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n 2$.$2$$3$$n-1$ $n$