GATE CS 2024 Set 2 | Question 60

NAT · 2 marks

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is _________

Eight dots at the corners of an octagon (two along the top, two on the left side, two on the right side and two along the bottom), joined by the octagon’s eight sides. Eight more edges join each top dot to the bottom dot directly below it, each left-side dot to the right-side dot level with it, the top-left dot to the lower right-side dot, the top-right dot to the lower left-side dot, the upper left-side dot to the bottom-right dot, and the upper right-side dot to the bottom-left dot.

Answer

2

Explanation

Any graph with an edge needs at least 2 colours, and exactly 2 suffice when the graph is bipartite. Go round the octagon and colour the corners alternately red and blue; the eight sides are properly coloured because 8 is even.

Every other edge (the two verticals, the two horizontals and the four long diagonals) joins two corners that are three steps apart around the octagon. Three is odd, so each of them joins a red corner to a blue corner.

No edge joins two corners of the same colour, so the graph is bipartite (it is in fact \(K_{4,4}\)) and its chromatic number is 2.

Answer: 2