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 coloured such that any two corners that are connected by an edge must be of different colours. The minimum number of colours required to achieve this is
Show Hint
A cube's corners split naturally into two groups of four so that every edge joins a corner from one group to a corner from the other; that alone is enough to colour it with just 2 colours.
Step 1: Recognise the problem type. This is a proper vertex-colouring problem on the graph formed by the cube's corners and edges. A cube has 8 vertices and 12 edges, and every vertex touches exactly 3 edges. The smallest number of colours that makes a proper colouring possible is called the chromatic number of the graph.
Step 2: Check for odd cycles. Every face of a cube is a 4-sided loop, and there is no 3-sided loop (triangle) anywhere in the cube graph. A graph in which every loop has even length is called bipartite, and every bipartite graph can be properly coloured with exactly 2 colours.
Step 3: Split the 8 corners into two sets. Set 1 = {a, d, f, h} and Set 2 = {b, c, e, g}. Every one of the 12 edges always joins one corner from Set 1 to one corner from Set 2, and never joins two corners of the same set.
Step 4: Colour accordingly. Colour every corner in Set 1 with colour 1 and every corner in Set 2 with colour 2. Since no edge ever joins two same-set corners, no edge ever joins two same-coloured corners, so this 2-colouring is proper.
Step 5: Confirm the minimum. One colour is never enough whenever any edge exists at all, since the two endpoints of that edge would be forced to share a colour. Since a valid 2-colouring exists and 1 colour is impossible, the minimum is exactly 2.
The minimum number of colours required is 2, which is option (D).
