Question Statement:
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 ________
Step-by-Step Solution & Explanation
### **Detailed Step-by-Step Solution (GATE AE 2026 Q.8)**
**1. Intuitive Physical Setup & Given Parameters**:
We consider a cube with 8 corners (vertices) labelled $a, b, c, d, e, f, g, h$.
Rule: All corners are to be colored such that any two corners connected by an edge must have **different colors** (proper vertex coloring of the cube graph $Q_3$).
We need to find the **chromatic number** $\chi(Q_3)$, i.e., the minimum number of colors required.
**2. Step-by-Step Mathematical Derivation**:
1. **Graph Theoretic Property of a Cube**:
- The skeleton of a 3-dimensional cube is the hypercube graph $Q_3$, having 8 vertices and 12 edges.
- A graph is bipartite if and only if it contains no odd-length cycles.
- In a cube, all faces are squares (cycles of length 4). Every closed cycle on a cube has even length ($4, 6, 8$).
- Since there are no odd cycles, $Q_3$ is a **bipartite graph**.
2. **Chromatic Number of Bipartite Graphs**:
- Every bipartite graph with at least one edge has a chromatic number of exactly 2:
$\chi(Q_3) = 2$
3. **Explicit 2-Coloring**:
- In Cartesian coordinates, the vertices can be indexed as $(x, y, z) \in \{0, 1\}^3$.
- Assign color based on the parity of the coordinate sum $x + y + z$:
- If $x + y + z \equiv 0 \pmod 2$, assign **Color 1** (4 vertices: $(0,0,0), (1,1,0), (1,0,1), (0,1,1)$).
- If $x + y + z \equiv 1 \pmod 2$, assign **Color 2** (4 vertices: $(1,0,0), (0,1,0), (0,0,1), (1,1,1)$).
- Any edge connects two vertices that differ in exactly one coordinate, changing the coordinate sum by $\pm 1$. Thus, adjacent vertices always have opposite parities and different colors.
- Therefore, the minimum number of colors is **2**.
**3. Comprehensive Options & Distractor Analysis**:
- **(A) 8**: ❌ **INCORRECT**. Trivial coloring where every vertex has a distinct color, far from the minimum.
- **(B) 4**: ❌ **INCORRECT**. The four-color theorem applies to planar map coloring; a cube graph needs far fewer.
- **(C) 3**: ❌ **INCORRECT**. 3 colors would be needed if there were an odd cycle (e.g., triangle), but a cube has only even cycles.
- **(D) 2**: ✅ **CORRECT**. A cube is bipartite; 2 colors are both necessary and sufficient.
**4. Official Master Key & Exam Takeaway**:
- **Official Answer Key**: **D**
- **Exam Takeaway**: A graph is 2-colorable if and only if it has no odd cycles (bipartite). Any $n$-dimensional hypercube $Q_n$ has $\chi(Q_n) = 2$ by alternating parity of coordinate sums.