GATE 2026 CH – 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
A cube is a bipartite graph. Colour a corner with one colour, all its neighbours with the second colour, and then their neighbours with the first again. Every edge then joins different colours, since the cube has no odd cycles (the shortest cycle has 4 corners). One colour is not enough because every edge needs two colours, so the minimum is 2.
More Analytical Aptitude: Logical Reasoning, Deduction and Analogy questions
- GATE 2026 CH Q9
- GATE 2024 DA Q2
- GATE 2023 ME Q5
- GATE 2023 ME Q6
- GATE 2025 CE (CE2) Q4
- GATE 2025 CE (CE2) Q7
All Analytical Aptitude: Logical Reasoning, Deduction and Analogy questions →