0
$\begingroup$

Full question: All vertices of a cube are colored such that no two vertices on the same edge of the cube are the same color. What is the minimum number of colors that are needed to color the vertices of the cube?

There's 8 vertices in total. If I look at one vertex I see that there are three other vertices directly connected. (Am I right?) Would this mean there are four colors minimum?

$\endgroup$
2
$\begingroup$

place all 8 vertices at points with $x,y,z$ coordinates either 0 or 1. Half the points, such as $(0,0,0),$ have an even sum. Half the points, such as $(0,0,1),$ have an odd sum.

Just two colors, odd and even. Any edge joins a vertex with odd sum to a vertex with even sum

$\endgroup$
2
$\begingroup$

In general, the hypercube graph $Q_n$ is bipartite for all $n$.

This includes the case $n=3$, which is a $3$-dimensional cube, as in your question.

Bipartiteness is equivalent to $2$-colorability, so a cube is $2$-colorable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.