Saturday, August 31, 2013

Improved completely-foldable octahedron

Completely foldable octahedron with Bassetti hinges and box closures on the outside.

View of the rubber band hinges and the unfolded shape of the triangle units.

Wednesday, August 28, 2013

Triplets of Dyck words code the physical configurations completely folded surfaces

In phantom configurations of a completely folded surface, the triangles and hinges can intersect and coincide. In semi-physical configurations of a completely folded surface, triangles do not coincide (they have a physical, stacked order,) but hinges may cross through each other. In physical configurations of a completely folded surface, triangles do not coincide and hinges do not cross. Since a surface in a physical configuration has no self-intersection, such can never be a non-orientable surface without boundary.

A completely folded surface in either a physical or semi-physical configuration has a stack of triangles—and consequently three stacks of edges—hinged together in a particular way. We assume in the following that the surface has no boundary: therefore every triangle edge is connected to one other triangle edge in the same edge stack by a hinge.

If hinges are permitted to cross each other (the semi-physical condition), then the hinge connections in a given edge stack are a perfect matching of those edges.

If hinges are not permitted to cross (the physical condition), then our boundary-less surface must be orientable, and the hinge connections in a given edge stack are a non-crossing partition of those edges. A natural way to code a non-crossing partition is as a parenthesis word, or Dyck word. When written out as a Dyck word, it is easy to imagine the non-crossing arrangement of the hinges in the edge stack by simply connecting the paired parentheses with arcs above the Dyck word, e.g.:

( ) ( ) ( ( ) ).

Since there are three edge stacks, a triplet of Dyck words of the same length can encode a completely folded physical configuration.

The number of Dyck words of length 2n are counted by the nth Catalan number:

1, 1, 2, 5, 14, 42, 132, 429, 1430, ....

and triplets of Dyck words are counted by the cube of the nth Catalan number:

1, 1, 8, 125, 2744, 74088, 2299968, 78953589, 2924207000, ....

For triangle-faced maps that are, as usual, without boundary, but possibly composed of multiple disjoint components, the same daunting integer sequence counts their completely folded configurations when 2n is the number of triangles in the stack. In using the cube of Catalan numbers we are counting as different every possible difference in the completely folded configuration: e.g., simply rotating the stack, flipping it over, enantiomorph-ing the surface or the folded configuration, etc. More significantly, since the map is permitted to have multiple disjoint components, we also count every possible way the multiple components can be arranged in the stack, including the different ways they can enclose each other.

Though it is appealing to think that we can now dial up the phone number of any completely folded configuration that will ever be designed, the combinatorial explosion frustrates "cold-calling" as a technique to discover new designs. Nonetheless, dialing from even the shortest phonebook puts us in touch with shapes that we humans have largely avoided thinking about. A phonebook with n<=2 has 1 + 1 + 8 = 10 entries in it. The configurations that pick up the phone are the empty set; the triangular pillow; a stack of two triangular pillows; a triangular pillow enclosing another triangular pillow; two triangular "ears" that have seamed along a double edge and folded along the seam—in three rotations; and the same "double ear" with one ear tucked inside the other—also in three rotations. 

Origami vs. Complete Folding in 3D printing

A large machine makes a creased sheet that folds to a small object.

A small machine makes a folded stack that unfolds to a large object.

Friday, August 23, 2013

Regular {3, 2n} maps

Weddslist has a listing of regular maps.

A necessary condition for a regular map to be a CFTM is that its Schläfli formula be {3, 2n} for some positive integer n.

Regular maps meeting this condition include:

Orientable genus 0
di-triangle {3, 2} (it seems the only configuration is folded)
octahedron {3,4}

Orientable genus 1
{3, 6} (1, 1)  (only one vertex)
{3, 6} (0, 2)  6 triangles ()(()); ((())); (())() (it seems the only configuration is folded)
{3, 6} (2, 2)  8 triangles
{3, 6} (1, 3) 14 triangles
{3, 6} (3, 3) 18 triangles
{3, 6} (0, 4) 24 triangles
{3, 6} (2, 4) 26 triangles
{3, 6} (4, 4) 32 triangles

Orientable genus 2
S2:{3, 8} 16 triangles

Non-orientable genus 1
hemioctahedron {3, 4} 4 triangles

