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
etc.

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.

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.

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

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

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 = m − n + 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.




TRIVALENT (3-REGULAR OR CUBIC) GRAPHS

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.)

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.)