some actual colouring :p

25 votes

30 votes

Best answer

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$

0

how do we differentiate between regular and planar graph to calculate chromatic number.

Like for planar graph we have chromatic number 4. whereas if we have odd cycles chromatic number = 3 else for even it is 2.

Please help.

Like for planar graph we have chromatic number 4. whereas if we have odd cycles chromatic number = 3 else for even it is 2.

Please help.

1

chromatic number of cycle graph if it is planar

3 if n is odd

2 if n is even

chromatic number of wheel graph if it is planar

3 if n is odd

4 if n is even

3 if n is odd

2 if n is even

chromatic number of wheel graph if it is planar

3 if n is odd

4 if n is even

9

The Four Color theorem

The chromatic number of a planar graph is no greater than four.

Using this we can rule out some option directly.

2 votes