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 ________
Show Hint
A cube graph has no odd cycles, since every face is a 4-sided square, so it is bipartite. A bipartite graph with at least one edge always needs exactly 2 colors.
Step 1: Restate what is being asked.
We need the smallest count of colors so that whenever two corners of the cube share an edge, they get different colors. Instead of using coordinates, we will color the cube directly, face by face, the way you would color a real 3D object by hand.
Step 2: Color the top face first.
The top face of the cube is a square with 4 corners, and a square is a 4-cycle, so going around it, each corner touches exactly two neighbours on that face. On any square, you can color the corners in an alternating pattern using just 2 colors, say Red and Blue, going Red, Blue, Red, Blue as you go around. This satisfies the top face's own edges with only 2 colors.
Step 3: Color the bottom face using the vertical edges as a check.
Each bottom corner sits directly under one top corner and is joined to it by a vertical edge of the cube. So the color of a bottom corner must be the opposite of the top corner sitting right above it. Doing this for all 4 vertical edges automatically also makes the bottom face alternate Red, Blue, Red, Blue around its own square, so the bottom face's own 4 edges get satisfied for free.
Step 4: Confirm no edge is left unchecked.
A cube has 3 kinds of edges: 4 on the top face, 4 on the bottom face, and 4 vertical ones connecting top to bottom. Step 2 fixes the top 4, Step 3 fixes the vertical 4 and, as a side effect, the bottom 4 as well. So all 12 edges of the cube are satisfied using only Red and Blue, meaning all 8 corners a through h are properly colored with 2 colors.
Step 5: Confirm 2 is the least possible.
Since the cube has at least one edge, a single color always fails for that edge's two endpoints. So the count cannot drop to 1, and combined with Step 4, exactly 2 is both achievable and necessary.
Final Answer:
Coloring the top face alternately and forcing each bottom corner opposite its top neighbour uses only 2 colors and satisfies every edge, so the minimum is 2.
\[ \boxed{2} \]
