Graph Coloring the Sonobe Model, Part 1

Yesterday, NaCreSoMo participant “Gashley” posted her Sonobe Model modular origami. The model is essentially a “spiked dodecahedron”: every vertex of a normal dodecahedron has been turned into a three-sided “spike”. Gashley attempted to color each side of each spike a different color such that no two colors would end up next to each other, but couldn’t quite manage to do it. She hypothesized that it wasn’t possible, and I was nerd sniped.

If you have some math background (like Gashley), you’ll instantly recognize this as graph coloring problem. There have been some famous accomplishments in graph theory in this space, one of which was a proof that you can color any planar graph (i.e. a graph without crossing edges, which could represent, say, a map) using only four colors. One particularly noteworthy thing about this theorem is that the proof made extensive use of a computer program—one of the first to do so.

A quick trip to MathWorld shows that the graph form of a dodecahedron is easily planar, and the Sonobe Model is basically the same as that graph, but with little triangles instead of each point. So it can definitely be colored using four colors.

…but we want to know if it can be colored using three.

I had a hunch that it could, but rather than try to come up with a coloring myself (or prove that it didn’t exist), I took the “lazy” route: I wrote a program. The program uses a very simple backtracking algorithm: try coloring one face-vertex after another, and if it doesn’t work, backtrack (i.e. “erase” the most recent colors and try again, possibly all the way back to the beginning.)

Such is the power of modern computers that it found a solution within seconds, and I spent another hour trying to figure out how to nicely print that solution to a file. As usual, you can check out the program as a Gist on Github, but here’s the graph in all its glory:

It was only after I had put everything together and even uploaded this post that I realized that this graph doesn’t actually correspond to the Sonobe Model. Look at the ring in the middle: in my graph the ring has ten vertices, but in the original it only has five faces. That means I didn’t actually generate the right graph from the dodecahedron!

Maybe I’ll try again tomorrow.

Part of NaCreSoMo; join us!

blog comments powered by Disqus