Discussion
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 ________
Answer: D
The minimum number of colors is 2.
The corners and edges of a cube form a bipartite graph: every edge joins corners whose positions differ in exactly one coordinate. Colour a, d, h and f with one colour and b, c, e and g with the other. Then every edge (a-b, b-d, d-c, c-a on top; e-h, h-g, g-f, f-e at the bottom; and the verticals a-e, b-h, d-g, c-f) joins two different colours.
At least two colours are needed, since any edge has two ends that must differ, so 2 is the minimum. 3, 4 and 8 colours are all possible but not minimal; 8 would give every corner its own colour.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development