UPSC CSE Prelims 2011

Correct Option

The minimum number of different colours required to paint the given figure, such that no two adjacent regions have the same colour, is 3. This problem is an application of graph colouring, where each region is considered a vertex and an adjacency between regions forms an edge.

The sufficiency of three colours can be demonstrated through a systematic assignment process:

• Select any region and assign it Color A.
• For regions adjacent to an already coloured region, assign the lowest possible colour from a set of three distinct colours (e.g., A, B, C) that has not been used by any of its immediate, coloured neighbours.
• By iteratively applying this rule across all regions, it is found that the entire figure can be successfully coloured using only three distinct colours without violating the condition that no two adjacent regions share the same colour.

The necessity of at least three colours arises from the presence of odd cycles within the graph formed by the regions and their adjacencies. A graph containing an odd cycle cannot be properly coloured with only two colours, thus requiring a third colour.

Incorrect Options

Options 2 (4 colours), 3 (5 colours), and 4 (6 colours) are incorrect because they represent a number of colours greater than the minimum required. While it is possible to colour the figure using more than three colours, the question specifically asks for the minimum number. Since three colours are both necessary and sufficient, any higher count does not satisfy the condition of minimality.