Coloring Sonobe origami, part 1: proper coloring

One thing that was on my mind while I was composing my Sonobe puzzlers [1, 2, 3] is the question of “properly coloring” a Sonobe construction: what does it mean, when is it possible, and in how many ways can it be done?

There are some hints about this idea in my post on the underlying geometry of Sonobe origami, and rather than discussing the origami itself I’ll just go straight ahead and talk about the underlying polyhedra. So, rather than thinking about origami constructions, we’ll instead think of the equivalent question for polyhedra; in particular, for polyhedra whose faces are all equilateral triangles.

In fact, to make things even simpler, we don’t want to think of the polyhedron as rigid: we really only care about the associated graph.1  That is, imagine that the edges of the polyhedron are made of some stretchy, flexible material, and stretch it and flatten it into the plane without edges crossing.  So, for example, if we start with an octahedron

we can do this to get a flat picture:

Note that you can count in the flattened versions and see that there are 7 bounded faces plus the outer, unbounded region; each of these is a “triangle” in the sense that it touches exactly three edges of the graph, and together they correspond exactly to the 8 faces of the octahedron.

Proper Coloring

The advantage of this change is that we can mostly stop worrying about geometry, and use known results from graph theory.  We’re interested in thinking about what a “proper coloring” of a Sonobe polyhedron might be.  A first natural condition that you might ask is that no two units of the same color of paper ever interlock.  If we translate this condition to the associated graph, it says that each edge should be a different color from its four “neighbor” edges, i.e., those with which it forms a triangle.  Equivalently, this asks that the edges of each triangular face be all different colors.

Now we switch to the dual graph (a cubic, planar, bipartite graph): we make a new graph with a vertex in each face (including the unbounded outer face), and edges connecting two adjacent faces, as in the first row of the image below.

(Click to embiggen.)   Observe that this preserves the number of edges, and moreover that every edge in the dual is uniquely identified with an edge in the original graph.  Thus, every coloring of the original graph is associated naturally with a coloring of the dual graph, as in the second row of the image above.  Colorings in which no face has two same-colored boundary edges are translated into colorings in which no vertex has two same-colored incident edges.  These latter colorings are a well-studied part of graph theory, and there are several nice theorems about them.

Vizing’s Theorem (1964) says that for a nonnegative integer Δ, if a graph has no vertices incident with more than Δ edges then the edges can be colored with Δ + 1 colors so that no two edges of the same color share a vertex.  It follows immediately that every Sonobe construction can be properly colored in four colors.  So, the only question is whether Sonobe polyhedra can be colored using only three colors.  (Certainly three is the minimum, since every face of the polyhedron needs three different colors.)  It turns out that an old (1880) theorem of Tait shows that this is equivalent to the Four Color Theorem!  So, in fact every Sonobe construction can be properly colored using only three colors of paper.

fn1.  Since all the polyhedra we’re talking about here have genus 0 (i.e., have no holes), their skeletons are planar graphs and have natural plane embeddings.  But one could just as well work with (triangulated) maps of arbitrary genus; all we need for this discussion are well-defined faces and the order in which they are glued together at each vertex.  (Though note that some of the results on proper colorings are only valid for planar graphs.)

Advertisements
This entry was posted in Combinatorics, Math, Origami and tagged , . Bookmark the permalink.

3 Responses to Coloring Sonobe origami, part 1: proper coloring

  1. Ann Morhaime says:

    May we please have permission to use your images in this blog?
    They are for a for a student article in our school’s math magazine on modular origami. I would be happy to forward a copy of the article if that is of help.

    Sincerely,

    Ann Morhaime

    Faculty Advisor to Math Mag
    SAR High School, Riverdale, NY

  2. JBL says:

    Yes, you are welcome to use the images on this blog. I would also enjoy seeing a copy of the article!

  3. Ann Morhaime says:

    Thank you so much. Is there address to forward a copy of the article?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s