The Origami flip graph of the 2× n Miura-ori

Given an origami crease pattern $C=(V,E)$, a straight-line planar graph embedded in a region of R², we assign each crease to be either a mountain crease (which bends convexly) or a valley crease (which bends concavely), creating a mountain-valley (MV) assignment μ:E→\-1,1\. An MV assignment $μ$ is locally valid if the faces around each vertex in C can be folded flat under $μ$. In this paper, we investigate locally valid MV assignments of the Miura-ori, Mm,n, an m× n parallelogram tessellation used in numerous engineering applications. The origami flip graph $OFG(C)$ of C is a graph whose vertices are locally valid MV assignments of C, and two vertices are adjacent if they differ by a face flip, an operation that swaps the MV-parity of every crease bordering a given face of C. We enumerate the number of vertices and edges in OFG(M2,n) and prove several facts about the degrees of vertices in OFG(M2,n). By finding recurrence relations, we show that the number of vertices of degree d and $2n-a$ (for 0≤ a) are both described by polynomials of particular degrees. We then prove that the diameter of OFG(M2,n) is n²/2 using techniques from 3-coloring reconfiguration graphs.