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 colours is 2.
The corners and edges of a cube form a bipartite graph: the corners split into two sets of four, and every edge joins a corner of one set to a corner of the other. One colouring that works:
- colour 1: a, d, f, h
- colour 2: b, c, e, g
Check any edge: a-b, a-c and a-e each join colour 1 to colour 2, and likewise for every other edge, since along each face the colours alternate around the square and each vertical edge joins a top corner to the corner below it of the other colour.
One colour is impossible because adjacent corners exist, so 2 is the minimum. Three, four or eight colours would also satisfy the rule, but none of them is the minimum.
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