edited by
8,175 views

4 Answers

Best answer
38 votes
38 votes

 

The chromatic number of a graph  is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.

Hence minimum number of colors needed to color given graph is equal to $3$

For odd length cycles we need minimum $3$ colors for vertex coloring and for even length cycles we need just $2$. 

Answer is $B$

edited by
4 votes
4 votes

$chromatic\ number(\chi) \ge \frac{total\ number\ of\ vertices(n)}{Independent\ set(\alpha)}$

$n=9\ and\ \alpha=4$

$\chi = \left \lceil \frac{9}{4} \right \rceil = 3$

$and\ also$

 

$so\ it\ cannot\ be\ 4\ and\ answer\ is\ (b)$

3 votes
3 votes

So 3 color used hence chromatic number =3 option B

edited by
Answer:

Related questions

43 votes
43 votes
6 answers
1
Ishrat Jahan asked Oct 28, 2014
13,883 views
$G$ is a simple undirected graph. Some vertices of $G$ are of odd degree. Add a node $v$ to $G$ and make it adjacent to each odd degree vertex of $G$. The resultant graph...
58 votes
58 votes
7 answers
3
Ishrat Jahan asked Oct 27, 2014
51,581 views
What is the size of the smallest $\textsf{MIS}$ (Maximal Independent Set) of a chain of nine nodes?$5$$4$$3$$2$
43 votes
43 votes
4 answers
4
Akash Kanase asked Feb 12, 2016
15,320 views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.