• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Discrete Mathematics

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 A. 2 B. 3 C. 4 D. n - 2*floor(n/2) + 2

GATE 2002 · Discrete Mathematics · Graph Coloring · medium

Answer: D. n - 2*floor(n/2) + 2

  1. Even cycle: Colour the nodes alternately colour-1, colour-2 around the ring. Since n is even, the last node (colour-2) sits next to the first (colour-1), so no clash. Two colours suffice.
  2. Odd cycle: With n odd, alternating two colours leaves the first and last node sharing a colour while adjacent, a clash. One extra colour for the last node fixes it, so exactly 3 colours are needed.
  3. Match to the options: Test option D: for even n, n - 2*(n/2) + 2 = 0 + 2 = 2; for odd n, n - 2*((n-1)/2) + 2 = 1 + 2 = 3. This is the only choice covering both cases, so the answer is D.