AFTD Auto-Formalizing Theoretical Domains

mixed_cage_order_girth_three

theoremverifiedformalization

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

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.

  1. 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.

    lines 3–16

    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_Icc

      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]
  2. 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.

    lines 17–24

    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_def

      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
  3. 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.

    lines 25–35

      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⟩ }
  4. 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.

    lines 36–64

    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_def

      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
  5. 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.

    lines 65–68

    uses le_antisymm, Nat.sInf_le, le_csInf, mixed_graph_card_ge_of_is_regular

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it