What are the chromatic numbers of the edge graphs of the platonic solids?
For the cube graph, its chromatic number is 2, because it is a bipartite graph.
The tetrahedron is isomorphic to $K_4$, and since $K_4$ must be colored with 4 different colors since each vertex is adjacent to any other vertex, the chromatic number of the tetrahedron is 4.
For the octahedron, each vertex is adjacent to four others and antipodal to one. There are six vertices, so there are three non-adjacent antipodal pairs. Each antipodal pair is given a color. So, its chromatic number is 3.
The Icosahedron is not bipartite, so the chromatic number is greater than 2.Its chromatic number is 4, but how do I argue it?
Dodecahedron is not bipartite, so the chromatic number is greater than 2. Its chromatic number is 3, but how do I argue it?
Best Answer
For the Icosahedron: Each face is a triangle and each vertex is included in $5$ triangles and $5$ edges. So let's assume we can color it using only $3$ colors. Take a vertex $v$ with its $5$ neighbors $w_1,...,w_5$ with triangles $vw_iw_{i+1}$ for $i=1,2,3,4$ and $vw_5w_1$. All vertices in those triangles need a different coloring. If we start at $v$ with color $1$, $w_1$ gets color $2$ and $w_2$ gets color $3$, we can go around the circle to get $w_3 \to 2,w_4\to 3,w_5\to2$. But the last color is in conflict with the triangle $vw_5w_1$ as both $w_5$ and $w_1$ get color $2$.
Therefore we need at least $4$ colors for coloring. $4$ colors are enough as well, you can just take an example coloring.
For the dodecahedron the easiest way to argue that is by writing down an example coloring with $3$ colors. That's in general the procedure for showing that the chromatic number is $k$: Write down a coloring with $k$ colors and show that no coloring with $<k$ colors is possible.