ISRO CS 2025 Q.6: solution and answer

Official answer: ASource: ISRO's final answer key of 15 May 2026

1. Read the edges from the figure: $a$-$f$, $a$-$e$, $e$-$d$, $e$-$f$, $e$-$g$, $f$-$g$, $f$-$h$, $f$-$b$, $g$-$h$, $g$-$c$, $g$-$d$, $h$-$b$, $h$-$c$.

2. Lower bound: $e$, $f$, $g$ are mutually adjacent (a triangle), so at least 3 colours are needed.

3. The triangles $efg$ and $fgh$ share the edge $fg$, but $e$ and $h$ are not adjacent, so there is no $K_4$. That alone does not rule out 4 colours, so try to colour the graph with 3.

4. Colour $f=1$, $g=2$, $e=3$. Vertex $h$ is adjacent to $f$ and $g$ but not to $e$, so $h=3$.

5. Vertex $a$ is adjacent to $f$ (colour 1) and $e$ (colour 3), so $a=2$. Vertex $d$ is adjacent to $e$ (colour 3) and $g$ (colour 2), so $d=1$.

6. Vertex $b$ is adjacent to $f$ (colour 1) and $h$ (colour 3), so $b=2$. Vertex $c$ is adjacent to $g$ (colour 2) and $h$ (colour 3), so $c=1$.

7. Every one of the 13 edges joins vertices of different colours, so 3 colours suffice. With the lower bound of 3, the chromatic number is 3.