mixed_cage_order_girth_three
For all r ≥ 1 and z ≥ 1, the minimum order of an (r, z, 3)-mixed cage is n(r, z, 3) = r + 2z + 1.
Statement
theorem mixed_cage_order_girth_three (r z : ℕ) (hr : 1 ≤ r) (hz : 1 ≤ z) :
mixed_cage_order r z 3 = r + 2 * z + 1- Formalizes
- arXiv:2610.14110 (New mixed cages, bounds and computational results), Theorem 5.1.
- Verified
- 17 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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).
- mixed_graph_card_ge_of_is_regularEvery (r, z)-regular mixed graph on a finite nonempty vertex set has at least r + 2z + 1 vertices.
- Used by 1
- mixed_cage_order_one_girth_threeThe case g = 3 of the conjecture: n(1, z, 3) = N(z, 3), i.e. 2z + 2 for every z ≥ 1 (both parities agree).
The proof, explained
The minimum order of an (r, z, 3)-mixed cage is shown to be r + 2z + 1 by proving matching upper and lower bounds. For the upper bound, an explicit circulant mixed graph on Fin (r + 2z + 1) is constructed with arcs for difference in [1, z] and undirected edges for difference in [z + 1, z + r], which is verified to be valid, regular with degrees (r, z), and of girth 3 (witnessed by the triangle on vertices 0, 1, and z + 1). For the lower bound, any valid regular mixed graph must satisfy the Moore-type bound |V| ≥ r + 2z + 1 (`mixed_graph_card_ge_of_is_regular`), and the girth 3 condition guarantees the vertex set is nonempty. Combining both bounds via antisymmetry completes the proof.
For any permutation f of Fin (r + 2z + 1) and any upper bound b < r + 2z + 1, the preimage of the interval [a, b] under f has cardinality b + 1 - a.
Linear arithmetic (`omega`) confirms that r + 2z + 1 ≥ 4 > 0, establishing that the modulus is non-zero (`hNz`). For the counting lemma H, the set {y | a ≤ (f y).val ∧ (f y).val ≤ b} is rewritten as the preimage under f of the subset of Fin (r + 2z + 1) whose values lie in [a, b]. Since f is a bijection, its preimage preserves cardinality by `Set.ncard_preimage_of_injective_subset_range`. Injectivity of `Fin.val` (`Fin.val_injective`) via `Set.ncard_image_of_injective` then identifies this cardinality with the size of its image in ℕ. Using `Set.mem_image`, `Set.mem_ofPred_eq`, `Finset.coe_Icc`, and `Set.mem_Icc`, this image is shown to equal the finset interval `Finset.Icc a b`, where the hypothesis b < r + 2z + 1 ensures that every integer in [a, b] comes from a valid element of Fin (r + 2z + 1). Applying `Set.ncard_coe_finset` and `Nat.card_Icc` evaluates the cardinality as b + 1 - a.
uses
Set.ncard_preimage_of_injective_subset_range,Set.ncard_image_of_injective,Fin.val_injective,Set.mem_image,Set.mem_ofPred_eq,Finset.coe_Icc,Set.mem_Icc,Set.ncard_coe_finset,Nat.card_Icchave hNz : NeZero (r + 2 * z + 1) := ⟨by omega⟩ have H : ∀ (f : Fin (r + 2 * z + 1) ≃ Fin (r + 2 * z + 1)) (a b : ℕ), b < r + 2 * z + 1 → {y | a ≤ (f y).val ∧ (f y).val ≤ b}.ncard = b + 1 - a := by intro f a b hb have e : {y | a ≤ (f y).val ∧ (f y).val ≤ b} = f ⁻¹' {d | a ≤ d.val ∧ d.val ≤ b} := rfl rw [e, Set.ncard_preimage_of_injective_subset_range f.injective (by simp), ← Set.ncard_image_of_injective _ Fin.val_injective] have : Fin.val '' {d : Fin (r + 2 * z + 1) | a ≤ d.val ∧ d.val ≤ b} = ↑(Finset.Icc a b) := by ext d simp only [Set.mem_image, Set.mem_ofPred_eq, Finset.coe_Icc, Set.mem_Icc] constructor · rintro ⟨e, he, rfl⟩; exact he · intro hd; exact ⟨⟨d, by omega⟩, hd, rfl⟩ rw [this, Set.ncard_coe_finset, Nat.card_Icc]
In Fin (r + 2z + 1), distinct elements x ≠ y satisfy (y - x).val + (x - y).val = r + 2z + 1, while (x - x).val = 0.
For distinct x ≠ y, their underlying integer values are distinct by `Fin.val_ne_of_ne`, so either x.val < y.val or y.val < x.val by `lt_or_gt_of_ne`. When x < y, modular subtraction in Fin gives (y - x).val = y.val - x.val by `Fin.coe_sub_iff_le` and `Fin.le_iff_val_le_val`, and (x - y).val = (r + 2z + 1) + x.val - y.val by `Fin.coe_sub_iff_lt` and `Fin.lt_def`. Their sum simplifies by linear arithmetic (`omega`) to r + 2z + 1. The case y < x is symmetric. Finally, `simp` proves that (x - x).val = 0 for every x.
uses
lt_or_gt_of_ne,Fin.val_ne_of_ne,Fin.coe_sub_iff_le,Fin.le_iff_val_le_val,Fin.coe_sub_iff_lt,Fin.lt_defhave key : ∀ x y : Fin (r + 2 * z + 1), x ≠ y → (y - x).val + (x - y).val = r + 2 * z + 1 := by intro x y hxy rcases lt_or_gt_of_ne (Fin.val_ne_of_ne hxy) with h | h · rw [Fin.coe_sub_iff_le.2 (Fin.le_iff_val_le_val.2 h.le), Fin.coe_sub_iff_lt.2 (Fin.lt_def.2 h)]; omega · rw [Fin.coe_sub_iff_lt.2 (Fin.lt_def.2 h), Fin.coe_sub_iff_le.2 (Fin.le_iff_val_le_val.2 h.le)]; omega have z0 : ∀ x : Fin (r + 2 * z + 1), (x - x).val = 0 := by simp
The definitions of arcs A and edges E form a well-defined loopless simple graph E and relation A on Fin (r + 2z + 1).
We define directed arcs by A x y ↔ 1 ≤ (y - x).val ≤ z and undirected edges by E.Adj x y ↔ z + 1 ≤ (y - x).val ≤ z + r. To show E is symmetric: if E.Adj x y, then x ≠ y (since x = y would yield (x - x).val = 0 ≥ z + 1, impossible as z ≥ 1). By the complementary difference identity `key`, (y - x).val + (x - y).val = r + 2z + 1, which implies (x - y).val = (r + 2z + 1) - (y - x).val also falls in [z + 1, z + r] by linear arithmetic (`omega`). Looplessness of E also holds since (x - x).val = 0 < z + 1.
let A : Fin (r + 2 * z + 1) → Fin (r + 2 * z + 1) → Prop := fun x y => 1 ≤ (y - x).val ∧ (y - x).val ≤ z let E : SimpleGraph (Fin (r + 2 * z + 1)) := { Adj := fun x y => z + 1 ≤ (y - x).val ∧ (y - x).val ≤ z + r symm := ⟨fun (x y : Fin (r + 2 * z + 1)) (h : z + 1 ≤ (y - x).val ∧ (y - x).val ≤ z + r) => by have hxy : x ≠ y := by rintro rfl; rw [z0] at h; omega have := key x y hxy constructor <;> omega⟩ loopless := ⟨fun (x : Fin (r + 2 * z + 1)) (h : z + 1 ≤ (x - x).val ∧ (x - x).val ≤ z + r) => by rw [z0] at h; omega⟩ }
The constructed mixed graph (E, A) on Fin (r + 2z + 1) is valid, regular of degree (r, z), and has girth 3.
We check the three requirements on the candidate graph (E, A): 1. Validity: Arc self-loops are impossible because (x - x).val = 0 < 1. Digons in A are impossible because if A x y and A y x, both differences are at most z, so their sum is at most 2z, contradicting that their sum is r + 2z + 1 > 2z. Edges and arcs are disjoint because E requires difference ≥ z + 1 while A requires difference ≤ z. 2. Regularity: For any vertex x, the undirected neighbors are {y | z + 1 ≤ (y - x).val ≤ z + r}, which by the bijection y ↦ y - x (`Equiv.subRight x`) and lemma H has size (z + r) + 1 - (z + 1) = r. The out-neighbors {y | 1 ≤ (y - x).val ≤ z} have size z + 1 - 1 = z by H with `Equiv.subRight x`. The in-neighbors {y | 1 ≤ (x - y).val ≤ z} have size z + 1 - 1 = z by H with the bijection y ↦ x - y (`Equiv.subLeft x`). 3. Girth 3: The sequence of vertices v₀ = 0, v₁ = 1, and v₂ = z + 1 are pairwise distinct by `Fin.ext_iff` and `omega`. The step v₀ → v₁ has difference 1 ∈ [1, z] (an arc A); v₁ → v₂ has difference z ∈ [1, z] (an arc A); and v₂ → v₀ has difference 0 - (z + 1) = r + z ∈ [z + 1, z + r] (an edge E). This establishes a 3-cycle using `Fin.coe_sub_iff_le`, `Fin.le_def`, `Fin.coe_sub_iff_lt`, and `Fin.lt_def`. Shorter cycles cannot exist because the cycle definition requires length t ≥ 3.
uses
le_rfl,Equiv.subRight,Equiv.subLeft,Fin.ext_iff,Fin.coe_sub_iff_le,Fin.le_def,Fin.coe_sub_iff_lt,Fin.lt_defhave hmem : r + 2 * z + 1 ∈ {n | ∃ (E : SimpleGraph (Fin n)) (A : Fin n → Fin n → Prop), mixed_graph_is_valid E A ∧ mixed_graph_is_regular E A r z ∧ mixed_graph_has_girth E A 3} := by refine ⟨E, A, ⟨fun x h => ?_, fun x y h h' => ?_, fun x y h h' => ?_⟩, fun x => ⟨?_, ?_, ?_⟩, ⟨⟨le_rfl, ![⟨0, by omega⟩, ⟨1, by omega⟩, ⟨z + 1, by omega⟩], ?_, ?_⟩, fun t ht h => by have := h.1; omega⟩⟩ · have := h.1; rw [z0] at this; omega · have hxy : x ≠ y := by rintro rfl; have := h.1; rw [z0] at this; omega have := key x y hxy have := h.1; have := h.2; have := h'.1; have := h'.2; omega · have := h.1; have := h'.2; omega · exact (H (Equiv.subRight x) (z + 1) (z + r) (by omega)).trans (by omega) · exact (H (Equiv.subRight x) 1 z (by omega)).trans (by omega) · exact (H (Equiv.subLeft x) 1 z (by omega)).trans (by omega) · intro i j hij fin_cases i <;> fin_cases j <;> simp_all [Fin.ext_iff] <;> omega · intro i fin_cases i · right show 1 ≤ ((⟨1, _⟩ : Fin (r + 2 * z + 1)) - ⟨0, _⟩).val ∧ ((⟨1, _⟩ : Fin (r + 2 * z + 1)) - ⟨0, _⟩).val ≤ z rw [Fin.coe_sub_iff_le.2 (Fin.le_def.2 (by simp))]; simp only []; omega · right show 1 ≤ ((⟨z + 1, _⟩ : Fin (r + 2 * z + 1)) - ⟨1, _⟩).val ∧ ((⟨z + 1, _⟩ : Fin (r + 2 * z + 1)) - ⟨1, _⟩).val ≤ z rw [Fin.coe_sub_iff_le.2 (Fin.le_def.2 (by simp))]; simp only []; omega · left show z + 1 ≤ ((⟨0, _⟩ : Fin (r + 2 * z + 1)) - ⟨z + 1, _⟩).val ∧ ((⟨0, _⟩ : Fin (r + 2 * z + 1)) - ⟨z + 1, _⟩).val ≤ z + r rw [Fin.coe_sub_iff_lt.2 (Fin.lt_def.2 (by simp))]; simp only []; omega
The mixed cage order mixed_cage_order r z 3 equals r + 2z + 1.
By partial order antisymmetry (`le_antisymm`), it suffices to show that mixed_cage_order r z 3 ≤ r + 2z + 1 and r + 2z + 1 ≤ mixed_cage_order r z 3. The upper bound follows from `Nat.sInf_le` because r + 2z + 1 belongs to the set of orders admitting an (r, z, 3)-mixed graph (witnessed by the construction above). For the lower bound, by `le_csInf`, we consider any order n admitting a valid, regular mixed graph (E, A) with girth 3. The 3-cycle yields a vertex, showing Fin n is nonempty. The theorem `mixed_graph_card_ge_of_is_regular` then gives r + 2z + 1 ≤ n, which shows r + 2z + 1 is a lower bound on all such orders, completing the proof.
uses
le_antisymm,Nat.sInf_le,le_csInf,mixed_graph_card_ge_of_is_regularrefine le_antisymm (Nat.sInf_le hmem) (le_csInf ⟨_, hmem⟩ fun n ⟨E, A, hv, hreg, hg⟩ => ?_) obtain ⟨-, x, -, -⟩ := hg.1 have : Nonempty (Fin n) := ⟨x 0⟩ simpa using mixed_graph_card_ge_of_is_regular E A r z hv hreg
Equiv.subLeft- An equivalence (bijection) on an additive group given by subtracting an element on the left: y ↦ x - y.
Equiv.subRight- An equivalence (bijection) on an additive group given by subtracting an element on the right: y ↦ y - x.
Fin.coe_sub_iff_lt- In Fin n, the value of a difference a - b is n + a.val - b.val if and only if a < b.
Fin.coe_sub_iff_le- In Fin n, the value of a difference a - b is a.val - b.val if and only if b ≤ a.
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Fin.le_def- An inequality a ≤ b in Fin n is defined by the inequality a.val ≤ b.val between their underlying values.
Fin.le_iff_val_le_val- An inequality a ≤ b in Fin n is equivalent to a.val ≤ b.val.
Fin.lt_def- A strict inequality a < b in Fin n is defined by the inequality a.val < b.val between their underlying values.
Fin.val_ne_of_ne- Distinct elements of Fin n have distinct underlying natural number values.
Fin.val_injective- The canonical coercion of Fin n to ℕ is injective.
Finset.coe_Icc- Coercing the finite integer interval [a, b] to a set produces the set-theoretic interval [a, b].
le_rfl- Inequality in a preorder is reflexive: a ≤ a.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
le_csInf- A lower bound of a nonempty set in a conditionally complete lattice is at most the infimum of the set.
lt_or_gt_of_ne- Two distinct elements in a linear order satisfy either a < b or b < a.
mixed_graph_card_ge_of_is_regular- Any valid, regular mixed graph with undirected degree r and directed degree z on a nonempty finite type has order at least r + 2z + 1.
Nat.card_Icc- The number of natural numbers in the closed interval [a, b] is b + 1 - a.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element belonging to the set.
Set.mem_Icc- An element x belongs to the closed interval [a, b] if and only if a ≤ x ≤ b.
Set.mem_image- An element y belongs to the image f(s) if and only if y = f(x) for some x ∈ s.
Set.mem_ofPred_eq- Membership of x in the set-builder comprehension {y | p y} is equivalent to p(x).
Set.ncard_coe_finset- The set cardinality of a coerced finite set equals its finset cardinality.
Set.ncard_image_of_injective- An injective map preserves the cardinality of the image of any set.
Set.ncard_preimage_of_injective_subset_range- An injective map preserves the cardinality of the preimage of any subset of its range.
- The hypothesis `hNz` (line 3) establishes `NeZero (r + 2 * z + 1)`, a technical typeclass instance required by Lean to equip `Fin (r + 2 * z + 1)` with subtraction and additive group operations.
- The formal definition `mixed_graph_has_cycle` includes the clause `3 ≤ t`, so the non-existence of cycles of length strictly less than 3 holds directly by definition.
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_girth_three (r z : ℕ) (hr : 1 ≤ r) (hz : 1 ≤ z) : mixed_cage_order r z 3 = r + 2 * z + 1 := by have hNz : NeZero (r + 2 * z + 1) := ⟨by omega⟩ have H : ∀ (f : Fin (r + 2 * z + 1) ≃ Fin (r + 2 * z + 1)) (a b : ℕ), b < r + 2 * z + 1 → {y | a ≤ (f y).val ∧ (f y).val ≤ b}.ncard = b + 1 - a := by intro f a b hb have e : {y | a ≤ (f y).val ∧ (f y).val ≤ b} = f ⁻¹' {d | a ≤ d.val ∧ d.val ≤ b} := rfl rw [e, Set.ncard_preimage_of_injective_subset_range f.injective (by simp), ← Set.ncard_image_of_injective _ Fin.val_injective] have : Fin.val '' {d : Fin (r + 2 * z + 1) | a ≤ d.val ∧ d.val ≤ b} = ↑(Finset.Icc a b) := by ext d simp only [Set.mem_image, Set.mem_ofPred_eq, Finset.coe_Icc, Set.mem_Icc] constructor · rintro ⟨e, he, rfl⟩; exact he · intro hd; exact ⟨⟨d, by omega⟩, hd, rfl⟩ rw [this, Set.ncard_coe_finset, Nat.card_Icc] have key : ∀ x y : Fin (r + 2 * z + 1), x ≠ y → (y - x).val + (x - y).val = r + 2 * z + 1 := by intro x y hxy rcases lt_or_gt_of_ne (Fin.val_ne_of_ne hxy) with h | h · rw [Fin.coe_sub_iff_le.2 (Fin.le_iff_val_le_val.2 h.le), Fin.coe_sub_iff_lt.2 (Fin.lt_def.2 h)]; omega · rw [Fin.coe_sub_iff_lt.2 (Fin.lt_def.2 h), Fin.coe_sub_iff_le.2 (Fin.le_iff_val_le_val.2 h.le)]; omega have z0 : ∀ x : Fin (r + 2 * z + 1), (x - x).val = 0 := by simp let A : Fin (r + 2 * z + 1) → Fin (r + 2 * z + 1) → Prop := fun x y => 1 ≤ (y - x).val ∧ (y - x).val ≤ z let E : SimpleGraph (Fin (r + 2 * z + 1)) := { Adj := fun x y => z + 1 ≤ (y - x).val ∧ (y - x).val ≤ z + r symm := ⟨fun (x y : Fin (r + 2 * z + 1)) (h : z + 1 ≤ (y - x).val ∧ (y - x).val ≤ z + r) => by have hxy : x ≠ y := by rintro rfl; rw [z0] at h; omega have := key x y hxy constructor <;> omega⟩ loopless := ⟨fun (x : Fin (r + 2 * z + 1)) (h : z + 1 ≤ (x - x).val ∧ (x - x).val ≤ z + r) => by rw [z0] at h; omega⟩ } have hmem : r + 2 * z + 1 ∈ {n | ∃ (E : SimpleGraph (Fin n)) (A : Fin n → Fin n → Prop), mixed_graph_is_valid E A ∧ mixed_graph_is_regular E A r z ∧ mixed_graph_has_girth E A 3} := by refine ⟨E, A, ⟨fun x h => ?_, fun x y h h' => ?_, fun x y h h' => ?_⟩, fun x => ⟨?_, ?_, ?_⟩, ⟨⟨le_rfl, ![⟨0, by omega⟩, ⟨1, by omega⟩, ⟨z + 1, by omega⟩], ?_, ?_⟩, fun t ht h => by have := h.1; omega⟩⟩ · have := h.1; rw [z0] at this; omega · have hxy : x ≠ y := by rintro rfl; have := h.1; rw [z0] at this; omega have := key x y hxy have := h.1; have := h.2; have := h'.1; have := h'.2; omega · have := h.1; have := h'.2; omega · exact (H (Equiv.subRight x) (z + 1) (z + r) (by omega)).trans (by omega) · exact (H (Equiv.subRight x) 1 z (by omega)).trans (by omega) · exact (H (Equiv.subLeft x) 1 z (by omega)).trans (by omega) · intro i j hij fin_cases i <;> fin_cases j <;> simp_all [Fin.ext_iff] <;> omega · intro i fin_cases i · right show 1 ≤ ((⟨1, _⟩ : Fin (r + 2 * z + 1)) - ⟨0, _⟩).val ∧ ((⟨1, _⟩ : Fin (r + 2 * z + 1)) - ⟨0, _⟩).val ≤ z rw [Fin.coe_sub_iff_le.2 (Fin.le_def.2 (by simp))]; simp only []; omega · right show 1 ≤ ((⟨z + 1, _⟩ : Fin (r + 2 * z + 1)) - ⟨1, _⟩).val ∧ ((⟨z + 1, _⟩ : Fin (r + 2 * z + 1)) - ⟨1, _⟩).val ≤ z rw [Fin.coe_sub_iff_le.2 (Fin.le_def.2 (by simp))]; simp only []; omega · left show z + 1 ≤ ((⟨0, _⟩ : Fin (r + 2 * z + 1)) - ⟨z + 1, _⟩).val ∧ ((⟨0, _⟩ : Fin (r + 2 * z + 1)) - ⟨z + 1, _⟩).val ≤ z + r rw [Fin.coe_sub_iff_lt.2 (Fin.lt_def.2 (by simp))]; simp only []; omega refine le_antisymm (Nat.sInf_le hmem) (le_csInf ⟨_, hmem⟩ fun n ⟨E, A, hv, hreg, hg⟩ => ?_) obtain ⟨-, x, -, -⟩ := hg.1 have : Nonempty (Fin n) := ⟨x 0⟩ simpa using mixed_graph_card_ge_of_is_regular E A r z hv hreg