Non-orientable genus 6
C6: {3, 10} 10 20 triangles
C6: {3, 10} 5 20 triangles

Parity embedding: completely foldable triangulations from Tait colored maps

The tetrahedron has a Tait coloring, but its dual is not a CFTM. We fix this by half-twisting every edge that has the same color orientation at each end.

If a cubic map has a Tait coloring, then it is possible to find a new embedding for its edge-colored graph such that the dual—a triangular map—is node tricolorable, and thus a completely foldable triangular map (CFTM).

Represent the Tait-colored cubic map as a ribbon graph. Apply a half-twist to any edge that has the same color orientation around the nodes at each end. This edge-selective application of the skew operation yields the ribbon graph of a map having the same number of nodes and edges, but (probably) a different number of faces, and therefore a different Euler characteristic and a different surface topology.

In the new map we always see color orientation reversing at each successive node in a walk on the surface. Thus, if a walk closes after an odd number of steps, our sense of orientation must therefore have reversed. Similarly, if a walk closes after an even number of steps, our sense of orientation must therefore have been preserved. Such an embedding, where every even closed walk is orientation-preserving and every odd closed walk is orientation-reversing, is called a parity embedding. In this new, custom made embedding, the Tait-colored graph has a CFTM as its dual.

Since a walk around the boundary of a face can never be orientation reversing (a face is a topological disk,) every face in a parity embedding is even.

For example, the Tait coloring of the tetrahedron is unique (deleting edges of any one color leaves a 4-cycle.) The unique Tait coloring gives the same color orientation to all four nodes. We need therefore to apply the skew operation to all the edges. That gives us the Petrie dual of the tetrahedron: the hemicube, a map on the projective plane with three 4-sided faces. Its dual, the hemioctahedron, also in the projective plane is the completely foldable triangular map we are looking for.

Edges inherit their Tait colors throughout this process. In the last step, the Eulerian triangulation generated by dualization has just two edge colors incident to each node. Picking the third color to color each node gives a tricoloring.

A nearly physical folded configuration for the hemioctahedron (a pair of hinges must pass through each other) can be imagined as the folding onto a central triangle numbered 0, of three "ear" triangles, numbered in order of folding, 1, 2, 3.

This scheme gives us already one hinge on each side of the stack of triangles—thus we have no choice in hinging together the remaining two edges on each side.

The parenthesis words describing the hinge connections on each side of the folded stack of triangles:

On the side where triangle 1 folds down: ( ) ( )

On the side where triangle 2 folds down: ( { ) }

On the side where triangle 3 folds dow: ( ( ) )

Thus only one side of the stack has a non-physical fold.

Wednesday, August 21, 2013

Completely foldable octahedron with Bassetti-style hinges

A completely foldable octahedron with Bassetti-style rubber band hinges and extra parts.

The Bassetti "Poly-O" style rubber band hinges work better for completely foldable models because they maintain accurate alignment after re-folding. Here the flaps are extended to form a triangular box closure in order to keep them folded flat. The triangle sides are 5 cm, the notches are 0.25" diameter holes centered on the triangle corners.

Tuesday, August 20, 2013

Making a completely foldable object

An equilateral surface is a closed surface composed of equilateral triangles connected edge to edge. Physicists have looked into the requirements for an equilateral surface to be able to fold down to a single triangle. The folding considered is both phantom (the material can pass through itself) and instantaneous (no worries about the intermediate states of the folding or the geometry of those intermediate states.) It turns out there is just one simple requirement for complete foldability: the triangulation must be node tricolorable, that is, we must be able to assign three colors to the nodes of the triangulation such that no edge has the same color at both ends.

From the viewpoint of constructing such a completely foldable surface, if we can assemble the surface from corner tricolored triangles (matching colors where triangles join) the completed surface will be completely foldable.

I have assembled some completely foldable models using cardboard and rubber band hinges.

The printed pattern is a node tricolored triangle grid. Print on 65-lb cardstock.

Press onto a thoroughly gluestick coated poster board. Allow an hour to dry.

Trim along triangle edges.

Separate triangle strips.

Separate triangles.

Punch indicated hole positions with an approximately 4mm diameter hole punch. This can be done in decks of two.

