mixed_cage_order_one_le
For z ≥ 1 and g ≥ 3, n(1, z, g) ≤ N(z, g), where N(z, g) = z(g − 1) + 2 for even z and (z + 1)(g − 1) for odd z: the circulant M(z, g) on 2m = N(z, g) vertices with arcs of jumps 1..⌈z/2⌉ and m+1..m+⌊z/2⌋ and the antipodal edges is a (1, z, g)-mixed graph.
Statement
theorem mixed_cage_order_one_le (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) : mixed_cage_order 1 z g ≤ if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1)
- Formalizes
- arXiv:2610.14110 (New mixed cages, bounds and computational results), Theorem 4.2 (with Definition 4.1).
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- mixed_graph_is_validA mixed graph on V: undirected edges E (a simple graph) and arcs A, with no loops and at most one edge or arc between two vertices (no…
- mixed_graph_is_regularA mixed graph is (r, z)-regular when every vertex has r neighbours along edges, z out-neighbours and z in-neighbours along arcs.
- mixed_graph_has_cycleA mixed graph has a cycle of length t ≥ 3: distinct vertices x_0, ..., x_{t-1} such that each x_i is joined to x_{i+1} (indices mod t) by…
- mixed_graph_has_girthA mixed graph has girth g: it has a cycle of length g and no shorter cycle.
- mixed_cage_ordern(r, z, g): the minimum order of an (r, z)-regular mixed graph of girth g (the order of an (r, z, g)-mixed cage).
- circulant_mixed_graph_valid_and_regularFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N = N(z, g) vertices with antipodal edges of jump m = N/2 and arc jumps 1..⌈z/2⌉ and…
- circulant_mixed_graph_cycle_g_existsFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N(z, g) vertices has a mixed cycle of length g: when z is even, g - 1 arc steps of jump…
- circulant_mixed_graph_no_cycle_lt_gFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N(z, g) vertices contains no mixed cycle of length t < g.
The proof, explained
The theorem establishes an upper bound on the order of a (1, z)-mixed cage with girth g. By definition, the cage order is the infimum over the orders of all valid (1, z)-regular mixed graphs of girth g, so it suffices to construct a single such graph of order N. The proof invokes helper lemmas showing that an explicit circulant mixed graph on N vertices satisfies all required conditions: it is valid, (1, z)-regular, has a cycle of length g, and has no shorter cycles.
It suffices to show that N = if Even z then z(g - 1) + 2 else (z + 1)(g - 1) is the order of some valid (1, z)-regular mixed graph of girth g.
Unfolding the definition of mixed_cage_order as the infimum of orders of valid (1, z)-regular mixed graphs of girth g, Nat.sInf_le reduces proving the upper bound to exhibiting a single valid (1, z)-regular mixed graph on N vertices with girth g.
uses
Nat.sInf_leunfold mixed_cage_order apply Nat.sInf_le
The canonical circulant mixed graph on N vertices is valid, (1, z)-regular, contains a cycle of length g, and contains no cycle of length less than g.
Three specialized lemmas establish the required properties for the circulant mixed graph on N vertices: circulant_mixed_graph_valid_and_regular establishes its validity and degree regularity, circulant_mixed_graph_cycle_g_exists yields a cycle of length g, and circulant_mixed_graph_no_cycle_lt_g ensures there are no cycles of length strictly less than g.
uses
circulant_mixed_graph_valid_and_regular,circulant_mixed_graph_cycle_g_exists,circulant_mixed_graph_no_cycle_lt_ghave h1 := circulant_mixed_graph_valid_and_regular z g hz hg have h2 := circulant_mixed_graph_cycle_g_exists z g hz hg have h3 := circulant_mixed_graph_no_cycle_lt_g z g hz hg
The candidate order N satisfies the defining condition of the set, completing the proof.
After unfolding the let-bindings in the established hypotheses, the edge relation and arc relation of the circulant graph serve as witnesses: validity and regularity (from h1) together with the girth condition (cycle of length g from h2 and no shorter cycles from h3) show that N belongs to the set of admissible graph orders.
dsimp only at h1 h2 h3 exact ⟨_, _, h1.1, h1.2, h2, h3⟩
Nat.sInf_le- If an element m belongs to a set of natural numbers s, then the infimum (least element) of s is at most m.
circulant_mixed_graph_valid_and_regular- For z ≥ 1 and g ≥ 3, the circulant mixed graph on N vertices is valid (no self-loops, no opposite directed arcs, and disjoint edge and arc sets) and regular with undirected degree 1 and directed degree z.
circulant_mixed_graph_cycle_g_exists- For z ≥ 1 and g ≥ 3, the circulant mixed graph on N vertices contains a cycle of length g.
circulant_mixed_graph_no_cycle_lt_g- For z ≥ 1 and g ≥ 3, the circulant mixed graph on N vertices contains no cycle of length strictly less than g.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem mixed_cage_order_one_le (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) : mixed_cage_order 1 z g ≤ if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1) := by unfold mixed_cage_order apply Nat.sInf_le have h1 := circulant_mixed_graph_valid_and_regular z g hz hg have h2 := circulant_mixed_graph_cycle_g_exists z g hz hg have h3 := circulant_mixed_graph_no_cycle_lt_g z g hz hg dsimp only at h1 h2 h3 exact ⟨_, _, h1.1, h1.2, h2, h3⟩