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 is 2 colours.
A cube's corners can be split into two sets of four so that every edge joins one set to the other. Colour a, d, f and h with one colour and b, c, e and g with the other. Checking every edge: a-b, a-c, a-e, d-b, d-c, d-g, f-c, f-e, f-g, h-b, h-e and h-g all join corners of different colours.
One colour is clearly not enough, because the two ends of any edge would match. So 2 is the minimum, and 3, 4 and 8 are all more colours than needed. In graph terms, the cube is bipartite (it has no cycle of odd length), so its chromatic number is 2.
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