Coloring an Icosahedron

Probability Level 3

What is the minimum number of colors you need to color all sides of an icosahedron such that no two sides that join on an edge have the same color? (The one in the image wouldn't qualify since two faces of the same color share an edge.)

Note: It is okay if two sides meeting at a vertex have the same color, but not if they share an edge.

2 3 4 5 6 8 20 None of these answers

1 solution

Geoff Pilling
Nov 10, 2016

We will show that 3 is the solution, by showing:

(1) That it can't be done in fewer than 3 colors
(2) An example where it is done with only 3 colors

For (1), consider any five triangular faces meeting at a vertex. Lets try to paint them with only two colors. You can pick one to be the first color, then the two next to that one need to be a second color. Then the two next to those two would need to be the first color again. However, they share an edge. Therefore, it can't be done with only two colors.

And here is an example with 3 colors (if you are not convinced, cut it out and fold it into the shape of an icosahedron):

Oh, I immediately thought '4-color theorem'

Wen Z - 4 years, 7 months ago

Haha... Yup, when I thought of posting the problem I thought the answer would be 4, but then when I saw that it could be done in 3, I thought... Whoa, this is going to be fun to post! ;0)

Geoff Pilling - 4 years, 7 months ago

Oh, this comment doesn't work because I recalled the wrong value in the theorem. The theorem should have been

If the max degree of a graph is $d$ , then the chromatic number is at most $d+1$ .

Proof: Given a graph $V, E$ whose max degree is $d$ , we will inductively color each vertex. Suppose that for a subgraph $V', E'$ , there exists such a coloring. Then, pick any vertex in $V \backslash V'$ and add it to the graph. It is connected to at most $d$ vertices, hence there is a remaining color that we can assign to it.

An existance proof that 3 colors is sufficient, is to use the coloring theorem that

If the max degree of a graph is $d$ , then $d$ colors is enough to give a chromatic coloring.

Then, we take the dual of the icosahedron (where the faces of the icosahedron become vertices in the dual graph), and see that the degree of each dual vertex is now 3 (or equivalently that in the icosahedron, each face is adjacent to 3 others).

Calvin Lin Staff - 4 years, 7 months ago

Cool! I'm tempted to follow up with the question, "How many different ways can you color the icosahedron with three colors such that no two similarly colored faces share an edge?" (Re-orientations not counted as different ways)... But I'm not too sure yet of the answer... ;0)

Geoff Pilling - 4 years, 7 months ago

@Calvin Lin But what about a tetrahedron? That can't be painted with fewer than four colors. However, it fits your definition for having the degree of each vertex (or face since its its own dual) being 3.

Geoff Pilling - 4 years, 7 months ago

The tetrahedron can be painted with 2 colors, where we paint the faces alternatingly.

Unfortunately, my original comment is wrong. I've edited it.

Calvin Lin Staff - 4 years, 7 months ago

@Calvin Lin – With the tetrahedron you need four colors, since every edge borders every other edge. So there is no way to avoid two colors being next to each other unless you color them all differently.

Geoff Pilling - 4 years, 7 months ago

@Geoff Pilling – Oh yes, the tetrahedron needs 4 colors. As mentioned in my edit, it needs at most $d + 1$ colors.

For some reason I was thinking of octahedron instead. Sorry for the multiple confusion.

Calvin Lin Staff - 4 years, 7 months ago

@Calvin Lin – Ah, OK cool... Looks like we are on the same page! :)

Geoff Pilling - 4 years, 7 months ago

Coloring an Icosahedron

1 solution

0 pending reports