AFTD Auto-Formalizing Theoretical Domains

mixed_cage_order_one_girth_three

theoremverifiedformalization

The case g = 3 of the conjecture: n(1, z, 3) = N(z, 3), i.e. 2z + 2 for every z ≥ 1 (both parities agree).

Statement

theorem mixed_cage_order_one_girth_three (z : ℕ) (hz : 1 ≤ z) :
    mixed_cage_order 1 z 3 = if Even z then z * (3 - 1) + 2 else (z + 1) * (3 - 1)
Formalizes
arXiv:2610.14110 (New mixed cages, bounds and computational results), Theorem 5.1 with r = 1 (the case g = 3 of Conjecture 2).
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_cage_order_girth_threeFor all r ≥ 1 and z ≥ 1, the minimum order of an (r, z, 3)-mixed cage is n(r, z, 3) = r + 2z + 1.

The proof, explained

The proof evaluates the mixed cage order for r = 1 and girth 3 using the known formula mixed_cage_order_girth_three, obtaining 1 + 2z + 1. It then performs a case split on the parity of z and verifies by linear arithmetic that 1 + 2z + 1 matches both z * (3 - 1) + 2 in the even case and (z + 1) * (3 - 1) in the odd case.

  1. The order of an (r=1, z)-mixed cage of girth 3 simplifies to 1 + 2z + 1.

    We rewrite the left-hand side using the general formula mixed_cage_order_girth_three instantiated at r = 1 and z, where the condition 1 ≤ 1 is proved by reflexivity (le_rfl) and 1 ≤ z is provided by the hypothesis hz.

    line 3

    uses mixed_cage_order_girth_three, le_rfl

      rw [mixed_cage_order_girth_three 1 z le_rfl hz]
  2. The identity holds whether z is even or odd. automation

    We split on the conditional condition (Even z). In the even case, the goal is 1 + 2z + 1 = z * (3 - 1) + 2, and in the odd case, it is 1 + 2z + 1 = (z + 1) * (3 - 1). Both are identities in linear arithmetic on natural numbers (both sides equal 2z + 2) and are closed by omega.

    line 4

      split_ifs <;> omega
mixed_cage_order_girth_three
For any r ≥ 1 and z ≥ 1, the order of an (r, z)-mixed cage of girth 3 is r + 2z + 1.
le_rfl
Any element in a preorder is less than or equal to itself (a ≤ a).

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_one_girth_three (z : ℕ) (hz : 1 ≤ z) :    mixed_cage_order 1 z 3 = if Even z then z * (3 - 1) + 2 else (z + 1) * (3 - 1) := by  rw [mixed_cage_order_girth_three 1 z le_rfl hz]  split_ifs <;> omega
See it in the graphDiscuss this resultChallenge it