ACE Test series question on Chromatic number

Question

Comments

c ?

---

Satbir

How ???

---

suppose we take a square without daigonals.

n=4

matching number =2

since it is even cycle chromtic no. =2

------------------------------------------------------------------------

suppose we take pentagon without daigonals

n=5

matching number = 2

since it is odd length cycle chromatic no. =3

---------------------------------------------------------------------------

both satisfy the given condition.

Answer 1

If the cycle graph has even number of vertices ,then chromatic number =2

Matching number,i.e size of maximum matching = n/2 (by taking every alternate edge)

If the cycle graph has odd number of vertices ,then chromatic number =3

matching number ,by choosing alternate edge,we get  = n/2-1

In both cases the answer is n+2