GATE 2024 CS2 Q.60: solution and answer

Official answer: 2Source: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

1. Label the vertices $v_0,\dots ,v_7$ around the octagon as in the figure. The edges seen are the outline edges $v_i{v}_{i+1}$ (indices mod 8), and the chords $v_0{v}_5$, $v_1{v}_4$, $v_2{v}_7$, $v_3{v}_6$, $v_0{v}_3$, $v_1{v}_6$, $v_4{v}_7$, $v_2{v}_5$. The short top and bottom edges $v_0{v}_1$ and $v_4{v}_5$ are hard to make out, but the argument below holds whether or not they are present.

2. Check the index difference of every edge. The outline edges differ by $1$ (or $7$), and the chords differ by $3$ (or $5$): $0-5$, $1-4$, $2-7$, $3-6$ give $5,3,5,3$, and $0-3$, $1-6$, $4-7$, $2-5$ give $3,5,3,3$. So every edge joins two vertices whose indices differ by an odd number.

3. Hence every edge joins an even-indexed vertex to an odd-indexed vertex. With $A=\{v_0,v_2,v_4,v_6\}$ and $B=\{v_1,v_3,v_5,v_7\}$, no edge lies inside $A$ and none lies inside $B$. So the graph is bipartite (it is a subgraph of $K_{4,4}$, and equals $K_{4,4}$ when all 16 edges are present).

4. The graph has at least one edge, so one colour is not enough and $\chi (G)\ge 2$.

5. Give every vertex of $A$ colour 1 and every vertex of $B$ colour 2. No edge joins two vertices of the same set, so this is a proper colouring with 2 colours, and $\chi (G)\le 2$.

6. Therefore $\chi (G)=2$.