GATE 2018 CS Q.18: solution and answer

Official answer: 3Source: Official answer key, GATE 2018 CS (IIT Guwahati)

1. Read the edges from the figure: $ae,ac,ab,ec,ef,cd,cb,db,df,bf$.

2. Lower bound: $a,b,c$ are pairwise adjacent (edges $ab$, $ac$, $cb$), so they form a triangle $K_3$ and $\chi (G)\ge 3$.

3. Try a 3-colouring with colours 1, 2, 3. Colour the triangle: $c=1,b=2,a=3$.

4. Vertex $e$ is adjacent to $a(3)$ and $c(1)$, so $e=2$ works.

5. Vertex $d$ is adjacent to $c(1)$ and $b(2)$, so $d=3$ works.

6. Vertex $f$ is adjacent to $b(2)$, $d(3)$ and $e(2)$, so $f=1$ works.

7. Check every edge: $ae(3,2)$, $ac(3,1)$, $ab(3,2)$, $ec(2,1)$, $ef(2,1)$, $cd(1,3)$, $cb(1,2)$, $db(3,2)$, $df(3,1)$, $bf(2,1)$. All end colours differ.

8. So 3 colours suffice, and the triangle shows fewer will not do: $\chi (G)=3$.