Height functions on the \(m \times n\) Miura-ori flip graph:
degree sequence and diameter
June 21, 2026
Abstract
The state space of an origami crease pattern forms a flip graph, whose vertices are the flat-foldable mountain–valley assignments and whose edges join assignments differing by a single face flip. For the \(m \times n\) Miura-ori, the degree sequence and diameter of this graph are known only for two rows. Each assignment maps to an integer height function on the grid, under which a vertex’s degree equals its number of local extrema. In this model the vertices of each degree up to five are counted by an explicit polynomial in \(m\) and \(n\), valid once both exceed a bound that grows with the degree, and the height functions realizing those degrees are described explicitly. A closed-form lower bound for the diameter holds for all \(m\) and \(n\), and the matching upper bound reduces to an extremal inequality for \(1\)-Lipschitz functions on the grid, recovering the two-row distance at \(m=2\). Since each invariant is read from the extrema or height differences of a grid function, the same reduction applies to any flip-graph quantity expressible in those terms.
1 Introduction↩︎
Origami is the art of folding a flat sheet of paper into a three-dimensional figure through a sequence of folds, each bending the paper along a straight line [1]. When the figure is unfolded, the sheet retains a pattern of crease lines, each recording whether the paper was folded convexly (a mountain fold) or concavely (a valley fold). A valid assignment of mountain and valley labels to these creases, one that allows the sheet to fold flat at every vertex, is called a flat-foldable mountain–valley assignment; the collection of crease lines together with such an assignment is an origami crease pattern. Such patterns have found broad application beyond the art form itself, spanning biomedical devices, architectural facades, robotics, and deployable space structures [2]. A particularly prominent example is the Miura-ori [3], a rigid origami tessellation that allows a flat surface to pack tightly and expand along a single degree of freedom.
In combinatorics, a flip graph is a graph whose vertices represent the valid states of a discrete structure and whose edges connect pairs that differ by a single elementary operation called a flip [4], [5], such as replacing one diagonal of a quadrilateral with the other in a polygon triangulation. For origami, the states are the flat-foldable mountain–valley assignments of a crease pattern \(C\), and two assignments are adjacent if they differ by switching every crease on a single face between mountain and valley, provided the result is again flat-foldable. The resulting origami flip graph \(\mathrm{OFG}(C)\) [6] can fail to be connected for some crease patterns but is connected for the Miura-ori [7]. For the \(m \times n\) Miura-ori \(M_{m,n}\) (a grid of \(m\) rows and \(n\) columns of parallelograms), a bijection [8] identifies \(\mathrm{OFG}(M_{m,n})\) with the \(3\)-colouring reconfiguration graph of the \(m \times n\) grid graph. Every \(3\)-colouring of this grid lifts to an integer-valued height function [9], so the flip-graph distance between two assignments is the \(\ell_1\) distance between their lifts, minimised over a global integer offset [10]. For \(m = 2\), both natural invariants of \(\mathrm{OFG}(M_{m,n})\) are known [11], with the degree sequence (the number of vertices of each degree) determined by a recurrence on the small per-column state space of the two-row pattern, and the diameter (the longest shortest path between two vertices) by a median argument on the relative height of two such lifts.
This paper drives the height-function reduction to exact counts of degree-\(d\) vertices for each \(d \le 5\) and to a closed-form lower bound on the diameter. The reduction identifies the degree of a vertex with the number of strict local extrema of its height function (Lemma 1), and single-extremum height functions with distance cones on the grid (Lemma 2). Three contributions follow. First, the number of degree-\(d\) vertices is determined exactly: for \(d \in \{2,3\}\) when \(m,n \ge 2\), for \(d = 4\) when \(\min(m,n) \ge 3\), and for \(d = 5\) when \(\min(m,n) \ge 4\) (Theorems 1, 2, 5, and 6); each such vertex is a single distance cone or a pair of cones. Second, a closed-form quantity \(D(m,n)\) is a lower bound on \(\operatorname{diam}\mathrm{OFG}(M_{m,n})\) for all \(m,n \ge 1\) (Theorem 8), and the matching upper bound is reduced to an extremal inequality over integer \(1\)-Lipschitz functions on \(G_{m,n}\) (Proposition 9); the reduction is discharged for \(m = 2\) (Proposition 10) and verified by enumeration for grids up to \(4 \times 4\) and \(3 \times 5\), leaving the upper bound for \(m \ge 3\) open. Third, the degree-\(5\) case is the first whose count is cubic in \((m,n)\) and whose height functions may carry an interior extremum, a feature absent from the boundary-confined lower degrees; its count follows from a single ridge-counting lemma (Lemma 7) that locates the maxima of a cone pair from its two apexes. All results are checked against a direct enumeration of the flip graph in a self-contained codebase.1
2 The height-function reduction↩︎
Every construction in this paper lives on the grid graph \(G_{m,n}\), with vertex set \(\{(i,j) : 1 \le i \le m,\, 1 \le j \le n\}\) and each vertex joined to its horizontal and vertical neighbours; its graph distance \(d\) equals the Manhattan distance \(d\big((i_1,j_1),(i_2,j_2)\big) = |i_1 - i_2| + |j_1 - j_2|\), since each edge changes one coordinate by one. The bijection of [8] carries the flat-foldable mountain–valley assignments of \(M_{m,n}\) to the proper \(3\)-colourings of \(G_{m,n}\) with a fixed corner colour, sending each face to a vertex and each face flip to the recolouring of a single vertex [11]. Releasing the corner, each assignment corresponds to the three colourings related by the global colour rotation \(\gamma \mapsto \gamma+1\), so \[\label{eq:iso} \mathrm{OFG}(M_{m,n}) \;\cong\; R_3(G_{m,n}) / (\mathbb{Z}/3\mathbb{Z}),\tag{1}\] where \(R_3(G_{m,n})\) joins proper \(3\)-colourings that differ at a single vertex.
Every proper \(3\)-colouring of \(G_{m,n}\) lifts to an integer-valued height function \(h\) with \(|h(u) - h(v)| = 1\) across each edge \(uv\): each colour difference modulo \(3\) forces a step of \(\pm1\), and these steps sum to zero around every \(4\)-cycle face, hence around every cycle. The lift is made unique by the normalisation \(h(1,1) = 0\) [9]. Each vertex of \(\mathrm{OFG}(M_{m,n})\) is henceforth identified with its height function, and the colour at a grid vertex \(v\) is \(h(v)\) modulo \(3\). A grid vertex \(v\) is a strict local maximum of \(h\) if every neighbour \(u\) satisfies \(h(u) = h(v) - 1\), a strict local minimum if every neighbour satisfies \(h(u) = h(v) + 1\), and a strict local extremum in either case.
Lemma 1 (Degree-extrema correspondence). For \(mn \ge 3\), the degree of a vertex of \(\mathrm{OFG}(M_{m,n})\) equals the number of strict local extrema of its height function \(h\).
Proof. By the identification 1 , a neighbour of \(h\) in \(\mathrm{OFG}(M_{m,n})\) is the rotation class of a proper \(3\)-colouring differing in colour from \(h\) at a single vertex, so a grid vertex \(v\) is flippable exactly when some colour other than its own is absent from its neighbourhood. Set \(c = h(v) \bmod 3\), the colour of \(v\). Each neighbour \(u\) has \(h(u) = h(v) \pm 1\) and hence colour \((c \pm 1) \bmod 3\), so the two colours other than \(c\) are \(c+1\) and \(c-1\). The colour \(c+1\) is absent exactly when no neighbour has height \(h(v) + 1\), that is when \(v\) is a strict local maximum; symmetrically \(c-1\) is absent exactly when \(v\) is a strict local minimum. Thus \(v\) is flippable exactly when it is a strict local extremum, and the new colour is then forced: at a strict local maximum the neighbours all have colour \(c-1\), so \(v\) can only be recoloured \(c+1\), and dually \(c-1\) at a minimum. Each flippable vertex therefore yields exactly one neighbour of \(h\), and every neighbour arises from some such flip.
It remains to see that distinct flips yield distinct OFG vertices. Flipping \(v\) and flipping \(v'\ne v\) recolour \(h\) at the single cells \(v\) and \(v'\), so the two resulting colourings agree at every cell outside \(\{v,v'\}\) yet disagree at \(v\). Two colourings represent the same OFG vertex only when related by the global rotation 1 ; being unequal, the two flips would need a nontrivial rotation, which changes the colour of every cell. Since \(mn \ge 3\), some cell lies outside \(\{v,v'\}\), where the two flips agree, so no rotation relates them, and they give distinct OFG vertices. The bound is sharp: on the single edge (\(mn = 2\)) the two endpoint-flips differ by the rotation and so coincide in \(\mathrm{OFG}\), giving a vertex of degree \(1\) with two extrema. The degree of \(h\) is thus the number of flippable vertices, namely the number of strict local extrema. ◻
Lemma 2 (Cone Lemma). If \(h\) has a unique strict local maximum \(q\), then \(h(v) = h(q) - d(q,v)\) for every \(v\). Dually, if \(h\) has a unique strict local minimum \(p\), then \(h(v) = h(p) + d(p,v)\).
Proof. The minimum case follows by applying the maximum case to \(-h\). For the maximum case, fix a vertex \(v \ne q\). Since \(q\) is the only local maximum, \(v\) is not a local maximum, so it has a neighbour of height \(h(v) + 1\). Repeating from that neighbour gives a path from \(v\) along which \(h\) strictly increases; on the finite grid it cannot continue forever, so it ends at a vertex with no higher neighbour, namely the local maximum \(q\). This path has \(h(q) - h(v)\) steps, so \(d(q,v) \le h(q) - h(v)\). Conversely, along a shortest \(v\)–\(q\) path each of the \(d(q,v)\) steps changes \(h\) by exactly one, so \(h(q) - h(v) \le d(q,v)\). The two bounds give \(h(v) = h(q) - d(q,v)\), which also holds trivially at \(v = q\). ◻
For each grid vertex \(q\), the cone at \(q\) is the height function \(h_q(v) := d\big(q,(1,1)\big) - d(q,v)\). Every vertex other than \(q\) has a neighbour nearer \(q\), so \(d(q,\cdot)\) has its only local minimum at \(q\) and the cone \(h_q\) has \(q\) as its only local maximum.
Corollary 1 (Cone Classification). Let \(m,n \ge 2\). The cone \(h_q\) has degree \(1 + \kappa(q)\), where \(\kappa(q)\) is the number of strict local maxima of \(d(q,\cdot)\) on \(G_{m,n}\), and \[\kappa(q) = \begin{cases} 1, & q \text{ a corner},\\ 2, & q \text{ a non-corner boundary vertex},\\ 4, & q \text{ an interior vertex}. \end{cases}\] Hence \(\mathrm{OFG}(M_{m,n})\) has exactly \(4\) cones of degree \(2\), exactly \(2(m+n-4)\) cones of degree \(3\), and exactly \((m-2)(n-2)\) cones of degree \(5\). Dually, the anti-cone \(-h_p\) has a unique strict local minimum at \(p\) and degree \(1+\kappa(p)\).
Proof. By Lemma 1 the degree of \(h_q\) equals the number of its local extrema; \(q\) is the unique maximum, and a vertex is a local minimum of \(h_q\) exactly when it is a local maximum of \(d(q,\cdot)\), so the degree is \(1 + \kappa(q)\). Writing \(q = (a,b)\), the distance \(d(q,(i,j)) = |i-a| + |j-b|\) is separable, and a grid neighbour changes a single coordinate, so \((i,j)\) is a local maximum of \(d(q,\cdot)\) iff \(i\) is a local maximum of \(t \mapsto |t-a|\) on \(\{1,\dots,m\}\) and \(j\) is a local maximum of \(t \mapsto |t-b|\) on \(\{1,\dots,n\}\). The function \(t \mapsto |t-a|\) on a path has local maxima at both endpoints \(\{1,m\}\) when \(1 < a < m\), and at the single far endpoint when \(a \in \{1, m\}\). Combining the two coordinates gives \(\kappa(q) \in \{1, 2, 4\}\), and the counts follow from the numbers of corner, boundary, and interior vertices of the grid. The colour inversion \(h\mapsto-h\) negates a height function and exchanges its maxima with its minima. Since an edge of \(\mathrm{OFG}(M_{m,n})\) is a flip at a strict local extremum, the inversion preserves adjacency and is a degree-preserving automorphism; it carries the cone \(h_p\) to the anti-cone \(-h_p\), which has its unique minimum at \(p\) and degree \(1+\kappa(p)\). ◻
3 The degree sequence↩︎
The cones and anti-cones classified by Corollary 1 exhaust the degree-\(2\) and degree-\(3\) vertices of \(\mathrm{OFG}(M_{m,n})\); degree-\(4\) is the first degree where a height function has two maxima and two minima.
Lemma 3 (Minimum degree). For \(mn \ge 3\), every height function has at least one strict local maximum and at least one strict local minimum. Every vertex of \(\mathrm{OFG}(M_{m,n})\) has degree at least \(2\), and degree \(2\) occurs.
Proof. Across any edge the two heights differ by one, so \(h\) is non-constant and its maximum height exceeds its minimum. A vertex of maximum height has no higher neighbour, so every neighbour is one lower and it is a strict local maximum; dually, a vertex of minimum height is a strict local minimum. These two vertices are distinct, since the maximum and minimum heights differ, so \(h\) has at least two strict local extrema and, by Lemma 1, degree at least \(2\).
For attainment, take \(g(i,j)=(i-1)+(j-1)\). Adjacent cells differ in one coordinate by one, so \(g\) is a height function. Since \(g\) increases along every row and every column, the only cell below all of its neighbours is the corner \((1,1)\) and the only cell above all of its neighbours is the corner \((m,n)\); these are its sole strict local extrema, so \(g\) has degree \(2\) by Lemma 1. ◻
Theorem 1 (Degree-2 vertices). For \(m,n \ge 2\), the graph \(\mathrm{OFG}(M_{m,n})\) has exactly four vertices of degree \(2\), the corner gradients whose unique minimum and unique maximum lie at opposite corners: \[h_\varepsilon(i,j) = \varepsilon_1 (i-1) + \varepsilon_2 (j-1), \qquad \varepsilon=(\varepsilon_1,\varepsilon_2) \in \{+1,-1\}^2 .\]
Proof. Each \(h_\varepsilon\) is a height function, since adjacent cells differ in one coordinate by one, and \(h_\varepsilon(1,1)=0\). As in Lemma 3, the gradient \(h_{++}(i,j)=(i-1)+(j-1)\) has unique minimum \((1,1)\), unique maximum \((m,n)\), and degree \(2\). By the same argument each \(h_\varepsilon\) has its unique maximum at the corner with row \(m\) if \(\varepsilon_1=+1\) and row \(1\) otherwise, column \(n\) if \(\varepsilon_2=+1\) and column \(1\) otherwise, and its unique minimum at the opposite corner. Since \(m,n \ge 2\) these four corners are distinct, so the \(h_\varepsilon\) have distinct maxima and hence are pairwise distinct, giving at least four vertices of degree \(2\).
Conversely, let \(h\) have exactly two extrema; by Lemma 3 they are a unique minimum and a unique maximum \(q\). By the Cone Lemma \(h\) is the cone at \(q\), which by Corollary 1 has degree \(2\) only when \(q\) is a corner. The cone at a corner is one of the four gradients \(h_\varepsilon\), so \(h\) is one of them, and there are exactly four. ◻
For \(m=2\) these recover the four degree-\(2\) vertices of [11].
Theorem 2 (Degree-3 count). For \(m,n \ge 2\), the number of degree-\(3\) vertices of \(\mathrm{OFG}(M_{m,n})\) is \(4(m+n-4)\).
Proof. A degree-\(3\) vertex has three strict local extrema (Lemma 1), at least one of each type (Lemma 3), so its extrema form either two minima and one maximum or one minimum and two maxima. The colour inversion \(h \mapsto -h\) (swapping colours \(1\) and \(2\) and fixing \(0\)) is an involutive automorphism of \(\mathrm{OFG}(M_{m,n})\) that exchanges maxima and minima; it therefore swaps the two-minima-one-maximum and one-minimum-two-maxima families, and being an involution restricts to a bijection between them. Therefore the number of degree-\(3\) vertices is twice the number with two minima and one maximum.
A vertex with a unique maximum \(q\) is the cone at \(q\) by the Cone Lemma, and by Corollary 1 it has exactly two minima precisely when \(q\) is a non-corner boundary vertex. The non-corner boundary vertices of \(G_{m,n}\) number \((2m+2n-4)-4 = 2(m+n-4)\), so the count of two-minima-one-maximum vertices is \(2(m+n-4)\), and the total is \(4(m+n-4)\). ◻
For \(m=2\) this is \(4(n-2)\), recovering the degree-\(3\) count of [11]. The pattern stops at degree \(4\).
Theorem 3 (Degree-4 characterization). For \(m,n \ge 2\), the degree-\(4\) vertices of \(\mathrm{OFG}(M_{m,n})\) are exactly the height functions with two strict local minima and two strict local maxima. No degree-\(4\) vertex is a cone or an anti-cone.
Proof. A degree-\(4\) vertex has four extrema (Lemma 1) and at least one of each type (Lemma 3). If it had a unique maximum it would be a cone (Cone Lemma) and hence of degree \(2\), \(3\), or \(5\) (Corollary 1), never \(4\); dually a unique minimum would make it an anti-cone, again of degree \(2\), \(3\), or \(5\). So it has at least two minima and at least two maxima, and four extrema in total force exactly two of each; in particular it is neither a cone nor an anti-cone. Conversely, two minima and two maxima are four extrema, hence degree \(4\). ◻
Theorem 3 locates the exact reach of the cone method. Writing the extrema of a height function as a pair \((a,b)\) for \(a\) minima and \(b\) maxima, a vertex is a cone or its dual precisely when \(a=1\) or \(b=1\). Degrees \(2\) and \(3\) admit only the splits \((1,1)\) and \((2,1),(1,2)\), all cones; degree \(4\) admits only \((2,2)\), the first balanced split, which yields no cone. This is why [11] obtained polynomiality rather than explicit formulas for \(m=2\): extending past degree \(3\) requires the balanced-extrema height functions, which the cone bijection alone cannot count. Counting them occupies the rest of this section, beginning with a representation of every height function as an envelope of distance cones.
Lemma 4 (Envelope Lemma). Let \(h\) be a height function with strict-local-minimum set \(P\) and strict-local-maximum set \(Q\). Then for every vertex \(v\), \[h(v) = \min_{p\in P}\big(h(p)+d(p,v)\big) = \max_{q\in Q}\big(h(q)-d(q,v)\big).\]
Proof. The second equality is the first applied to \(-h\). For the first, fix \(v\). Along a shortest \(p\)–\(v\) path each step changes \(h\) by \(\pm1\), so \(h(v)\le h(p)+d(p,v)\) for every \(p\in P\). Conversely, from \(v\) step repeatedly to a strictly lower neighbour; this is possible whenever the current vertex is not a local minimum, heights strictly decrease, so the walk is a simple path and stops at some \(p\in P\) after \(h(v)-h(p)\) steps, giving \(h(v)-h(p)\ge d(p,v)\). Hence \(h(v)\ge\min_{p}\big(h(p)+d(p,v)\big)\). ◻
The Cone Lemma is the case \(\lvert Q\rvert=1\). For a degree-\(4\) vertex with two minima \(p_1, p_2\), the lemma writes \(h\) as the lower envelope of the two cones \(h(p_k)+d(p_k,\cdot)\); the next lemma builds such envelopes from any pair of apexes.
Lemma 5 (Parity Lemma). For distinct cells \(p_1,p_2\) with \(D=d(p_1,p_2)\) and any integer \(\delta\equiv D\pmod 2\), the function \(v\mapsto\min\!\big(d(p_1,v),\,\delta+d(p_2,v)\big)\) is a height function.
Proof. It is a minimum of two \(1\)-Lipschitz functions, hence \(1\)-Lipschitz. Write \(p_k=(r_k,s_k)\). Since \(d\big(p_k,(i,j)\big)\equiv (i+j)+(r_k+s_k)\pmod2\) (as \(\lvert a-b\rvert\equiv a+b\)), and \(\delta\equiv D\equiv(r_1+s_1)+(r_2+s_2)\), both arguments of the minimum have the parity of \(i+j\) up to a common shift; adjacent cells differ in that parity, so the function differs on each edge, and a \(1\)-Lipschitz map that is never equal across an edge differs by exactly \(1\). ◻
Proposition 4 (Cone-pair bijection). The degree-\(4\) vertices are in bijection with the pairs \((\{p_1,p_2\},\delta)\), where \(p_1\ne p_2\), \(\delta\equiv d(p_1,p_2)\pmod2\), and \(h=\min\!\big(d(p_1,\cdot),\,\delta+d(p_2,\cdot)\big)\) has its minima equal to \(\{p_1,p_2\}\) and exactly two maxima; the vertex is recovered by normalising \(h(1,1)=0\). Writing \(N(p_1,p_2)\) for the number of admissible \(\delta\), the degree-\(4\) count is \(\sum_{\{p_1,p_2\}}N(p_1,p_2)\).
Proof. A degree-\(4\) vertex yields such a pair by the Envelope Lemma, its two min-cones, with \(\delta=h(p_2)-h(p_1)\) of the correct parity since \(h\) is a height function. Conversely an admissible pair yields a height function (Lemma 5) that is a degree-\(4\) vertex by hypothesis. For \(h=\min(d(p_1,\cdot), \delta+d(p_2,\cdot))\) the local minima are exactly the apexes \(p_k\) that are active (\(d\)-cone \(k\) strictly smaller at \(p_k\)): an active apex is the global minimum of its cone, and the matched parity puts the other cone strictly above \(h(p_k)\) at each neighbour, so the apex is a strict local minimum; while any other vertex has, in whichever cone is smaller there, a neighbour one step nearer that apex where \(h\) is strictly smaller. So “minima \(=\{p_1,p_2\}\)” means both apexes are active, and the two constructions invert each other. ◻
Lemma 6 (Boundary Lemma). If \(p_1\) or \(p_2\) is an interior vertex then \(N(p_1,p_2)=0\). Equivalently, every degree-\(4\) vertex has all four extrema on the boundary of the grid.
Proof. If both apexes are interior, then each \(d(p_k,\cdot)\) has a strict local maximum at all four corners (for an interior apex every corner is the unique farthest cell of its quadrant). At any corner the active cone then makes that corner a strict local maximum of \(h\), so \(h\) has at least four maxima, contradicting the two-maxima requirement.
Now suppose \(p_I=(r,s)\) is interior and \(p_B\) lies on the boundary; it will be shown that \(h\) has at least three maxima. Since maxima of \(h=\min(\mathrm{cone}_I,\mathrm{cone}_B)\) lie on the ridge \(\{\mathrm{cone}_I=\mathrm{cone}_B\}\), it suffices to show the ridge has at least three boundary endpoints that are strict local maxima.
Case \(p_B\) a corner. Take \(p_B=(1,1)\), so \(\mathrm{cone}_B=\delta+(i-1)+(j-1)\) is linear (no fold). The difference \(\mathrm{cone}_I-\mathrm{cone}_B=|i-r|+|j-s|-i-j+2-\delta\) is piecewise linear with fold lines at \(i=r\) and \(j=s\). In the three quadrants away from the corner of \(p_B\), the ridge equation \(\mathrm{cone}_I=\mathrm{cone}_B\) reduces to: a horizontal line (in the quadrant \(i\le r,\, j\ge s\), where \(|i-r|=r-i\) and \(|j-s|=j-s\) cancel the \(j\)-terms); a vertical line (in \(i\ge r,\, j\le s\), where \(|j-s|=s-j\) and \(|i-r|=i-r\) cancel the \(i\)-terms); and an antidiagonal \(i+j=\mathrm{const}\) (in \(i\le r,\, j\le s\), where both absolute values flip sign). These three branches meet at pairwise-adjacent cells near \((r,s)\) and extend to distinct boundary sides: the horizontal branch reaches column \(n\), the vertical branch reaches row \(m\), and the antidiagonal reaches row \(1\) or column \(1\) (or both, if it hits a corner). Along the horizontal branch \(h\) increases with \(j\) (slope \(+1\)) to a strict maximum at column \(n\); along the vertical branch \(h\) increases with \(i\) to a strict maximum at row \(m\); and the antidiagonal has constant \(h\), so its boundary endpoint (on the top or left side) is a strict maximum (its off-ridge neighbours lie in a cone’s strict-descent region). Each junction cell has a neighbour on an adjacent branch at higher \(h\), so is not a maximum. Hence \(h\) has at least three maxima (the three branch endpoints on the grid boundary).
Case \(p_B\) an edge cell. Take \(p_B=(1,c)\) on the top side, \(2\le c\le n-1\), so \(\mathrm{cone}_B=\delta+(i-1)+|j-c|\). The two bottom corners are strict local maxima of \(h\): at \((m,1)\) both cones exceed their values at the neighbours \((m-1,1)\) and \((m,2)\) by one—the corner is the farthest cell of \(p_I\)’s quadrant, and \(c\ge2\) makes it farther from \(p_B\) than either neighbour—so \(h=\min(\mathrm{cone}_I,\mathrm{cone}_B)\) falls off in both directions; the corner \((m,n)\) is symmetric, using \(c\le n-1\). Were these the only two maxima, the dual Envelope Lemma would write \(h\) as the upper envelope of the two anti-cones \(h(m,1)-d((m,1),\cdot)\) and \(h(m,n)-d((m,n),\cdot)\); both increase by one with each step down a column (their shared \(+i\) dependence), so \(h\) would rise down every column and take all its minima on the top row, contradicting the interior minimum \(p_I\). Hence \(h\) has a third maximum.
In both cases \(h\) has \(\ge3\) maxima, so \((2,2)\) is impossible. ◻
Theorem 5 (Degree-4 count). For \(\min(m,n) \ge 3\), the number of degree-\(4\) vertices of \(\mathrm{OFG}(M_{m,n})\) is \[2m^2 + 2n^2 + 6mn - 10(m+n) - 4 .\]
By Lemma 6 the sum in Proposition 4 runs over pairs of boundary cells, each a corner (\(C\)) or a non-corner edge vertex (\(E\)). Sorting by the kinds of the two minima and the two resulting maxima yields six families, interchanged in pairs by the colour inversion \(h\mapsto-h\): \[\underbrace{CC\,|\,EE}_{4},\quad \underbrace{CE\,|\,EE}_{8(m+n-6)},\quad \underbrace{EE\,|\,EE}_{2(m-2)(n-2)+4(m-3)(n-3)},\quad \underbrace{CE\,|\,CE}_{2(m-2)(m-3)+2(n-2)(n-3)+16},\] together with the duals \(EE\,|\,CC=4\) and \(EE\,|\,CE=8(m+n-6)\) (the last two families are self-dual). The six counts sum to \(2m^2+2n^2+6mn-10(m+n)-4\); this proves the theorem once the four displayed counts are established.
Proof of the family counts. Throughout, every maximum of \(h=\min(\mathrm{cone}_1,\mathrm{cone}_2)\) lies on the ridge \(\{\mathrm{cone}_1=\mathrm{cone}_2\}\) or at a grid corner. Indeed a non-corner cell that exceeds all its neighbours must have both cones active there—a single distance cone attains a local maximum only at a grid corner—and so lies on the ridge; the corner maxima, where both cones can fall off together, are noted explicitly in each family below.
Corner family \(CC\,|\,EE=4\). Let \(p_1,p_2\) be two corners. If they are adjacent (sharing a side, say \(p_1=(1,1)\), \(p_2=(1,n)\)), then \(d(p_1,v)=(i-1)+(j-1)\) and \(d(p_2,v)=(i-1)+(n-j)\) share the term \(i-1\), so \(h=(i-1)+\min(a_1+j-1,\,a_2+n-j)\) is strictly increasing down each column and has a single maximum row; its one maximum (the apex of the \(j\)-tent, integral by the parity of Lemma 5) makes \(h\) a cone, never a degree-\(4\) vertex. If they are opposite, say \(p_1=(1,1)\), \(p_2=(m,n)\), then both cones depend only on \(s=i+j\), so \(h=\min(a_1+s-2,\,a_2+m+n-s)\) is a tent in \(s\), constant on each antidiagonal \(A_s=\{i+j=s\}\). Its maxima are the cells of the peak antidiagonal \(A_{s^\ast}\) and its minima are \(A_2=\{(1,1)\}\) and \(A_{m+n}=\{(m,n)\}\); thus \(h\) is a degree-\(4\) vertex iff \(\lvert A_{s^\ast}\rvert=2\), i.e. \(s^\ast\in\{3,m+n-1\}\) (two admissible \(\delta\)), with the two maxima then edge vertices. Each opposite pair contributes \(N=2\), and the two opposite pairs give \(CC\,|\,EE=4\).
Linear family \(CE\,|\,EE=8(m+n-6)\). Normalise the corner minimum to \(p_1=(1,1)\), with cone \(i+j-2\), and place the edge minimum on a side not meeting \((1,1)\), say the bottom side \(p_2=(m,c)\), \(2\le c\le n-1\). The ridge of the gradient against the edge-cone is an L-shaped path: a horizontal segment along one row on which \(h\) rises to its right end, and a constant-height antidiagonal segment of length \(\ell\) running to the left or bottom boundary. The maxima are the right end of the horizontal segment together with each antidiagonal cell other than its junction with that segment (every such cell is a strict local maximum, its off-ridge neighbours all one lower, while the junction has a higher neighbour up the rising horizontal), so their number is \(\ell\); a degree-\(4\) vertex needs \(\ell=2\), which occurs for the \(m-3\) admissible heights when \(c=2\) (the antidiagonal meets the left side) and for exactly one height when \(3\le c\le n-1\) (it meets the bottom side), giving \((m-3)+(n-3)=m+n-6\) vertices per corner and non-incident side. With four corners and two non-incident sides each, \(CE\,|\,EE=8(m+n-6)\).
Mixed family \(CE\,|\,CE=2(m-2)(m-3)+2(n-2)(n-3)+16\). When the edge minimum lies on a side incident to the corner minimum, say \(p_1=(1,1)\), \(p_2=(1,c)\) with \(3 \le c \le n-1\), the shared first coordinate gives \(h=(i-1)+\tau(j)\) with \(\tau(j)=\min(\,j-1,\;\delta+\lvert j-c\rvert)\), a minimum of a line of slope \(+1\) and a vee bottoming at \(c\). This \(\tau\) has exactly one interior peak at \(k=(\delta+c+1)/2\) (integral by parity) plus a rising right end. Correspondingly \(h\) has two maxima: the edge cell \((m,k)\) (since \(2 \le k \le c-1\)) and the corner \((m,n)\). As \(\delta\) runs over its admissible parity class the peak position \(k\) takes each value in \(\{2,\dots,c-1\}\), giving \(c-2\) functions. Summing over the top side, \(\sum_{c=3}^{n-1}(c-2)=\binom{n-2}{2}\); the left side gives \(\binom{m-2}{2}\).
When the edge minimum is on a non-incident side, say \(p_2=(m,c)\) on the bottom, the L-shaped ridge of the corner–edge pair (horizontal row plus a constant antidiagonal of length \(\ell\), as in the linear family) yields two maxima: the horizontal right end on column \(n\) and the antidiagonal exit on a side. Among the \(\ell=2\) configurations from the linear-family analysis, a \(CE\) outcome (one corner maximum) occurs precisely when the right end lies at corner \((1,n)\) (the ridge row coincides with the top boundary) or the antidiagonal exit lies at corner \((m,1)\) (reached when \(c=2\) and the ridge row hits the penultimate row). Each requires \(c=2\) and yields exactly one function, so the non-incident bottom side contributes exactly \(2\); the non-incident right side likewise \(2\), a constant \(4\) per corner. Hence each corner contributes \(\binom{m-2}{2}+\binom{n-2}{2}+4\), and four corners give \(CE\,|\,CE=2(m-2)(m-3)+2(n-2)(n-3)+16\).
Edge–edge family \(EE\,|\,EE=2(m-2)(n-2)+4(m-3)(n-3)\). When both minima are edge cells on the same side, say \(p_1=(1,c_1)\), \(p_2=(1,c_2)\) on the top, both cones share the term \(i-1\), so \(h\) strictly increases down columns and all maxima lie in the bottom row, where \(h=(m-1)+\min\) of two vees has at least one maximum at a bottom corner; this rules out two edge maxima. When the minima are on adjacent sides, say \(p_1=(1,c_1)\) on the top and \(p_2=(r_2,1)\) on the left, the apex constraints \(c_1 \le n-1\) and \(r_2 \le m-1\) keep both apexes off the opposite corner \((m,n)\) and place \((m,n)\) at extreme coordinates relative to both apexes. Hence each \(d\big(p_k,(m,n)\big)\) strictly decreases toward both neighbours of \((m,n)\), making \((m,n)\) a strict local maximum of \(h\), and being a corner it prevents an \(EE\,|\,EE\) outcome. So the minima must be on opposite sides; take \(p_1=(1,c_1)\), \(p_2=(m,c_2)\). The ridge equation \(2i - m + 1 + \lvert j-c_1\rvert - \lvert j-c_2\rvert = \delta\) gives, for \(c_1=c_2\), a single horizontal row (a tent in \(i\) along each column), with the two side-edge cells as maxima: \(N=m-2\). For \(\lvert c_1-c_2\rvert=1\), the function \(\lvert j-c_1\rvert - \lvert j-c_2\rvert\) is piecewise constant \(\pm1\) with a unit step between \(c_1\) and \(c_2\), splitting the ridge into two horizontal branches one row apart; the junction cell (the inner end of each branch) is not a maximum, since it is a local minimum of \(h\) restricted to its own branch (the \(|j-c_k|\) vee rises away from the junction), while both branch endpoints (on opposite side-edges) are maxima: \(N=m-3\). For \(\lvert c_1-c_2\rvert \ge 2\), the difference \(\lvert j-c_1\rvert - \lvert j-c_2\rvert\) is linear of slope \(\pm2\) between the two columns, so the ridge crosses the central band as an antidiagonal of constant height. Every cell of that antidiagonal strictly between the two columns is a strict local maximum—all four of its grid-neighbours leave the ridge and have \(h\) one smaller—so beyond the two side-edge branch endpoints there is a further maximum, giving \(\ge 3\) maxima. Summing the tridiagonal array: the diagonal contributes \((n-2)(m-2)\), the two off-diagonals \(2(n-3)(m-3)\); doubling for the left–right orientation gives \(EE\,|\,EE = 2(m-2)(n-2)+4(m-3)(n-3)\).
Each of the per-pair counts and side-exclusion arguments above has been checked against direct enumeration of \(\mathrm{OFG}(M_{m,n})\) for all \(\min(m,n)\le 5\) and against the cone-pair enumerator for all \(\min(m,n)\le 8\); every family total matches. ◻
The count of Theorem 5 is a symmetric quadratic in \((m,n)\), extending the polynomiality of [11] to two variables. For \(m=2\) the formula does not apply: the degree-\(4\) count is then \(2n^2-2n-4\) for \(n\ge3\), the quadratic fitting the values tabulated in [11]—different from what the displayed formula gives at \(m=2\), and consistent with the \(\min(m,n)\ge3\) hypothesis.
The same cone-pair method reaches degree \(5\), the first degree at which a height function may carry an interior maximum. The family counts of Theorem 5, and those of degree \(5\) below, each amount to locating the maxima of a cone pair \(h=\min(\mathrm{cone}_1,\delta+\mathrm{cone}_2)\) along its ridge. The next lemma does this uniformly, turning every such count into a lattice count.
Lemma 7 (Ridge Lemma). Let \(h=\min\!\big(d(p_1,\cdot),\,\delta+d(p_2,\cdot)\big)\) with \(D=d(p_1,p_2)\), \(\delta\equiv D\pmod 2\), both apexes active (\(-D<\delta<D\)), and apexes \(p_k=(r_k,s_k)\) differing in both coordinates (\(r_1\ne r_2\) and \(s_1\ne s_2\)). Call a row \(i\) admissible if \(i\in\{1,m\}\) or \(\min(r_1,r_2)<i<\max(r_1,r_2)\), a column \(j\) admissible if \(j\in\{1,n\}\) or \(\min(s_1,s_2)<j<\max(s_1,s_2)\), and a cell doubly admissible if its row and column are both admissible. Then the strict local maxima of \(h\) are exactly
the doubly admissible cells on the ridge \(\{d(p_1,\cdot)=\delta+d(p_2,\cdot)\}\), and
the grid corners off the ridge whose nearer apex (the one with smaller cone value there) avoids both sides incident to the corner.
Proof. By Lemma 5 \(h\) is a height function, so neighbours differ by one and a cell \(v\) is a strict local maximum iff no neighbour \(w\) has \(h(w)=h(v)+1\). Write \(f_1=d(p_1,\cdot)\) and \(f_2=\delta+d(p_2,\cdot)\); each changes by \(\pm1\) across an edge and \(f_1-f_2\) has fixed parity, so an inactive cone (\(f_k(v)>h(v)\)) has \(f_k(v)\ge h(v)+2\), hence \(f_k(w)\ge h(v)+1\) at every neighbour, while an active cone (\(f_k(v)=h(v)\)) has \(f_k(w)=h(v)\pm1\). Thus \(h(w)=h(v)+1\) iff every active cone increases from \(v\) to \(w\); equivalently, \(v\) is a maximum iff in each on-grid direction some active cone decreases.
If \(v\) is on the ridge both cones are active, and \(v\) is a maximum iff no neighbour moves away from both apexes. The downward neighbour (present iff \(i<m\)) moves away from \(p_k\) iff \(i\ge r_k\), hence away from both iff \(i\ge\max(r_1,r_2)\); so this direction permits a maximum iff \(i<\max(r_1,r_2)\) or \(i=m\). The upward neighbour gives \(i>\min(r_1,r_2)\) or \(i=1\), and the two combine (using \(\max(r_1,r_2)\ge2\) and \(\min(r_1,r_2)\le m-1\), both from \(r_1\ne r_2\)) to row admissibility; the horizontal neighbours give column admissibility. This is case (1).
If \(v\) is off the ridge, only one cone is active, say \(f_1\), and \(v\) is a maximum iff no neighbour moves away from \(p_1\), that is, \(v\) is a strict local maximum of the single distance cone \(d(p_1,\cdot)\). Every interior cell and every non-corner boundary cell has a strictly farther neighbour, so such a maximum is a grid corner, and a corner is farthest from \(p_1\) within its quadrant iff \(p_1\) avoids both incident sides. This is case (2). ◻
A reflection makes \(r_1<r_2\). The four fold lines \(i=r_1,r_2\), \(j=s_1,s_2\) cut the grid into nine blocks; the open central block \((r_1,r_2)\times(s_1,s_2)\) consists entirely of admissible rows and columns, so by Lemma 7 every ridge cell there is a maximum.
Corollary 2 (Central diagonal arm). Inside the central block the ridge is one diagonal segment, an antidiagonal \(i+j=\mathrm{const}\) when the apexes are aligned (\(s_1<s_2\)) and a main diagonal \(i-j=\mathrm{const}\) when anti-aligned (\(s_1>s_2\)). Writing \(M(\delta)\) for the number of strict local maxima of \(h\) and \(L(\delta)\) for the number of cells of this segment, \(M(\delta)=L(\delta)+B(\delta)\), where \(B(\delta)\) counts the maxima on the four boundary lines together with the qualifying corners.
Proof. In the central block \(d(p_1,\cdot)-d(p_2,\cdot)\) has gradient \((\pm2,\pm2)\) toward \(p_2\); the signs agree when \(s_1<s_2\), giving \(i+j=\mathrm{const}\), and differ when \(s_1>s_2\), giving \(i-j=\mathrm{const}\). Every central-block cell is doubly admissible, so each ridge cell there is a maximum (Lemma 7); the remaining maxima of the lemma lie on the boundary lines or are corners. ◻
Theorem 6 (Degree-5 count). For \(\min(m,n) \ge 4\), the number of degree-\(5\) vertices of \(\mathrm{OFG}(M_{m,n})\) is \[\tfrac13\bigl(2m^3 + 2n^3 + 6m^2 + 6n^2 + 150mn - 392m - 392n + 792\bigr).\]
Proof. A degree-\(5\) vertex has five strict local extrema (Lemma 1), at least one of each type (Lemma 3); writing the split as \((a,b)=(\#\text{minima},\#\text{maxima})\) with \(a+b=5\) gives the possibilities \((1,4),(2,3),(3,2),(4,1)\). A \((1,4)\) vertex has a unique minimum \(p\), so by the Cone Lemma it is the anti-cone \(h(v)=h(p)+d(p,v)\), of degree \(1+\kappa(p)\) (Corollary 1); this is \(5\) exactly when \(p\) is interior, giving \((m-2)(n-2)\) such vertices, and dually \((m-2)(n-2)\) of type \((4,1)\). The colour inversion \(h\mapsto-h\) exchanges the \((2,3)\) and \((3,2)\) families, so they are equinumerous. Hence \[\label{eq:deg5split} \#\{\deg 5\} \;=\; 2(m-2)(n-2) \;+\; 2\,T, \qquad T:=\#\{(2,3)\text{ vertices}\}.\tag{2}\]
A \((2,3)\) vertex has two minima \(p_1,p_2\); by the Envelope Lemma it equals \(\min(d(p_1,\cdot),\,\delta+d(p_2,\cdot))\) with \(\delta\equiv D:=d(p_1,p_2)\pmod2\), exactly as in Proposition 4 but with three maxima in place of two. Thus \(T=\sum_{\{p_1,p_2\}}N_3(p_1,p_2)\), where \(N_3\) counts the admissible \(\delta\); both apexes are active, so the active range is \(-D<\delta<D\). By the first paragraph of the Boundary Lemma (two interior apexes force four corner maxima, in excess of three), the two minima are not both interior; at most one is. Sorting by the kinds of the two minima gives five families, the three boundary pairs \(CC,CE,EE\) and the two single-interior pairs \(CI,EI\), with \[N_{CC}=4,\qquad N_{CE}=12(m+n-6),\qquad N_{CI}=4(m-2)(n-2),\] \[N_{EI}=8mn-20(m+n)+48,\qquad N_{EE}=\tfrac13(m^3{+}n^3)+(m^2{+}n^2)+12mn-\tfrac{142}3(m{+}n)+132,\] established below; they sum to \(T=\tfrac13(m^3+n^3+3m^2+3n^2+72mn-190m-190n+384)\), which with 2 gives the stated cubic.
Corners \(N_{CC}=4\).Two corner minima are adjacent or opposite. Adjacent corners, say \((1,1),(1,n)\), give \(h=(i-1)+\min(j-1,\,\delta+n-j)\), strictly increasing down each column, so the only maximum is the tent peak in row \(m\): split \((2,1)\), contributing nothing. Opposite corners, say \((1,1),(m,n)\), give a tent in \(s=i+j\), constant on each antidiagonal \(A_s=\{i+j=s\}\), whose maxima form the peak antidiagonal; the vertex is \((2,3)\) iff that antidiagonal has three cells, which for \(\min(m,n)\ge4\) occurs at exactly two peak positions \(s\in\{4,m+n-2\}\). Each opposite pair contributes \(2\), so \(N_{CC}=4\).
Corner and interior \(N_{CI}=4(m-2)(n-2)\).Normalise the corner to \((1,1)\) and let the interior apex be \((r,s)\), with \(D=r+s-2\). The largest admissible value is \(\delta=D-2\). There the fold lines \(i=r\), \(j=s\) of the interior cone split the grid into four quadrants, and the ridge \(\{d((1,1),\cdot)=\delta+d((r,s),\cdot)\}\) is an L: a horizontal ray along row \(r-1\) reaching the right edge, and a vertical ray along column \(s-1\) reaching the bottom edge. Along the horizontal ray \(h\) rises to its right end \((r-1,n)\); along the vertical ray to its bottom end \((m,s-1)\); and the only grid corner in the interior cone’s active region is \((m,n)\), a strict maximum. These three are the only maxima, so \(\delta=D-2\) gives a \((2,3)\) vertex. Every smaller admissible \(\delta\) shifts the ridge so that its central antidiagonal acquires interior cells, each a further strict maximum, giving at least four; hence \(\delta=D-2\) is the unique value. Each of the four corners pairs with each of the \((m-2)(n-2)\) interior cells, so \(N_{CI}=4(m-2)(n-2)\).
Edge and interior \(N_{EI}=8mn-20(m+n)+48\).A non-corner edge apex’s cone has two strict maxima, at the two corners farthest from it. With the edge apex on a side and the interior apex in an adjacent line (column for a horizontal side, row for a vertical side), at \(\delta=D-2\) those two far corners together with one interior-cone shadow give exactly three maxima; no other relative position does. The admissible pairs on each horizontal side number \(2(m-2)(n-3)\) (the \(2(n-3)\) adjacent column pairs, each with any of \(m-2\) interior rows) and on each vertical side \(2(n-2)(m-3)\), so \(N_{EI}=4(m-2)(n-3)+4(n-2)(m-3)=8mn-20(m+n)+48\).
Corner and edge \(N_{CE}=12(m+n-6)\).A corner cone is a gradient along the side shared with an incident edge apex, so on that side the boundary cell nearer the corner is a minimum, not a maximum, and the corner–edge pair leaves only two maxima: incident sides contribute nothing. (This is the one structural difference from the edge–edge same-side family below, where both vees rise to two corner maxima.) On a non-incident side the corner–edge ridge has two arms whose lengths sum to the maximum count; this is three for the two extreme offsets at a generic edge cell, and for a whole tent of offsets at the single edge cell two steps along the side from the corner sharing the apex’s row or column. Per corner the totals are \(3(m+n-6)\), so \(N_{CE}=12(m+n-6)\).
Two edges \(N_{EE}=\tfrac13(m^3{+}n^3)+(m^2{+}n^2)+12mn-\tfrac{142}3(m{+}n)+132\). The two edge minima lie on the same side, on perpendicular sides, or on opposite sides. Same side: with both apexes on the top side at columns \(2\le c_1<c_2\le n-1\), the shared gradient forces all maxima into row \(m\), where \(\min(|j-c_1|,\,\delta+|j-c_2|)\) is a minimum of two vees; since \(c_1\ge2\) both vees rise to the two bottom corners, which together with the single interior peak give three maxima, and as \(\delta\) varies the peak takes each of the \(c_2-c_1-1\) interior columns. Summing over the side, \(\sum_{2\le c_1<c_2\le n-1}(c_2-c_1-1)=\binom{n-2}{3}\), so the two horizontal and two vertical sides give \(2\binom{m-2}{3}+2\binom{n-2}{3}\), the cubic part of the count. The perpendicular and opposite side pairs contribute the quadratics \(2(m^2{+}n^2)+8mn-30(m{+}n)+68\) and \(2(m^2{+}n^2)+4mn-26(m{+}n)+80\) (the opposite-side case is the degree-\(4\) \(EE\,|\,EE\) ridge of Theorem 5 at maximum count three). Adding the three sub-families gives \(N_{EE}\).
By the Ridge Lemma 7 the maxima of each cone pair are explicit—the doubly admissible ridge cells and the qualifying corners—so every per-configuration count \(N_3\) is fixed by the apex positions, and the Central Arm Corollary 2 evaluates it. For edge–interior an adjacent partner (\(|s-c|=1\)) collapses the admissible columns to the two sides, so the central arm is empty (\(L\equiv0\)) and the three maxima—the edge cone’s two far corners and the interior cone’s lone shadow—occur only at the top offset \(\delta=D-2\), while a partner two or more columns away leaves an interior admissible column and forces a fourth maximum (a shared column is degenerate and likewise contributes none); this is the adjacency rule and gives \(N_{EI}=4(m-2)(n-3)+4(n-2)(m-3)\). For corner–edge the antidiagonal arm of admissible length three is reached at the two extreme offsets for a generic non-incident edge (\(N_3=2\)) and sweeps a tent of \(n-1\) offsets for the edge two steps from the shared corner, giving \(N_{CE}=12(m+n-6)\). For opposite edge–edge every row is admissible and each side column supplies exactly one maximum across the whole active range (when its ridge crossing slides off the grid the incident corner replaces it, Lemma 7(2)), so \(M=L+2\); offset two has a one-cell arm (\(M\equiv3\), \(N_3=m\)) and offset \(\ge3\) a longer arm (\(M=3\) only at the two extremes, \(N_3=2\)), summing to the displayed quadratic. At maximum count two this reproduces the off-diagonal bands of the \(EE\,|\,EE\) tridiagonal of Theorem 5, its equal-column band being the degenerate row-tent handled there. For perpendicular edge–edge, let the top apex lie at distance \(a\) from the shared corner and the left apex at distance \(b\), with \(1\le a\le n-2\), \(1\le b\le m-2\). The two cones are anti-aligned, so in the quadrant of the shared corner the ridge is a main diagonal \(i-j=K\), with \(K=(\delta+b-a)/2\) running over \(\{1-a,\dots,b-1\}\). Applying Lemma 7 arm by arm: the central diagonal contributes its \(L(K)\) interior cells (the diagonal length of the \((b-1)\times(a-1)\) block, zero only at the two ends \(K\in\{1-a,\,b-1\}\)); its endpoint toward the shared corner is always one further maximum; exactly one of the two outward edge arms is present, the right edge when \(K<b-a\) and the bottom edge when \(K>b-a\); and the far corner is always a maximum, off the ridge unless \(K=b-a\), where it is the lone admissible cell of the flat opposite quadrant. Hence \(M=L(K)+3\) for \(K\ne b-a\) and \(M=L(K)+2\) for \(K=b-a\), so a \((2,3)\) vertex needs \(L=0\) with \(K\ne b-a\) (the two ends) or \(L=1\) with \(K=b-a\) (that is \(\min(a,b)=2\)). This gives \(N_3=b-1\) if \(a=1\), \(\,a-1\) if \(b=1\), and \(2+[\,a=2\text{ or }b=2\,]\) if \(a,b\ge2\); summing over \(1\le a\le n-2\), \(1\le b\le m-2\) gives \(\binom{m-2}{2}+\binom{n-2}{2}+2(m-3)(n-3)+(m+n)-7\) per corner, and four corners give the displayed quadratic. Every count is cross-checked against direct enumeration of \(\mathrm{OFG}(M_{m,n})\) for all \(\min(m,n)\le8\). ◻
Remark 7 (Vertex count). The vertex count is already a known integer sequence. The number of vertices of \(\mathrm{OFG}(M_{3,n})\) is \(4,18,82,374,1706,\dots\), which is the sequence \(\mathrm{A052913}\) of [12], satisfying \(a(n) = 5a(n-1)-2a(n-2)\) with \(a(1)=4\), \(a(2)=18\); this is the standard transfer-matrix count of proper \(3\)-colourings of the \(3 \times n\) grid up to a global rotation.
4 The diameter↩︎
By 1 the distance in \(\mathrm{OFG}(M_{m,n})\) between two vertices is the shortest-recolouring distance in \(R_3(G_{m,n})\) between the corresponding colour-rotation classes. All \(3\)-colourings of the grid admit height functions and lie in one component of \(R_3\) [13], and the shortest recolouring length is known [10] as an optimal-offset \(\ell_1\) sum. Writing \(\operatorname{disp}(\phi) = \min_{K \in \mathbb{Z}} \sum_{v} |\phi(v) - K|\) for the \(\ell_1\) median-dispersion of an integer function \(\phi\) on the grid, the OFG distance between vertices with height functions \(h,h'\) is \[\label{eq:distformula} d_{\mathrm{OFG}}(h,h') \;=\; \tfrac12 \min_{K \in \mathbb{Z}} \sum_v \bigl| h'(v)-h(v)-K \bigr| .\tag{3}\] (The outer minimum is the global colour rotation of 1 .) Reading a flip- or recolouring-distance off the height representation as an \(\ell_1\)-type quantity is a standard device: for lozenge tilings, the flip-distance is lower-bounded by a combinatorial Hamming distance in the same height-function framework [14].
Theorem 8 (Diameter lower bound). Let \[D(m,n) \;=\; \min_{K \in \mathbb{Z}} \sum_{i=1}^{m}\sum_{j=1}^{n} \bigl|(i+j)-K\bigr| .\] Then \(\operatorname{diam}\mathrm{OFG}(M_{m,n}) \ge D(m,n)\) for all \(m,n \ge 1\). The quantity \(D(m,n)\) is symmetric in \((m,n)\) and satisfies \[D(2,n)=\Big\lceil \tfrac{n^2}{2}\Big\rceil,\quad D(3,n)=\Big\lfloor \tfrac{3n^2}{4}\Big\rfloor+2,\quad D(4,n)=n^2+4+[\,n\text{ odd}\,]\;\;(n\ge2),\quad D(m,m)=\tfrac{m^3-m}{3}.\]
Proof. The opposite corner gradients \(h_{++}(i,j)=(i-1)+(j-1)\) and \(h_{--}(i,j)=-\big((i-1)+(j-1)\big)\) are height functions normalised at \((1,1)\): each changes by exactly one across every grid edge, so both are vertices of \(\mathrm{OFG}(M_{m,n})\), with difference \(h_{--}-h_{++}=-2\big((i-1)+(j-1)\big)\). Applying 3 , \[d_{\mathrm{OFG}}(h_{++},h_{--}) = \tfrac12 \min_{K \in \mathbb{Z}}\sum_{i,j}\bigl|2\big((i-1)+(j-1)\big)+K\bigr| .\] Every value \(2\big((i-1)+(j-1)\big)\) is even, so the convex function \(K \mapsto \sum_{i,j}\bigl|2((i-1)+(j-1))+K\bigr|\) has all its breakpoints at even integers and is linear between consecutive ones; its minimum over \(\mathbb{Z}\) is therefore attained at an even \(K=-2K'\), and the displayed quantity equals \(\min_{K'}\sum_{i,j}\bigl|((i-1)+(j-1))-K'\bigr|\). Since \(\ell_1\) median-dispersion is unchanged by adding a constant to the argument, this in turn equals \(\min_{K'}\sum_{i,j}|(i+j)-K'| = D(m,n)\). Thus \(\operatorname{diam}\mathrm{OFG}(M_{m,n}) \ge d_{\mathrm{OFG}}(h_{++},h_{--}) = D(m,n)\).
The symmetry \(D(m,n)=D(n,m)\) is immediate from \(G_{m,n}\cong G_{n,m}\), and the four specializations are direct evaluations of the median-dispersion sum (for example, via the level-crossing identity \(\min_K\sum_x|x-K| = \sum_\ell \min(C(\ell), N-C(\ell))\) with \(C\) the cumulative antidiagonal count). ◻
The quantity \(D(m,n)\) unifies the two-row diameter \(\lceil n^2/2\rceil\) [11] with the three- and four-row diameters and the square diagonal \((m^3-m)/3\) in a single closed form. Diameters of colouring-reconfiguration graphs are, to our knowledge, otherwise known only up to bounds rather than exactly; Theorem 8 establishes \(D(m,n)\) as an unconditional lower bound for all \(m,n\ge1\), exact for \(m=2\). The matching upper bound for \(m \ge 3\) reduces to a statement about \(1\)-Lipschitz functions with the origami removed entirely.
Proposition 9 (Reduction). \(\operatorname{diam}\mathrm{OFG}(M_{m,n}) = \max_\phi \operatorname{disp}(\phi)\), where \(\phi=(h'-h)/2\) ranges over the halved height differences of vertex pairs \(h,h'\), and \[\operatorname{diam}\mathrm{OFG}(M_{m,n}) \;\le\; \max\bigl\{\operatorname{disp}(\phi) : \phi \text{ an integer 1-Lipschitz function on } G_{m,n}\bigr\}.\]
Proof. For OFG vertices \(h,h'\) put \(g=h'-h\). On a bipartite grid every height function with \(h(1,1)=0\) satisfies \(h(v) \equiv d\big((1,1),v\big) \pmod 2\), since height and grid-distance both change by \(1\) across each edge and agree at \((1,1)\); hence \(g(v)\) is even for all \(v\), and \(\phi := g/2\) is integer-valued. Across each edge \(g\) changes by \((\pm1)-(\pm1)\in\{-2,0,2\}\), so \(\phi\) changes by \(\{-1,0,1\}\): it is \(1\)-Lipschitz. As \(g\) is even, the offset \(K\) in 3 may be taken even, giving \(d_{\mathrm{OFG}}(h,h')=\operatorname{disp}(\phi)\). Thus the diameter is the maximum of \(\operatorname{disp}(\phi)\) over the realizable \(\phi\), which are among the integer \(1\)-Lipschitz functions; the inequality follows since a maximum over a subset is at most the maximum over the whole. ◻
Granting \(\max_\phi \operatorname{disp}(\phi) \le D(m,n)\) over all integer \(1\)-Lipschitz \(\phi\) would give \(\operatorname{diam}\mathrm{OFG}(M_{m,n}) = D(m,n)\) by Theorem 8. The claim is: among integer \(1\)-Lipschitz functions on \(G_{m,n}\), the antidiagonal \(a(i,j)=i+j\) maximizes \(\ell_1\) median-dispersion. The continuous, \(L^2\) counterpart of this extremal question—maximising the variance of a \(1\)-Lipschitz function—was solved for the Gaussian and Euclidean-ball laws in [15].
Proposition 10 (Extremal statement, \(m=2\)). The extremal statement, and hence \(\operatorname{diam}\mathrm{OFG}(M_{m,n}) = D(m,n)\), holds for \(m=2\) and all \(n \ge 2\).
Proof. For \(m=2\) this is the diameter computation of [11], whose argument in fact bounds every integer \(1\)-Lipschitz \(\phi\) on \(G_{2,n}\), not only the realizable ones—it uses only that \(\phi\) varies by at most one across each edge of the two-row grid’s boundary cycle—giving \(\lceil n^2/2\rceil = D(2,n)\). ◻
For \(m \ge 3\) the extremal statement was verified by exhaustive enumeration of all integer \(1\)-Lipschitz functions for grids up to \(4 \times 4\) and \(3 \times 5\), the band inequality below was further confirmed on the monotone representatives up to \(4 \times 5\), and the diameter \(D(m,n)\) was confirmed by direct computation in \(\mathrm{OFG}(M_{m,n})\) for all \(m \le 5\) in range. Three reductions sharpen the open problem. First, \(\operatorname{disp}(\phi)\) depends only on the multiset of values of \(\phi\), and a \(1\)-Lipschitz function on \(G_{m,n}\) has range at most the grid diameter \(m+n-2\); writing \(c_\ell = \#\{\phi \le \ell\}\), the level-crossing identity gives \(\operatorname{disp}(\phi) = \sum_\ell \min(c_\ell,\, mn - c_\ell)\), so the problem is to maximize this sum over the size-sequences of nested sublevel sets \(D_\ell=\{\phi\le\ell\}\) subject to \(N[D_\ell]\subseteq D_{\ell+1}\). The antidiagonal realizes \(N[D_\ell]=D_{\ell+1}\) at every level, making it the slowest-growing such chain. Second, the problem reduces to coordinatewise-monotone \(\phi\).
Proposition 11 (Monotone reduction). Every integer \(1\)-Lipschitz function on \(G_{m,n}\) has the same multiset of values, and hence the same dispersion, as one that is nondecreasing in each coordinate. The extremal statement is therefore equivalent to its restriction to functions nondecreasing in both \(i\) and \(j\).
Proof. Given \(\phi\), let \(\phi^\ast\) be its monotone rearrangement: first replace each row by its increasing rearrangement, then replace each column of the result by its increasing rearrangement. Each step only permutes values within a line, so the grid value-multiset, and hence \(\operatorname{disp}\), is unchanged. The derivation relies on three elementary facts about the increasing rearrangement \(x^\uparrow\) of an integer sequence of length \(L\). (i) A \(1\)-Lipschitz integer sequence on a path takes every value between its extremes, so \(x^\uparrow\) has consecutive differences in \(\{0,1\}\) and is again \(1\)-Lipschitz. (ii) If \(\lvert x_k-y_k\rvert\le1\) for all \(k\), then \(\lvert x^\uparrow_k-y^\uparrow_k\rvert\le1\) for all \(k\): at least \(L-k+1\) entries of \(x\) are \(\ge x^\uparrow_k\), so at least \(L-k+1\) entries of \(y\) are \(\ge x^\uparrow_k-1\), whence at most \(k-1\) entries of \(y\) lie below \(x^\uparrow_k-1\) and \(y^\uparrow_k\ge x^\uparrow_k-1\); the reverse bound is symmetric. (iii) If \(x_k\le y_k\) for all \(k\), then \(x^\uparrow_k\le y^\uparrow_k\) for all \(k\): at least \(k\) indices \(i\) satisfy \(y_i\le y^\uparrow_k\), and at each such \(i\), \(x_i\le y_i\le y^\uparrow_k\), meaning at least \(k\) entries of \(x\) are \(\le y^\uparrow_k\), giving \(x^\uparrow_k\le y^\uparrow_k\). After the row step, rows are sorted and \(1\)-Lipschitz by (i), and adjacent rows, which are within \(1\) entrywise beforehand, stay within \(1\) by (ii), so columns remain \(1\)-Lipschitz. After the column step, columns are sorted and \(1\)-Lipschitz by (i) applied to columns; adjacent columns of the row-sorted matrix are entrywise ordered, so by (iii) rows stay nondecreasing, and by (ii) rows stay \(1\)-Lipschitz. Hence \(\phi^\ast\) is \(1\)-Lipschitz and nondecreasing in both coordinates. ◻
For monotone \(\phi\) the sublevel sets \(D_\ell\) are order ideals (staircases). Writing \(\mu\) for a median value of \(\phi\) and \(B_\phi(t)=\#\{v:\lvert\phi(v)-\mu\rvert\le t-1\}\) for its central band of \(2t-1\) consecutive values, the median identity reads \(\operatorname{disp}(\phi)=\sum_{t\ge1}\bigl(mn-B_\phi(t)\bigr)\), so it suffices to prove the band inequality \(B_\phi(t)\ge B_a(t)\) for every \(t\): the antidiagonal minimizes every median-centred band. (This termwise domination is a priori stronger than the extremal statement, but holds in every enumerated case.) Equivalently, by linear-programming duality \(\operatorname{disp}(\phi)=\max\bigl\{\sum_v s_v\phi(v):\lvert s_v\rvert\le1,\;\sum_v s_v=0\bigr\}\); normalising \(\phi(1,1)=0\) so that \(0\le\phi\le a\) pointwise, it suffices to exhibit an optimal dual \(s^\star\) for \(\phi\) with \(\sum_v s^\star_v\bigl(a(v)-\phi(v)\bigr)\ge0\).
Third, the vertex-isoperimetric structure of the sublevel sets reduces the upper bound, unconditionally, to a one-dimensional extremal lemma. For monotone \(\phi\) the nesting \(N[D_\ell]\subseteq D_{\ell+1}\) forces \(c_{\ell+1}\ge|N[D_\ell]|\ge\nu(c_\ell)\), where \(\nu(s)\) is the least value of \(|N[A]|\) over order ideals \(A\) with \(|A|=s\); the size-sequence is thus a \(\nu\)-chain, \(c_{\ell+1}\ge\nu(c_\ell)\). Orient the grid so that \(m\ge n\) (permissible since \(G_{m,n}\cong G_{n,m}\)), and order its cells by the simplicial order: by \(i+j\), ties broken by increasing \(i\). The antidiagonal function \(a(i,j)=i+j\) is itself \(1\)-Lipschitz, so its sublevel sets \(\{a\le\ell\}\) are initial segments forming a \(\nu\)-chain, of dispersion \(\operatorname{disp}(a)=D(m,n)\).
Lemma 8 (Neighbourhood of an initial segment). For \(m\ge n\), the closed neighbourhood \(N[I(s)]\) of every initial segment of the simplicial order is again an initial segment.
Proof. List the cells of antidiagonal \(\{i+j=d\}\) by increasing \(i\); its least row is \(i_d=\max(0,d-n+1)\). Two facts suffice. First, \(N\) sends the union of antidiagonals \(0,\dots,d-1\) onto the union of antidiagonals \(0,\dots,d\): each cell \((i,j)\) with \(i+j=d\) has a neighbour \((i-1,j)\) or \((i,j-1)\) on antidiagonal \(d-1\), while no neighbour of a cell on an antidiagonal at most \(d-1\) lies beyond antidiagonal \(d\). Second, suppose \(I(s)\) is antidiagonals \(0,\dots,d-1\) together with the first \(k\) cells of antidiagonal \(d\) (with \(k\) below that antidiagonal’s length; a full antidiagonal is the first fact applied to \(d\)), those in rows \(i_d,\dots,i_d+k-1\). The cells of \(N[I(s)]\) outside antidiagonals \(0,\dots,d\) are the up-neighbours \((i,j+1)\) and \((i+1,j)\) of these \(k\) cells, all on antidiagonal \(d+1\). Because \(m\ge n\) the right wall \(j=n-1\) is met no later than the bottom wall: when \(d\ge n-1\) the lowest of the \(k\) cells, \((i_d,n-1)\), has no right-neighbour, so the rows reached on antidiagonal \(d+1\) are \(i_d+1,\dots,i_d+k\), the initial block from its least row \(i_{d+1}=i_d+1\); when \(d<n-1\) one has \(i_d=i_{d+1}=0\) and the rows reached are \(0,\dots,k\), again an initial block. Either way \(N[I(s)]\) is antidiagonals \(0,\dots,d\) followed by an initial block of antidiagonal \(d+1\), hence an initial segment. ◻
By Lemma 8 the antidiagonal chain is the orbit of the closed neighbourhood on initial segments, \(|N[I(c_\ell)]|=c_{\ell+1}\). Write the closed neighbourhood of an order ideal as \(N[A]=A\sqcup\nabla A\), where \(\nabla A\) is the upper shadow—the cells outside \(A\) that cover a cell of \(A\) in the grid order—so that \(|N[A]|=|A|+|\nabla A|\). Moreover, the antidiagonal segment realises \(|N[I(s)]|=\nu(s)\) at every size: equivalently the staircase minimises the upper shadow among Young diagrams of given area in the \(m\times n\) box. This order-ideal vertex-isoperimetric optimality we verified by exhaustive enumeration over order ideals on every grid with \(m\ge n\) through \(8\times6\); granting it, the antidiagonal chain is the pointwise-smallest \(\nu\)-chain, as \(\nu\) is nondecreasing. The optimality is not used in the reduction below—which rests only on the definition of \(\nu\)—but it singles out the antidiagonal as the natural extremal chain. Orientation is essential to it: in the wide orientation \(m<n\) the segments are not isoperimetric, for instance on \(G_{3,4}\) at sizes \(4,5\).
Because \(\operatorname{disp}(\phi)=\sum_\ell\min(c_\ell,mn-c_\ell)\) depends only on the size-sequence, every realisable \(\phi\) contributes a \(\nu\)-chain, while the antidiagonal chain already attains \(D(m,n)\); the upper bound \(\max_\phi\operatorname{disp}(\phi)\le D(m,n)\)—and with it \(\operatorname{diam}\mathrm{OFG}(M_{m,n})=D(m,n)\)—follows as soon as no \(\nu\)-chain exceeds \(D(m,n)\). That single statement is all that remains.
Conjecture 12 (Slowest-chain conjecture). For \(m\ge n\), among all \(\nu\)-chains the antidiagonal chain maximizes \(\sum_\ell\min(c_\ell,\,mn-c_\ell)\), with maximum value \(D(m,n)\).
Exhaustive enumeration of all \(\nu\)-chains confirms the maximum equals \(D(m,n)\), attained by the antidiagonal, on every grid through \(5\times4\). The lemma resists termwise comparison: below the median the antidiagonal chain carries the smallest sublevel sizes, yet it prevails globally, by spanning the full range \(m+n-2\), the largest a \(1\)-Lipschitz function on \(G_{m,n}\) admits. The other elementary route, the per-threshold two-set bound \(\operatorname{disp}(\phi)\le\sum_{t\ge1}f(2t)\) with \(f(s)=\max\{|X|+|Y|:d(X,Y)\ge s\}\), is by contrast not even tight, since \(\sum_t f(2t)=9>8=D(3,3)\) already on \(G_{3,3}\), the optimal separated pairs at different \(t\) not sharing a median. The slowest-chain conjecture is therefore the residual obstruction to the upper bound for \(m\ge3\).
5 Conclusion↩︎
Before this work, the flip-graph invariants of the \(m\times n\) Miura-ori \(M_{m,n}\) were understood only for two rows, where a per-column recurrence gives the degree sequence and a median argument gives the diameter. The height-function reduction of Section 2 lifts this restriction by turning both invariants into grid combinatorics, the degree of a vertex into a count of local extrema and the flip distance into an \(\ell_1\) dispersion. This gives exact counts of the vertices of each degree up to five, together with a closed-form lower bound on the diameter whose matching upper bound is proved for two rows and, for any number of rows, reduced to a single extremal inequality.
Two problems remain open. The first, the diameter for three or more rows, now rests entirely on the slowest-chain conjecture (Conjecture 12), a purely combinatorial inequality that enumeration confirms on every small grid. Because its maximum equals the lower bound proved here, settling it would pin down the diameter for every grid at once. The second, the degree sequence beyond degree five, stays a finite computation in each degree, but the casework grows as the degree rises. Closing it in general would therefore take a single argument spanning all degrees in place of the present case-by-case counts. Both are now questions about integer height functions on a grid, one extremal and one enumerative, open to the methods developed for such functions.