I've been working on a little math puzzle for the past few hours — applying standard map-coloring to the vertices of an icosahedron. Coloring the vertices is equivalent to coloring the faces of the dual — the dodecahedron in this case. Not wanting to spend a bunch of time on this, I did a bit of research and found the platonic solids had a topological genus of 0, which means that surfaces is indeed four-colorable. Now all I need are the actual colorings of the vertices:
I've arranged the edge ordering to make v0 the center of a pentagonal circuit: v1 – v2 – v3 – v4 – v5 – v1. This allows fixing the vertex relations in space and eliminate permutations.
Edges:
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 3), (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (2, 8), (2, 9), (3, 6), (3, 9), (4, 5), (4, 8), (4, 10), (5, 7), (5, 10), (6, 7), (6, 9), (6, 11), (7, 10), (7, 11), (8, 9), (8, 10), (8, 11), (9, 11), (10, 11)]
With our v0 centered pentagonal circuit, v0, v1, v2 must all be different, so we'll color them 0,1,2. Starting with this constraint, there are only 5 ways to color the remaining 3 vertices:
- v3 must differ from v0, v2, v4 — colors [1,3]
- v4 must differ from v0, v3, v5 — colors [2,3,4]
- v5 must differ from v0, v4, v1 — colors [2,3]
Enumerated, (v3,v4,v5) must be one of [(1,2,3), (1,3,2), (3,1,2), (3,1,3), (3,2,3)].
From these 5 seeds, there are only 6 uncolored vertices remaining. At this point, I got mathematically lazy and performed a simple exhaustive search of the 4096 simple combinations for each seed. The solutions proved to be very interesting. Seeds [(1,2,3), (1,3,2), (3,2,3)] do not have any valid map colorings. The two seeds remaining each have two valid map colorings:
- Seed (0,1,2),(3,1,2):
- coloring (2,3,3,0,0,1)
- coloring (0,3,3,1,0,2)
- Seed (0,1,2),(3,1,3):
- coloring (2,0,3,0,2,1)
- coloring (2,0,0,1,2,3)
I find it fascinating that there are exactly 4 unique map colorings of the vertices of an icosahedron and the faces of a dodecahedron. Hopefully when I have some extra time I can dig into the three seeds that have no solutions. Perhaps there is a simple contradiction that eliminates them.
Posts
