Consider the cube shown below with its 8 corners labelled a, b, c, d, e, f, g,…

The problem asks for the chromatic number of the cube graph, whose vertices are the 8 corners and whose edges are the 12 cube edges. A graph can be colored with two colors if and only if it is bipartite, i.e., it contains no odd cycle. The cube graph has only 4-cycles (its faces) and 6-cycles (around the body); it has no triangle or any odd cycle, so it is bipartite. Concretely, label the corners by 3-bit coordinates and split them by parity: set X = {a, d, f, h} and set Y = {b, c, e, g}. Every edge joins one vertex of X to one of Y (e.g., a–b, a–c, a–e, b–d, b–h, c–d, c–f, d–g, d–b, e–f, e–h, f–g, g–h, h–e all cross the partition). Coloring all of X one color and all of Y another color satisfies the rule. Since at least one edge exists, one color is impossible, so the minimum is 2.