AFTD Auto-Formalizing Theoretical Domains

mixed_cage_order_one_le

theoremverifiedformalization

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.

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

    lines 3–4

    uses Nat.sInf_le

      unfold mixed_cage_order
      apply Nat.sInf_le
  2. 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.

    lines 5–7

    uses circulant_mixed_graph_valid_and_regular, circulant_mixed_graph_cycle_g_exists, circulant_mixed_graph_no_cycle_lt_g

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

    lines 8–9

      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

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