GATE 2026 PH – Question 8
Consider the cube shown below with its 8 corners labelled a, b, c, d, e, f, g, and h. The figure is representative. All corners are to be colored such that any two corners that are connected by an edge must be of different colors. The minimum number of colors required to achieve this is ________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) 2
Explanation
In the cube graph, the 8 corners are vertices and the 12 edges join corners that differ in exactly one coordinate (0 or 1 in each of the three directions).
**Two colours are enough.** Colour a corner by the parity of the number of 1s in its coordinates: even parity red, odd parity blue. Moving along an edge changes exactly one coordinate, so it changes the parity. Hence any two corners joined by an edge get different colours.
**One colour is not enough**, since adjacent corners must differ.
The minimum number of colours is **2** (option D). A graph that can be coloured with two colours is called bipartite.