WorksMathematics
Nonintersecting Unit Diagonals in Odd Square Arrays
Abstract
Let be the maximum number of unit-square diagonals in an square array such that no two selected diagonals share an endpoint and no unit square contains both diagonals. We prove that, for every odd positive integer , . The matching lower bound was established by Boyland, Roth, Pintér, Laukó, Schoenfield, and Wasielewski. We obtain the upper bound by transforming any admissible selection in a square array into an isometric path cover of the vertex grid with at most paths. An auxiliary matching decomposes the original vertices into alternating paths. On each such path, all segments between blocks are either of type or of type . Projecting these paths to the block grid gives coordinate-monotone sequences, which become geodesics when diagonal steps are expanded. The Fisher–Fitzpatrick theorem then yields the sharp upper bound. We also describe a Lean verification of the upper-bound reduction, with the grid-cover theorem supplied as an explicit hypothesis.
Introduction
Consider the lattice vertex set
and the array of unit squares that it determines. A unit diagonal is a diagonal of one of these squares. A selection is admissible if its members have pairwise disjoint endpoints and no square contains both of its diagonals. These conditions are equivalent to the selected segments being pairwise disjoint. Indeed, the relative interiors of distinct unit squares are disjoint, and a diagonal meets the boundary of its own square only at its endpoints. Write for the maximum cardinality of an admissible selection.
Boyland, Roth, Pintér, Laukó, Schoenfield, and Wasielewski [1] proved
when is even.
For odd , Proposition 5 and the border extension following its proof give the lower bound
They also gave an upper bound and discussed the conjectured optimality of their constructions. The odd-order formula is still labeled a conjecture in OEIS entry A264041 as accessed on October 15, 2026 [4]. Our contribution is a general upper bound matching (1).
Theorem 1.1. For every integer ,
Equivalently, for every odd positive integer ,
Date: October 15, 2026.
Key words and phrases. Nonintersecting diagonals, matchings, Cartesian grids, isometric path covers.
The upper bound applies to every admissible selection, without imposing a prescribed pattern. Its main ingredient is a transformation to an isometric path cover of a smaller grid. The number of paths in the cover is controlled exactly by the number of unmatched original vertices. § 3 proves this transformation, including the type invariant needed for geodesicity, and combines the resulting upper bound with the published lower bound to prove Theorem 1.1. Finally, § 4 states the scope of the accompanying Lean verification.
Grid paths and the Fisher–Fitzpatrick theorem
Coordinates are written as , with the row coordinate increasing downward and the column coordinate increasing to the right. Thus a unit diagonal joins to or joins to . An admissible selection is a matching in the graph of all unit diagonals, subject to the additional prohibition on the two diagonals of a single square.
Let
be the Cartesian grid with vertex set and edges joining vertices at Manhattan distance one. Here has vertices. A path is isometric, or geodesic, if it is a shortest path between its endpoints. A path consisting of one vertex is permitted. An isometric path cover is a family of such paths whose vertex sets cover the graph; different paths may share vertices.
The distance between and in is . In particular, an orthogonal grid path whose two coordinates are each monotone is isometric: its horizontal and vertical step counts are the absolute changes in the corresponding coordinates, so its length equals this distance.
Theorem 2.1 (Fisher–Fitzpatrick). The minimum number of paths in an isometric path cover of is .
This is the square-grid specialization of the grid-cover results in [2 Section 4]; see also [3] for the distinction between covers and partitions. We use only the assertion that every isometric path cover contains at least paths. The grid in this statement has vertices, rather than unit squares.
An upper bound by local routing
Fix and an arbitrary admissible selection on . Put . Partition the original vertices into the disjoint four-vertex blocks
Within a block, write
We suppress the subscripts when discussing a single block and display its labels as . An edge of is internal if its endpoints belong to the same block, and external otherwise. The only possible internal edges are and . They cannot both be selected, since they are the two diagonals of one unit square.
Local routes and their ports
Define an auxiliary perfect matching within the blocks. In a block with no internal edge of , choose and as the two -edges. In a block containing either internal edge, choose and . In each case pairs all four vertices and has no edge in common with . Here is a matching in the graph-theoretic sense: its edges may cross in the drawing, and such crossings do not create graph vertices.
The graph consisting of the local -edges and the internal -edges is a union of paths. We call these paths local routes. Their endpoints are called ports. A route is of type A if its ports are , oriented from to , and of type B if its ports are , oriented from to . All possibilities are listed in Table 1.
| Internal edge of | Edges of | Oriented local routes | Types |
| none | A and B | ||
| B | |||
| A |
Table 1. Local routes. In the last two rows the intermediate vertices are already matched by the internal edge of .
The routes partition the original vertices. At least one route occurs in every block. Furthermore, an external -edge can meet a local route only at a port: each intermediate vertex of a three-edge route is already incident with its internal -edge.

