(AHSME 1990, P9)

Consider a cube whose edges are colored either red or black such that each face of the cube has at least one black edge. What is the minimum number of black edges?
Of course, we will solve this problem in two steps:

- We need at least 3 black edges. Indeed, each edge is shared between 2 faces, and since there are 6 faces, we need at least $\frac{6}{2}=3$ black edges.

- 3 is indeed sufficient: it is enough that no pair of edges shares a vertex.