Trim along colored curves. This can be done in decks of two.

Using small scissors, make three cuts meeting in the center.

Use scunci miniature hair elastics. Unstretched, these are about 16 mm in diameter.

With the aid of a crochet hook, attach a single rubber band to make a hinge with an 'X' crossing on each side.

A completely foldable octahedron

Monday, August 12, 2013

Properties of Tait-colored graphs

[Much of this post and the previous one is drawn from Marijke van Gans' 2007 doctoral thesis, "Topics in Trivalent Graphs."]

A proper edge coloring of a graph is a coloring of its edges such that nowhere are two edges of the same color incident to a node. A proper edge coloring of a cubic graph using three colors is called a Tait coloring. (Note, that if a cubic graph has a Tait coloring, it may well have many.)

An example of a trivalent graph that does not have a Tait coloring is the Peterson graph.

Nearly all cubic graphs have a Tait coloring. The Petersen graph is an example of one that does not.

Because each edge in a Tait-colored graph belongs to two cycles of alternating edge colors, no graph with a bridge can have a Tait coloring. (More obviously, no graph with a self-loop can have a Tait coloring, but all such cubic graphs have a bridge as well.)

Every bicubic (bipartite cubic) graph has a Tait coloring.

Every Hamiltonian cubic graph has a Tait coloring.

Since nearly all cubic graphs are Hamiltonian, it follows that nearly all are Tait-colorable.

Every bridge-free, planar cubic graph has a Tait coloring. (A consequence of the Four Color Theorem.)

A Heawood node 2-coloring is a node-2-coloring of a plane (i.e., embedded planar) graph under the condition that the number of black and white nodes in every face cycle are equal mod 3. A bridge-free planar, cubic graph can be Tait colored if and only if it can be Heawood node-2-colored; hence, as a consequence of the Four Color Theorem, every bridge-free, planar cubic graph can be Heawood node 2-colored.

Properties of graphs and trivalent graphs


A graph is the action of a bilateral, reciprocal relationship (example: friendship) on the members of a set (example: the characters in Jane Austen's novels.) Clearly, there is no natural drawing of a graph. Nonetheless, we can always contrive a drawing by arbitrarily assigning to each member of the set a distinct point in space, its node, and then drawing curved or straight lines, edges, between nodes whose corresponding set members are joined by the relationship.

The valence of a node is the number of edges that join to it. The valence of an edge—i.e, the number of vertices that are joined by it—is always 2. A graph is n-valent if all of its nodes have valence n.

We allow multiple instances of the relationship to exist between the same two members (parallel edges); and we also allow instances of the bilateral relationship to exist where both parties are the same individual (a self-loop.) (Note that the existence of either of these these situations will require us to use curved lines in drawing the graph.) A graph having neither parallel edges nor self-loops is called a simple graph. There is such an abundance of non-intersecting lines in 3-space that every simple graph can be drawn using straight lines intersecting only at the nodes. Curved lines allow all graphs to be drawn in 3-space. Graphs that can be drawn in 2-space using curved, non-crossing lines are called planar. 

In outline form, the hierarchy of graph classes is:

graphs (historically, pseudographs)

     multigraphs = graphs without self-loops

          simple graphs = graphs with neither self-loops nor parallel edges (historically, graphs)

A walk in a graph is an alternating sequence of nodes and edges such that successive pairs of nodes are indeed joined in the graph by the edge named between them. A walk can re-travel the same edge or pass through the same node any number of times. A trail is a walk where no edge is re-travelled. A trail where furthermore, no node is passed through more than once, is called a path. A cycle is a closed path (the node where a cycle both begins and ends is not considered to be passed through more than once.) A cleaner definition of a cycle is a connected 2-regular graph—see terms defined below. The length of a cycle is the positive integer that gives the number of edges in it—there is no such thing as a 0-length cycle. A cycle is termed odd or even as its length is odd or even. A graph with no odd cycles is called bipartite. In a bipartite graph the nodes can be properly bicolored, e.g. each node can be colored black or white such that no two nodes of the same color are joined by an edge. The length of the shortest cycle in a graph is its girth.

A graph is not necessarily all in one connected piece. The smallest number of walks that can span the graph (i.e., include every node) is k, the 0th Betti number, the number of components of the graph. A graph with k = 1 is termed connected.

A graph with no cycles is called a forest. A single component of a forest (i.e., a connected, acyclic graph) is called a tree. An edge that is not part of any cycle is called a bridge. Thus every edge in a forest is a bridge, and—having indeed no odd cycles—every forest is bipartite.

The minimum number of edges whose deletion reduces a graph to a forest is o, the cyclomatic number, or 1st Betti number of the graph.

o = mn + k,

where, n is the number of nodes and m the number of edges.

The minimum number of edges whose deletion disconnects a graph is its edge connectivity. For example, the edge connectivity of a multicomponent graph is 0, while the edge connectivity of a connected graph containing a bridge is 1.

The minimum number of nodes whose deletion disconnects a graph is its vertex connectivity, or simply its connectivity.

Edge connectivity and vertex connectivity are rather different things. For example, a good strategy for edge-disconnecting a network of friends would be to break a friendship of a person with few friends in the network. In contrast, a good strategy for vertex-disconnecting a network of friends would be to remove from the network someone with many friends in the network.

A tree that spans a graph (includes every node) is called a spanning tree—a spanning tree is a connected, acyclic subgraph that spans the graph. Every component has a spanning tree.

A closed trail (no edges are re-travelled) that includes every edge in a graph is called an Eulerian circuit. If such a closed trail exists, the graph is termed Eulerian. A necessary and sufficient condition for a graph to be Eulerian is that the valence of every node is even.

A 1-factor, or perfect matching, is a 1-valent subgraph (i.e., a set of disjoint edges) that spans the graph.

A 2-factor is a 2-valent subgraph (i.e., a set of disjoint cycles) that spans the graph. If there exists a single-component 2-factor, the graph is termed Hamiltonian.

A graph is termed n-regular or n-valent (or zero-valent, monovalent, bivalent, triavalent, etc.) if every vertex has valence n.


A graph where the valence of every node is 3 (every node is the junction of three edges) is called 3-regular, trivalent, or cubic.

A zero-valent graph, or empty graph, is simply an unconnected set of nodes. A monovalent graph is a collection of disconnected line segments. A bivalent graph is composed of disconnected cycles. But, a trivalent graph may have great complexity. As we will see, any sort of graph, and all its embedding in two dimensional surfaces, can be studied in the guise of edge-colored trivalent graphs.

Every cubic graph has an even number of nodes. In particular, for any cubic graph there is an integer, h, such that n = 2h and m = 3h.

Every cubic graph is cyclic.

A cubic graph having a self-loop also has a bridge.

In a cubic graph with n>2, no edge can have more than one parallel.

In every cubic graph, edge connectivity is numerically equal to vertex connectivity.

The number of Hamiltonian cycles in a cubic graph is even.

If one Hamiltonian cycle passes through a given edge of a cubic graph, another Hamilton cycle passes through the same edge.

Nearly all cubic graphs are Hamiltonian  (i.e., the likelihood that a randomly chosen cubic graph will be Hamiltonian goes to 1 as n goes to infinity.)

Friday, August 9, 2013

Gems from gems

Action of the map dualities on the edge 4-cycles of a graph-encoded map.

From one graph-encoded map, five other gems are easily generated. The six mutually related gems are called direct derivates.

Recall that black-pink cycles in gems are special. They are always 4-cycles because they represent edges (edges must have exactly two ends) so we cannot make a move that turns black-pink cycles into any other sort of cycle for fear that what will be left (to turn into black-pink cycles) will not have cycles of 4.

We can, however, switch those two colors, black and pink. That will still leave us with a Tait-colored graph having black-pink cycles of length 4. But, in consequence of switching black and pink, the pink-white cycles transform into black-white cycles, and the black-white cycles transform into pink-white cycles. In other words, vertices have become faces, and faces have become vertices. This color switch is an operation of order two, since repeating the color switch just returns the original gem. The new gem encodes what is known as the (Poincare) dual of the original map.

There are four more possible permutations of three colors, but none of them is fair game because of the need to insure that we have black-pink cycles are of length 4. Nonetheless, we can still do some systematic re-connecting of the nest.

Tracing around a black-pink cycle, we can always label the vertices in the order they are encountered such that the colored cycle is:

(ab), {bc}, (cd), {da}

where parentheses are black edges and curly brackets are pink edges. The operation skew "cross-wires" the black segments to make the cycle:

(ac), {cb}, (bd), {da}

The result of skew is called the Petrie dual of the map. 

 The corresponding operation that "cross-wires" the pink segments is called phial, the result of phial is called the antimap. (Since dual allows us to switch colors at will, having a separate, color-specific operator for pink edges is not strictly necessary.)

Like dual, skew and phial are operations of order two: "cross-wiring" the same pair of edges twice leaves them in their original arrangement. Operations of order two are termed dualities.

Composing the three dualities discovered above (Du, Sk, Ph) yields two more operations we can perform on a gem: Sk(G*) and Ph(G*). These two composite operations are mutual inverses—each undoes the other. They are also trialities: applying either operation three times in succession returns the original gem.

Above is an incomplete Cayley diagram (the actions of the two trialities are omitted) that shows what happens to the black-pink 4-cycles under the action of the dualities. (Note the surprising fact that when one color is already crossed, the operation of crossing the other color is equivalent to simply rotating the diagram 90 degrees.)

Tuesday, August 6, 2013

What the heck are graph-encoded maps?

A wireframe model of an octahedron uses only 12 wires but fails to specify what surface is being described (in other words, the wireframe specifies the abstract graph, but not its embedding.)  A graph-encoded map of the octahedron needs 24 wires in each of three colors (72 in total), but succeeds in specifying the surface up to topological equivalence.

What has three colors, a wire of each color at each junction, and encodes a surface?

Graph-encoded maps (gems) are just the thing for anyone who would rather think about surfaces and maps visually rather than algebraically. This is a short introduction to graph-encoded maps for those who might be inclined to put them to use. It will be seen that understanding gems makes it easy to understand relations between maps that may seem at first perplexing, e.g., dual, Petrie dual, phial, antimap, etc. Deep insights like map permutations become almost obvious.

A graph is a collection of edges having vertices at both ends. We allow the same two vertices to be at the ends of multiple distinct edges (parallel edges) and we allow the same vertex to be at both ends of an edge (a self-loop.) A graph is not necessarily connected (it may have multiple components), but we will be dealing here exclusively with connected (single component) graphs.

A practical use for graphs, especially in computer graphics and generative art, is to describe and subdivide a surface. A proper embedding of a graph in a closed surface is a drawing of the graph on the surface without any crossing lines, and such that, if all the lines of the drawing were to dematerialize, the surface would fall apart into simply-connected pieces. (It follows immediately that only a connected graph can be properly embedded.) By requiring the surface to fall apart into simply-connected pieces we are requiring that the drawing have enough lines in the right places to fully reveal all the topologically significant details of the surface such as the presence of a handle or a cross-cap.

A map is a proper embedding of a graph in a surface considered up to topological equivalence.

A Tait-colored graph is a graph in which each edge has been assigned one of 3 colors, and every vertex has exactly three incident edges, one of each color. (It follows immediately that a Tait-colored graph cannot have a loop.) It turns out that we never have to deal with any other kinds of graphs if we don't want to, nor with any of their various embeddings in surfaces. Wilson (1979) and Lins (1982) found that anything we might say on these meaty subjects can be just as well expressed as Tait-colorings of abstract trivalent graphs. How simple!

Given a map, any drawing of the map on its surface is locally planar (topologically speaking) provided we stay within the scope of the simply-connected faces surrounding one vertex.  Staying within that limited scope, we can construct what is known as the barycentric subdivision of the map as follows.

We color the vertex at the center of our local scope with the 0-color because a vertex is a 0-dimensional component of the map. Here we identify the 0-color with BLACK.

We construct a mid-edge vertex on each edge incident to the (now black) vertex at the center of our scope (unless such a mid-edge vertex has already been constructed) and color these mid-edge vertices with the 1-color because an edge is a 1-dimensional component of the map. We identify the 1-color with WHITE.

We construct a mid-face vertex in the middle of each face surrounding the black vertex at the center of our local scope (unless such a mid-face vertex has already been constructed) and color these mid-face vertices with the 2-color because a face is a 2-dimensional component of the map. We identify the 2-color with PINK.

Now we construct new edges connecting the (black) vertex at the center of our local scope to its surrounding (pink) mid-face vertices, and also construct new edges connecting the mid-face vertices to the (white) mid-edge vertices within the scope (if such edges have not already been constructed.)

By repeating this construction for each vertex, what emerges is a new map, an Eulerian triangular (triangle-faced) map of the same surface (it is Eulerian because an even number of edges—and triangles—meet at each vertex.) In particular, the number of triangles meeting at each white, mid-edge vertex is 4; the number of triangles meeting at each pink, mid-face vertex is twice the number of original sides on that face; and the number of triangles meeting at each black, original vertex is twice the number of original edges meeting at that vertex. Every edge in this new triangular map connects vertices of two different colors, so each edge can be systematically colored using the third color, the color not present at either of its endpoints.

The dual of this Eulerian triangular map is a simple map (meaning three edges meet at each vertex) having an even number of sides in each of its faces. We can automatically generate a Tait-coloring for the edges of this map by allowing edges to inherit the color of the dual edge.

Using the "good 'n plenty" coloring scheme (0 = black, 1 = white, 2 = pink), every black-white cycle in a gem is a face, every pink-white cycle in a gem is a vertex, and every black-pink cycle in a gem is a 4-cycle representing an edge. Here, the gem—an abstract graph—is shown co-embedded with the original map (a barely visible triangulation) that it completely describes.

Now comes the good news: we can discard at this point the original map, graph, and surface. All can be reconstructed (up to topological equivalence) from the Tait-colored abstract graph—a "bird's nest" in three colors of wire—which is known as a graph-encoded map or gem.

A graph-encoded map of the tetrahedral graph embedded in a sphere (realized in Flexeez.)

Still the same gem. 

Recovering the map

To make a physical model of the surface encoded by a gem (a tricolored "bird's nest"):

1. Give each vertex in the "bird's nest" a number.

2. Cut out an equilateral triangle of mylar drawing film, one for each numbered vertex (if you find that your surface is non-orientable, you will need "ghost mylar" that passes through itself without difficulty.) Mark the vertex number in the center of the triangle, and draw black, white, and pink perpendiculars to the sides. Either of the two possible cyclical orders will do: black-white-pink or black-pink-white. (Since mylar is translucent, we can always flip a triangle over to switch the cyclical order when needed.)

3. Trace the wiring in the "bird's nest" to find the numbers of the black, white, and pink neighbors of each numbered vertex, and so label the correspondingly-colored perpendiculars on its triangle.

4. At this point, no further reference to the gem or "bird's nest" is needed. Assemble the triangles edge-to-edge in accordance with their labels.

Friday, August 2, 2013

An exchange move that preserves tricolorability

Edge-coloring of the connectivity map for the completely foldable triangle grid.
When the edges of the connectivity map are colored the same as the edges of the triangulation (the triangle edges being colored with the mean of the node colors at each end,) left-right, geodesic paths (Petrie paths) cycle through three colors, and facial cycles cycle through two colors.

By shifting branches past each other two-past-two, and then swapping the colors of two edges, a doubled exchange can be made that preserves tricolorability.

An exchange move that preserves tricolorability.

Thursday, August 1, 2013

An expansion move that preserves complete foldability

An expansion move that preserves the tricolorability (complete foldability) of  a triangulation.

Like the Pachner moves in the previous post, the composite move that preserves the tricolorability or tripartite-ness of a triangulation has a dual version that acts  on the trivalent connectivity map.

The expansion move acts on the dual connectivity map (dashed lines) in a predictable way.

Expansion in the connectivity map is simply the insertion of a digon in an edge. This increases face count by one, vertex count by 2, edge count by 3.

Expansion in the connectivity map is simply the insertion of a digon in an edge.

Moves that preserve the tricolorability of the triangulation preserve the local bipartite-ness of the connectivity map.

Exchange and expansion: Dual versions of the Pachner moves

Expansion and exchange moves, dual versions of the Pachner moves. Image quoted from Bilson-Thompson et al., "Update on braids and preons."

Each of the Parchner moves (and their compositions) has an equivalent in the dual map, the 3-regular (a.k.a., trivalent or cubic) map that directs the connectivity of the triangles in the triangulation.

Exchange = dual version of flip22 = Find a 3-edge path that turns left-then-right or right-then-left. Slide the two non-path, branch edges past each other. Leaves the face, vertex, and edge counts unchanged. In fullerene chemistry this is the Stone-Wales transformation.

Expansion = dual version of flip13 : truncate a (trivalent) vertex, creating a trianglular face in its place. Increases face count by 1, vertices by 2, and edges by 3.

Contraction = dual version of flip31 = contract a trianglular face, leaving a trivalent vertex in its place. Decreases face count by 1, vertices by 2, and edges by 3.

Mutating completely foldable triangulations

If we have a completely foldable (CF) triangulation in hand, we might be able to mutate it into another CF triangulation by making local "moves" that preserve its tricolorability.

It is known that a sequence of Pachner moves (a.k.a., bistellar flips) connect any two triangulations of the same surface.

The three Pachner moves are:

flip22 = rotate the edge shared by two triangles (this move is self-inverse.)
flip13 = trisection one triangle into three triangles by adding one vertex and three edges to its interior.
flip31 = weld together the three triangles around a trivalent vertex by removing the vertex and its three incident edges (this is the inverse of flip13.)

None of the Pachner moves preserve the tricolorability of a triangulation by themselves. Rotate creates four non-Eulerian vertices when applied to a triangulation that is already tricolorable. Trisection does the same. Weld cannot even be applied to a tricolorable triangulation since it needs a trivalent vertex. 

The tricolorability-preserving mutation we are looking for, if it exists, must be expressible as a composition of Pachner moves.

There are nine possible 2-move compositions of Pachner moves, and these may have variations depending on which edge or triangle we choose operate on in the second move.

We can immediately eliminate the 2-move compositions that begin with weld since there are no trivalent vertices to be found in a triangulation that is tricolorable. For like reasons, we can eliminate the 2-move compositions that end with trisection since this would leave us with a trivalent vertex in the triangulation making it non-tricolorable.

The three remaining possibilities are:

rr: rotate-then-rotate: an identity when the same edge is operated on in the second move; the first rotation creates four non-Eulerian vertices and there is simply no way to repair them all with a subsequent rotation of any other edge.

rw: rotate-then-weld: this fails in the general case because there is no guarantee that the edge rotation of the first move will produce a trivalent vertex to weld in the second move. The special cases when an edge rotation produces a trivalent vertex are: I, when at least one of the vertices the edge rotates away from has valence 4, and II, when at least one of the vertices the edge rotates toward has valence 2.

tr: trisection-then-rotate: this works any time the rotation acts on one of the three edges created in the first move. Rotating some other edge in the second move would leave a trivalent vertex from the first move, making the triangulation non-tricolorable.

tw: trisection then weld: this is an identity since the only trivalent vertex available to weld is the one created in he first move.

So the only 2-move composition of Pachner moves that preserves tricolorability is tr, more explicitly, "trisection a triangle, then rotate one of the new edges." The action of tr is to increase the count of vertices by 1, faces by 2, and edges by 3.

In visual terms, tr parallellizes an edge and then separates the two parallel edges with a bisected edge.

With hindsight we can construct an inverse for tr from special case II of rw as follows. If any vertex in a triangulation has valence 2, it must lie between two parallel edges (else its incident faces could not both be triangles.) Finding such a 2-valent vertex, we can rotate either of its opposing parallel edges, making said vertex 3-valent, and then remove the vertex with weld. Note that this rw acts as the inverse of tr regardless of which of the two opposing parallels gets rotated and ultimately removed.

That gives us tr, which can grow a tricolorable triangulation, and rw, which can shrink one, leaving us still in the hunt for a mutation that can interconvert tricolorable triangulations of the same size.

What tr means physically is that we slit open one edge of the triangulation (creating the two parallel edges) and repair the wound by gluing on a triangular envelope that has been likewise slit open one on edge. The net result is that we have joined a triangular "ear" to the surface. The 2-valent vertex is the point of the ear. Inversely, rw finds such an ear and removes it.

Clearly, slit-and-join is a general technique we can use to compose any two completely foldable triangulations (CFT's) along a doubled common edge. If we imagine this surgery occurring when both CFT's are completely folded, the final move is simply to fold on the coincident common edges so that we once again have a single triangle.