Figure 1. Solid edges belong to and dashed edges belong to . A crossing without a dot is not a graph vertex. The auxiliary matching is used only for routing.
It is essential to distinguish the type of a route from the labels of its intermediate vertices. For example, is a type B route even though it contains and . Those two vertices cannot carry external edges. Type preservation concerns the ports through which routes are connected.
Alternating paths in the original graph
Let
Since is a perfect matching, is a matching, and the two matchings have no common edge, every vertex of has degree one or two. A degree-two vertex is incident with one edge of each matching. Each connected component is therefore an alternating path or an alternating cycle. In particular, has no isolated vertices. The local routes in Table 1 are the parts of these components inside individual blocks, before external -edges are included.
Lemma 3.1 (Uniform type and directed steps). Every external edge of joins the exit port of one local route to the entry port of another local route of the same type. Consequently, all local routes in a connected component of have a common type.
Orient the local routes as in Table 1, and orient each external edge from its exit port to its entry port. These orientations make every component of a directed path or a directed cycle. In a type A component, every external edge is directed from to , with block increment
In a type B component, every external edge is directed from to , with block increment
Thus all cross-block segments on a given component are of type , or all are of type .
Proof. A unit diagonal changes both coordinate parities. Thus it pairs an -vertex with a -vertex, or a -vertex with a -vertex. External edges meet local routes only at ports. An external edge therefore joins two type A routes, and an external edge joins two type B routes. In either case, one is an exit to an entry. Every component of consists of local routes joined by external edges, so its local routes all have the same type.
At the entry port of a local route, its first edge points out of that port, and an external edge, if present, points into it. At the exit port the directions are reversed. The matching property allows at most one external edge at each port. At an intermediate vertex of a local route there is already one incoming and one outgoing edge, and no external edge can occur there. The orientations therefore fit together to give directed paths and directed cycles.
The four unit-diagonal neighbors of are
whenever the corresponding indices are in range. The first neighbor is internal; the other three give (5) in the orientation . Similarly, the four possible neighbors of are
Removing the internal neighbor gives (6) in the orientation .
Lemma 3.2 (Path decomposition and count). Every connected component of is an alternating path with at least one edge. The number of these paths is
Proof. By Lemma 3.1, a component has a common type. Assign the integer to each vertex in a type A local route in block , and assign to each vertex in a type B local route in that block. Along an oriented local route this value is constant. Along an external edge it increases strictly, by (5) and (6).
Any cycle in would be directed by Lemma 3.1 and would contain an external edge: inside any single block, the local routes are disjoint paths. The assigned integer would then be nondecreasing around the cycle and would increase strictly at least once, which is impossible. Hence every component is a path. It has at least one edge because meets every original vertex.
A vertex of has degree one exactly when it is not matched by . There are such vertices. Each path component has exactly two degree-one vertices, so
:::
Projected paths in the block grid
Let be the ordinary vertex grid: its vertices are the block indices , and two vertices are adjacent exactly when their Manhattan distance is one. Define the block projection
For a directed path of , project its vertex sequence by and delete consecutive repetitions. Each remaining step corresponds to an external edge of . A step may be diagonal in the block coordinates; expand it into an east step followed by its vertical step, as specified below. We call the resulting walk the projected walk of in . The next lemma shows that it is a geodesic path.
The paths used to cover are these projections of the paths of . Different projected paths may meet at a grid vertex; the prescribed continuation of each is inherited from its path in . Their number is counted in , not by the connected components of their union in .
Lemma 3.3 (Geodesic cover transformation). An admissible selection on determines an isometric path cover of with at most paths.
Proof. Let be a directed path component of , and project it as described above. Lemma 3.1 applies to the entire path: all its cross-block segments are of type , or all are of type . In the first case, both block coordinates are nondecreasing; in the second, the row coordinate is nonincreasing and the column coordinate is nondecreasing. After consecutive
repetitions have been deleted, every step changes at least one coordinate strictly. Thus a block index cannot recur in the resulting sequence.
Expand its diagonal steps using
Each inserted vertex lies in , because its coordinates are coordinates of the two original endpoints. The expanded walk uses only edges of and preserves both coordinate directions.
This monotonicity proves simplicity and shortestness. If a vertex occurred twice, both coordinates would have the same value at those occurrences. Monotonicity would force them to remain constant between those occurrences, contradicting the unit steps. The horizontal step count equals the total increase of the column coordinate, and the vertical step count equals the absolute change of the row coordinate. Hence the length equals the Manhattan distance between the endpoints, so the projected walk is a geodesic path. If lies in a single block, its projection is the single-vertex path at that block index.
Every original vertex belongs to a path component of . Thus each block is visited by at least one of these paths. Projection retains its block index, and expansion only adds vertices. Consequently, the projected paths cover all vertices of . They form an indexed family with one member for each of the paths of , by Lemma 3.2. Intersections between members are allowed. If coincident members are discarded, the number of paths can only decrease.
Proposition 3.4. For every ,
Proof. For any admissible , Lemma 3.3 and Theorem 2.1 imply
Rearranging and maximizing over proves the assertion.
Proof of Theorem 1.1. For , the lower bound of Boyland et al. recorded in (1), with , gives
where the equality follows from . Together with Proposition 3.4, this proves (2). Substituting gives (3).
Formal verification and its scope
A Lean 4.19.0 formalization of the upper-bound reduction is provided as ancillary material with this article on arXiv. It is available through the ancillary-file links on the article’s abstract page. The source project includes a pinned mathlib dependency, a toolchain specification, and a README giving reproduction instructions and the correspondence between formal declarations and the paper’s arguments. The formalization verifies the encoding of unit diagonals, the uniform route type, acyclicity, the component count, and the transformation to a cover by shortest grid paths. The implementation uses local routes as an intermediate representation of the paths of .
The Fisher–Fitzpatrick grid-cover bound is an explicit hypothesis of the formal upper-bound theorem; that published result is not proved in the Lean project. The published lower-bound construction of Boyland et al. is also not formalized, and the formal exact-value statement assumes the existence of an attaining selection. Thus the formal verification covers the reduction and its conditional consequences, rather than every ingredient of Theorem 1.1. A separate Python script in the ancillary material checks explicit configurations attaining the known lower bound for all odd side lengths from 1 through 99. These finite checks supplement the proofs and do not replace them.
Disclosure of generative AI assistance
Generative AI tools (OpenAI Codex) assisted with the development and exposition of the proof, the drafting and revision of the manuscript, and the Lean formalization. The author is responsible for the mathematical claims, attribution, and submitted content. The scope of the formal verification is stated in § 4.
School of Mathematical Sciences, Peking University, Beijing, China
References
- [1]P. Boyland, I. Roth, G. Pintér, I. Laukó, J. E. Schoenfield, and S. Wasielewski, On the maximum number of non-intersecting diagonals in an array, J. Integer Seq. 20 (2017), Article 17.2.4. https://cs.uwaterloo.ca/journals/JIS/VOL20/Pinter/pinter3.html.
- [2]D. C. Fisher and S. L. Fitzpatrick, The isometric path number of a graph, J. Combin. Math. Combin. Comput. 38 (2001), 97–110. https://combinatorialpress.com/jcmcc-articles/volume-038/the-isometric-path-number-of-a-graph/.
- [3]P. Manuel, On the isometric path partition problem, Discuss. Math. Graph Theory 41 (2021), 1077–1089. https://doi.org/10.7151/dmgt.2236.
- [4]OEIS Foundation Inc., Entry A264041, The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A264041, accessed October 15, 2026.