What is the chromatic number of the following graph? [Graph: A 3D cube-skeleton graph (Q_3) drawn with an outer square 1-2-3-4 and inner square 5-6-7-8 with corresponding edges, but with an additional diagonal edge creating an odd cycle, making chi = 3.] A. 2 B. 3 C. 4 D. 5

GATE 2008 · Discrete Mathematics · Graph Coloring · medium

Answer: B. 3

1. Establish chi >= 3: find an odd cycle: The graph contains an odd cycle (the extra diagonal edge creates a triangle with two adjacent vertices). Therefore 2 colours are insufficient and chi >= 3.
2. Exhibit a valid 3-colouring: chi <= 3: Label vertices and assign colour 1, 2, or 3 systematically: the outer ring and inner vertices can be coloured with 3 colours respecting all adjacencies. No vertex requires a 4th colour.