AFTD Auto-Formalizing Theoretical Domains

circulant_mixed_graph_cycle_g_exists

theoremverified

For 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 z/2 followed by one arc step of jump m + 1; when z is odd, g - 1 arc steps of jump (z+1)/2 followed by one edge step of jump m.

Statement

theorem circulant_mixed_graph_cycle_g_exists (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) :
    let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1)
    let m := N / 2
    let E := SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m
    let A : Fin N → Fin N → Prop := fun x y =>
      (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨
      (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2)
    mixed_graph_has_cycle E A g
Source
step towards mixed_cage_order_one_le
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1
  • mixed_cage_order_one_leFor 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…

The proof, explained

To find a mixed cycle of length g ≥ 3 in the circulant mixed graph on N vertices, the vertices are chosen as x_i = i * ((z + 1) / 2) for i = 0, ..., g - 1. With n = g - 1, each of the first n steps advances by the constant jump (z + 1) / 2, which falls into the first allowed interval of directed arcs in A. The closing step from x_n back to x_0 = 0 wraps around modulo N with jump N - n * ((z + 1) / 2). When z is even, this modular jump simplifies to m + 1, forming an arc in A; when z is odd, it simplifies to m, forming an undirected edge in E.

  1. In Fin N, if y.val = x.val + h and x.val + h < N, then (y - x).val = h.

    By definition, the value of y - x in Fin N is (N - x.val + y.val) % N. Substituting y.val = x.val + h gives (N + h) % N, which equals h % N, and since h < N, this reduces to h.

    lines 1–10

    uses Fin.sub_def, Nat.add_mod_left, Nat.mod_eq_of_lt

    lemma circulant_mixed_graph_cycle_g_exists_sub_eq_of_add_eq {N : ℕ} (x y : Fin N) (h : ℕ)
        (hy : y.val = x.val + h) (hN : x.val + h < N) :
        (y - x).val = h := by
      have _ := hN
      rw [Fin.sub_def]
      dsimp
      have hlt : h < N := by omega
      have : N - x.val + y.val = N + h := by omega
      rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt hlt]
    
  2. In Fin N, if x.val > 0 and zero.val = 0, then (zero - x).val = N - x.val.

    By Fin subtraction, (0 - x).val = (N - x.val + 0) % N = (N - x.val) % N. Because 0 < x.val < N, the remainder N - x.val is strictly between 0 and N, so the modulo operation is the identity.

    lines 11–21

    uses Fin.sub_def, Nat.mod_eq_of_lt

    lemma circulant_mixed_graph_cycle_g_exists_sub_zero_eq {N : ℕ} (x : Fin N)
        (zero : Fin N) (hzero : zero.val = 0) (hx : 0 < x.val) :
        (zero - x).val = N - x.val := by
      rw [Fin.sub_def]
      dsimp
      rw [hzero]
      have : N - x.val + 0 = N - x.val := by omega
      rw [this]
      have : N - x.val < N := by omega
      exact Nat.mod_eq_of_lt this
    
  3. For even z ≥ 1, the graph parameters N = z*n + 2, m = N/2, and h = (z+1)/2 satisfy h = z/2, 1 ≤ h, N = 2m, m = n*h + 1, N - n*h = m + 1, m + 1 ≤ m + z/2, and i*h < N for all i ≤ n.

    Writing z = 2k with k ≥ 1, integer division gives h = (2k + 1)/2 = k = z/2. Then N = 2kn + 2 = 2(nk + 1), so m = nk + 1 = n*h + 1. The difference N - n*h simplifies to 2kn + 2 - nk = nk + 2 = m + 1. Since k ≥ 1, m + 1 ≤ m + k. Finally, for i ≤ n, i*k ≤ n*k < 2nk + 2 = N.

    lines 22–55

    uses Nat.mul_div_right, Nat.mul_le_mul_right

    lemma circulant_mixed_graph_cycle_g_exists_arith_even
        (z n : ℕ) (hz : 1 ≤ z) (he : Even z) :
        let N := z * n + 2
        let m := N / 2
        let h := (z + 1) / 2
        h = z / 2 ∧
        1 ≤ h ∧
        N = 2 * m ∧
        m = n * h + 1 ∧
        N - n * h = m + 1 ∧
        m + 1 ≤ m + z / 2 ∧
        ∀ i < n + 1, i * h < N := by
      intro N m h
      obtain ⟨k, rfl⟩ := he
      have hk : 1 ≤ k := by omega
      have h_div : (k + k + 1) / 2 = k := by omega
      have hz_div : (k + k) / 2 = k := by omega
      have hN_eq : (k + k) * n + 2 = 2 * (n * k + 1) := by ring
      have hm_eq : ((k + k) * n + 2) / 2 = n * k + 1 := by
        rw [hN_eq, Nat.mul_div_right _ (by omega)]
      change (k + k + 1) / 2 = (k + k) / 2 ∧
        1 ≤ (k + k + 1) / 2 ∧
        (k + k) * n + 2 = 2 * (((k + k) * n + 2) / 2) ∧
        ((k + k) * n + 2) / 2 = n * ((k + k + 1) / 2) + 1 ∧
        (k + k) * n + 2 - n * ((k + k + 1) / 2) = ((k + k) * n + 2) / 2 + 1 ∧
        ((k + k) * n + 2) / 2 + 1 ≤ ((k + k) * n + 2) / 2 + (k + k) / 2 ∧
        ∀ i < n + 1, i * ((k + k + 1) / 2) < (k + k) * n + 2
      rw [h_div, hz_div, hm_eq]
      refine ⟨rfl, hk, by omega, by omega, by omega, by omega, ?_⟩
      intro i hi
      have : i ≤ n := by omega
      have : i * k ≤ n * k := Nat.mul_le_mul_right k this
      omega
    
  4. For odd z ≥ 1 and n ≥ 2, the graph parameters N = (z+1)*n, m = N/2, and h = (z+1)/2 satisfy 1 ≤ h, N = 2m, m = n*h, N - n*h = m, 0 < m, and i*h < N for all i ≤ n.

    Writing z = 2k + 1, the step size h is (2k + 2)/2 = k + 1 ≥ 1. Then N = 2(k + 1)n = 2(n*h), so m = n*h and N = 2m. The difference N - n*h is 2nh - nh = nh = m. Since n ≥ 2 and h ≥ 1, m > 0. For i ≤ n, i*h ≤ n*h = m < 2m = N.

    lines 56–87

    uses Nat.not_even_iff_odd.mp, Nat.mul_div_right, Nat.mul_le_mul_right

    lemma circulant_mixed_graph_cycle_g_exists_arith_odd
        (z n : ℕ) (hz : 1 ≤ z) (hn : 2 ≤ n) (he : ¬ Even z) :
        let N := (z + 1) * n
        let m := N / 2
        let h := (z + 1) / 2
        1 ≤ h ∧
        N = 2 * m ∧
        m = n * h ∧
        N - n * h = m ∧
        0 < m ∧
        ∀ i < n + 1, i * h < N := by
      intro N m h
      dsimp [N, m, h]
      obtain ⟨k, rfl⟩ : ∃ k, z = 2 * k + 1 := Nat.not_even_iff_odd.mp he
      have h_div : (2 * k + 1 + 1) / 2 = k + 1 := by omega
      have hN_eq : (2 * k + 1 + 1) * n = 2 * (n * (k + 1)) := by ring
      have hm_eq : ((2 * k + 1 + 1) * n) / 2 = n * (k + 1) := by
        rw [hN_eq, Nat.mul_div_right _ (by omega)]
      have h1 : 1 ≤ (2 * k + 1 + 1) / 2 := by rw [h_div]; omega
      have h2 : (2 * k + 1 + 1) * n = 2 * (((2 * k + 1 + 1) * n) / 2) := by rw [hm_eq]; ring
      have h3 : ((2 * k + 1 + 1) * n) / 2 = n * ((2 * k + 1 + 1) / 2) := by rw [hm_eq, h_div]
      have h4 : (2 * k + 1 + 1) * n - n * ((2 * k + 1 + 1) / 2) = ((2 * k + 1 + 1) * n) / 2 := by
        rw [hm_eq, h_div]; omega
      have h5 : 0 < ((2 * k + 1 + 1) * n) / 2 := by rw [hm_eq]; nlinarith
      refine ⟨h1, h2, h3, h4, h5, ?_⟩
      intro i hi
      rw [h_div]
      have : i ≤ n := by omega
      have : i * (k + 1) ≤ n * (k + 1) := Nat.mul_le_mul_right (k + 1) this
      have : n * (k + 1) < 2 * (n * (k + 1)) := by nlinarith
      linarith
    
  5. Set n = g - 1 ≥ 2, so that the cycle length condition 3 ≤ n + 1 = g is satisfied.

    Writing g as n + 1 where n = g - 1, the hypothesis g ≥ 3 implies n ≥ 2, satisfying the requirement that the cycle length is at least 3.

    lines 88–101

    /-- The circulant mixed graph M(z, g) contains a mixed cycle of length g. -/
    theorem circulant_mixed_graph_cycle_g_exists (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) :
        let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1)
        let m := N / 2
        let E := SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m
        let A : Fin N → Fin N → Prop := fun x y =>
          (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨
          (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2)
        mixed_graph_has_cycle E A g := by
      obtain ⟨n, rfl⟩ : ∃ n, g = n + 1 := ⟨g - 1, by omega⟩
      have hn : 2 ≤ n := by omega
      intro N m E A
      have hg_le : 3 ≤ n + 1 := hg
      refine ⟨hg_le, ?_⟩
  6. Define the cycle vertices x_i = i * ((z + 1) / 2) in Fin N for each index i ∈ Fin (n + 1).

    By the arithmetic bounds established in the even and odd cases, i * ((z + 1) / 2) < N holds for all i < n + 1. Thus each vertex x i can be defined directly by this natural number value without modular wraparound.

    lines 102–109

    uses circulant_mixed_graph_cycle_g_exists_arith_even, circulant_mixed_graph_cycle_g_exists_arith_odd

      have h_bound : ∀ i < n + 1, i * ((z + 1) / 2) < N := by
        intro i hi
        dsimp [N]
        split_ifs with he
        · exact (circulant_mixed_graph_cycle_g_exists_arith_even z n hz he).2.2.2.2.2.2 i hi
        · exact (circulant_mixed_graph_cycle_g_exists_arith_odd z n hz hn he).2.2.2.2.2 i hi
      let x : Fin (n + 1) → Fin N := fun i => ⟨i.val * ((z + 1) / 2), h_bound i.val i.isLt⟩
      refine ⟨x, ?_, ?_⟩
  7. The vertex map x : Fin (n + 1) → Fin N is injective.

    If x i = x j, then i * ((z + 1) / 2) = j * ((z + 1) / 2). Because z ≥ 1, the jump (z + 1) / 2 is strictly positive, so right multiplication cancellation on natural numbers yields i = j.

    lines 110–114

    uses Fin.mk.injEq, Fin.ext, Nat.eq_of_mul_eq_mul_right

      · -- Injective
        intro i j hij
        simp only [x, Fin.mk.injEq] at hij
        have hpos : 0 < (z + 1) / 2 := by omega
        exact Fin.ext (Nat.eq_of_mul_eq_mul_right hpos hij)
  8. At the closing index i = n, cyclic rotation maps n to 0, and the jump is (x_0 - x_n).val = N - n * ((z + 1) / 2).

    When i = Fin.last n, cyclic rotation gives finRotate (n + 1) n = 0, so x (finRotate (n + 1) i) = x 0 = 0. Because x n = n * ((z + 1) / 2) > 0, applying the lemma for subtraction from zero yields (0 - x_n).val = N - n * ((z + 1) / 2).

    lines 115–134

    uses finRotate_last, Fin.val_zero, Nat.zero_mul, circulant_mixed_graph_cycle_g_exists_sub_zero_eq

      · -- Cycle condition
        intro i
        have hx_val : ∀ j : Fin (n + 1), (x j).val = j.val * ((z + 1) / 2) := fun _ => rfl
        by_cases hi : i = Fin.last n
        · -- hi : i = Fin.last n
          have hrot : finRotate (n + 1) i = 0 := by
            rw [hi, finRotate_last]
          have hi_val : i.val = n := by
            rw [hi]
            rfl
          have hrot_val : (x (finRotate (n + 1) i)).val = 0 := by
            rw [hrot, hx_val, Fin.val_zero, Nat.zero_mul]
          have hx_i_pos : 0 < (x i).val := by
            rw [hx_val, hi_val]
            have : 0 < (z + 1) / 2 := by omega
            nlinarith
          have hsub : (x (finRotate (n + 1) i) - x i).val = N - n * ((z + 1) / 2) := by
            have := circulant_mixed_graph_cycle_g_exists_sub_zero_eq (x i)
              (x (finRotate (n + 1) i)) hrot_val hx_i_pos
            rw [this, hx_val, hi_val]
  9. When z is even, the closing step from x_n to x_0 is a directed arc in A of jump m + 1.

    When z is even, N = z*n + 2 and the closing jump N - n * ((z + 1) / 2) evaluates to m + 1. Since m + 1 ≤ m + z/2, this jump lies in the second arc interval [m + 1, m + z/2], proving that the pair belongs to A.

    lines 135–146

    uses circulant_mixed_graph_cycle_g_exists_arith_even, if_pos, le_rfl

          by_cases he : Even z
          · -- Even z
            obtain ⟨he1, he2, he3, he4, he5, he6, he7⟩ :=
              circulant_mixed_graph_cycle_g_exists_arith_even z n hz he
            have hN_eq : N = z * n + 2 := by dsimp [N]; rw [if_pos he]
            have hm_eq : m = (z * n + 2) / 2 := by dsimp [m]; rw [hN_eq]
            have hsub' : (x (finRotate (n + 1) i) - x i).val = m + 1 := by
              rw [hsub, hN_eq, he5, ← hm_eq]
            right
            right
            rw [hsub', hm_eq]
            exact ⟨le_rfl, he6⟩
  10. When z is odd, the closing step from x_n to x_0 is an undirected edge in E of jump m.

    When z is odd, N = (z + 1)*n and the closing jump N - n * ((z + 1) / 2) evaluates to m. Since x n > 0 = x 0, the two vertices are distinct, so they form an undirected edge in SimpleGraph.fromRel with difference m.

    lines 147–164

    uses circulant_mixed_graph_cycle_g_exists_arith_odd, if_neg, SimpleGraph.fromRel_adj, Or.inl, congrArg

          · -- Odd z
            obtain ⟨ho1, ho2, ho3, ho4, ho5, ho6⟩ :=
              circulant_mixed_graph_cycle_g_exists_arith_odd z n hz hn he
            have hN_eq : N = (z + 1) * n := by dsimp [N]; rw [if_neg he]
            have hm_eq : m = ((z + 1) * n) / 2 := by dsimp [m]; rw [hN_eq]
            have hsub' : (x (finRotate (n + 1) i) - x i).val = m := by
              rw [hsub, hN_eq, ho4, ← hm_eq]
            left
            rw [SimpleGraph.fromRel_adj]
            refine ⟨?_, Or.inl hsub'⟩
            intro h_eq
            have : (x i).val = (x (finRotate (n + 1) i)).val := congrArg Fin.val h_eq
            rw [hx_val, hi_val, hrot_val] at this
            have : 0 < n * ((z + 1) / 2) := by
              have : 0 < n := by omega
              have : 0 < (z + 1) / 2 := by omega
              positivity
            omega
  11. For each non-closing index i < n, the step from x_i to x_{i+1} is a directed arc in A of jump (z + 1) / 2.

    For i < n, cyclic rotation advances i to i + 1, so x_{i+1}.val = x_i.val + (z + 1) / 2 < N. By the lemma for subtraction of an added offset, (x_{i+1} - x_i).val = (z + 1) / 2. Since 1 ≤ (z + 1) / 2 ≤ (z + 1) / 2, this jump lies in the first arc interval [1, (z + 1) / 2], confirming that the pair belongs to A.

    lines 165–180

    uses coe_finRotate_of_ne_last, circulant_mixed_graph_cycle_g_exists_sub_eq_of_add_eq, le_rfl

        · -- hi : i ≠ Fin.last n
          have hrot : (finRotate (n + 1) i).val = i.val + 1 := coe_finRotate_of_ne_last hi
          have hsub : (x (finRotate (n + 1) i) - x i).val = (z + 1) / 2 := by
            have hy_eq : (x (finRotate (n + 1) i)).val = (x i).val + (z + 1) / 2 := by
              rw [hx_val, hx_val, hrot]
              ring
            have hN_lt : (x i).val + (z + 1) / 2 < N := by
              rw [← hy_eq]
              exact (x (finRotate (n + 1) i)).isLt
            exact circulant_mixed_graph_cycle_g_exists_sub_eq_of_add_eq (x i)
              (x (finRotate (n + 1) i)) ((z + 1) / 2) hy_eq hN_lt
          right
          left
          rw [hsub]
          have : 1 ≤ (z + 1) / 2 := by omega
          exact ⟨this, le_rfl⟩
Fin.sub_def
In Fin n, the subtraction a - b is computed by (n - b + a) % n.
Nat.add_mod_left
For natural numbers x and z, (x + z) % x = z % x.
Nat.mod_eq_of_lt
If a < b, then a % b = a.
Nat.mul_div_right
For m > 0, (m * n) / m = n.
Nat.mul_le_mul_right
If n ≤ m, then n * k ≤ m * k.
Nat.not_even_iff_odd.mp
If a natural number is not even, it is odd (expressible as 2k + 1).
circulant_mixed_graph_cycle_g_exists_arith_even
For z ≥ 1 even, setting N = z*n + 2, m = N/2, and h = (z+1)/2, we have h = z/2, 1 ≤ h, N = 2m, m = n*h + 1, N - n*h = m + 1, m + 1 ≤ m + z/2, and i*h < N for all i ≤ n.
circulant_mixed_graph_cycle_g_exists_arith_odd
For z ≥ 1 odd and n ≥ 2, setting N = (z+1)*n, m = N/2, and h = (z+1)/2, we have 1 ≤ h, N = 2m, m = n*h, N - n*h = m, 0 < m, and i*h < N for all i ≤ n.
Fin.mk.injEq
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Fin.ext
Two elements of Fin n are equal if their values as natural numbers are equal.
Nat.eq_of_mul_eq_mul_right
If m > 0 and n * m = k * m, then n = k.
finRotate_last
Cyclic rotation on Fin (n + 1) maps the last element n to 0.
Fin.val_zero
The value of 0 in Fin n as a natural number is 0.
Nat.zero_mul
Multiplying 0 by any natural number yields 0.
circulant_mixed_graph_cycle_g_exists_sub_zero_eq
In Fin N, if x > 0 and zero has value 0, then (zero - x).val = N - x.val.
if_pos
If condition c is true, then (if c then t else e) evaluates to t.
le_rfl
Every element is less than or equal to itself.
if_neg
If condition c is false, then (if c then t else e) evaluates to e.
SimpleGraph.fromRel_adj
Vertices v and w are adjacent in SimpleGraph.fromRel r if and only if v ≠ w and either r v w or r w v holds.
Or.inl
A disjunction a ∨ b holds whenever the left disjunct a holds.
congrArg
Applying a function to equal arguments yields equal results.
coe_finRotate_of_ne_last
For i ≠ Fin.last n in Fin (n + 1), the cyclic rotation of i has numerical value i.val + 1.
circulant_mixed_graph_cycle_g_exists_sub_eq_of_add_eq
In Fin N, if y.val = x.val + h and x.val + h < N, then (y - x).val = h.

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

lemma circulant_mixed_graph_cycle_g_exists_sub_eq_of_add_eq {N : ℕ} (x y : Fin N) (h : ℕ)    (hy : y.val = x.val + h) (hN : x.val + h < N) :    (y - x).val = h := by  have _ := hN  rw [Fin.sub_def]  dsimp  have hlt : h < N := by omega  have : N - x.val + y.val = N + h := by omega  rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt hlt]lemma circulant_mixed_graph_cycle_g_exists_sub_zero_eq {N : ℕ} (x : Fin N)    (zero : Fin N) (hzero : zero.val = 0) (hx : 0 < x.val) :    (zero - x).val = N - x.val := by  rw [Fin.sub_def]  dsimp  rw [hzero]  have : N - x.val + 0 = N - x.val := by omega  rw [this]  have : N - x.val < N := by omega  exact Nat.mod_eq_of_lt thislemma circulant_mixed_graph_cycle_g_exists_arith_even    (z n : ℕ) (hz : 1 ≤ z) (he : Even z) :    let N := z * n + 2    let m := N / 2    let h := (z + 1) / 2    h = z / 2 ∧    1 ≤ h ∧    N = 2 * m ∧    m = n * h + 1 ∧    N - n * h = m + 1 ∧    m + 1 ≤ m + z / 2 ∧    ∀ i < n + 1, i * h < N := by  intro N m h  obtain ⟨k, rfl⟩ := he  have hk : 1 ≤ k := by omega  have h_div : (k + k + 1) / 2 = k := by omega  have hz_div : (k + k) / 2 = k := by omega  have hN_eq : (k + k) * n + 2 = 2 * (n * k + 1) := by ring  have hm_eq : ((k + k) * n + 2) / 2 = n * k + 1 := by    rw [hN_eq, Nat.mul_div_right _ (by omega)]  change (k + k + 1) / 2 = (k + k) / 2 ∧    1 ≤ (k + k + 1) / 2 ∧    (k + k) * n + 2 = 2 * (((k + k) * n + 2) / 2) ∧    ((k + k) * n + 2) / 2 = n * ((k + k + 1) / 2) + 1 ∧    (k + k) * n + 2 - n * ((k + k + 1) / 2) = ((k + k) * n + 2) / 2 + 1 ∧    ((k + k) * n + 2) / 2 + 1 ≤ ((k + k) * n + 2) / 2 + (k + k) / 2 ∧    ∀ i < n + 1, i * ((k + k + 1) / 2) < (k + k) * n + 2  rw [h_div, hz_div, hm_eq]  refine ⟨rfl, hk, by omega, by omega, by omega, by omega, ?_⟩  intro i hi  have : i ≤ n := by omega  have : i * k ≤ n * k := Nat.mul_le_mul_right k this  omegalemma circulant_mixed_graph_cycle_g_exists_arith_odd    (z n : ℕ) (hz : 1 ≤ z) (hn : 2 ≤ n) (he : ¬ Even z) :    let N := (z + 1) * n    let m := N / 2    let h := (z + 1) / 2    1 ≤ h ∧    N = 2 * m ∧    m = n * h ∧    N - n * h = m ∧    0 < m ∧    ∀ i < n + 1, i * h < N := by  intro N m h  dsimp [N, m, h]  obtain ⟨k, rfl⟩ : ∃ k, z = 2 * k + 1 := Nat.not_even_iff_odd.mp he  have h_div : (2 * k + 1 + 1) / 2 = k + 1 := by omega  have hN_eq : (2 * k + 1 + 1) * n = 2 * (n * (k + 1)) := by ring  have hm_eq : ((2 * k + 1 + 1) * n) / 2 = n * (k + 1) := by    rw [hN_eq, Nat.mul_div_right _ (by omega)]  have h1 : 1 ≤ (2 * k + 1 + 1) / 2 := by rw [h_div]; omega  have h2 : (2 * k + 1 + 1) * n = 2 * (((2 * k + 1 + 1) * n) / 2) := by rw [hm_eq]; ring  have h3 : ((2 * k + 1 + 1) * n) / 2 = n * ((2 * k + 1 + 1) / 2) := by rw [hm_eq, h_div]  have h4 : (2 * k + 1 + 1) * n - n * ((2 * k + 1 + 1) / 2) = ((2 * k + 1 + 1) * n) / 2 := by    rw [hm_eq, h_div]; omega  have h5 : 0 < ((2 * k + 1 + 1) * n) / 2 := by rw [hm_eq]; nlinarith  refine ⟨h1, h2, h3, h4, h5, ?_⟩  intro i hi  rw [h_div]  have : i ≤ n := by omega  have : i * (k + 1) ≤ n * (k + 1) := Nat.mul_le_mul_right (k + 1) this  have : n * (k + 1) < 2 * (n * (k + 1)) := by nlinarith  linarith/-- The circulant mixed graph M(z, g) contains a mixed cycle of length g. -/theorem circulant_mixed_graph_cycle_g_exists (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) :    let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1)    let m := N / 2    let E := SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m    let A : Fin N → Fin N → Prop := fun x y =>      (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨      (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2)    mixed_graph_has_cycle E A g := by  obtain ⟨n, rfl⟩ : ∃ n, g = n + 1 := ⟨g - 1, by omega⟩  have hn : 2 ≤ n := by omega  intro N m E A  have hg_le : 3 ≤ n + 1 := hg  refine ⟨hg_le, ?_⟩  have h_bound : ∀ i < n + 1, i * ((z + 1) / 2) < N := by    intro i hi    dsimp [N]    split_ifs with he    · exact (circulant_mixed_graph_cycle_g_exists_arith_even z n hz he).2.2.2.2.2.2 i hi    · exact (circulant_mixed_graph_cycle_g_exists_arith_odd z n hz hn he).2.2.2.2.2 i hi  let x : Fin (n + 1) → Fin N := fun i => ⟨i.val * ((z + 1) / 2), h_bound i.val i.isLt⟩  refine ⟨x, ?_, ?_⟩  · -- Injective    intro i j hij    simp only [x, Fin.mk.injEq] at hij    have hpos : 0 < (z + 1) / 2 := by omega    exact Fin.ext (Nat.eq_of_mul_eq_mul_right hpos hij)  · -- Cycle condition    intro i    have hx_val : ∀ j : Fin (n + 1), (x j).val = j.val * ((z + 1) / 2) := fun _ => rfl    by_cases hi : i = Fin.last n    · -- hi : i = Fin.last n      have hrot : finRotate (n + 1) i = 0 := by        rw [hi, finRotate_last]      have hi_val : i.val = n := by        rw [hi]        rfl      have hrot_val : (x (finRotate (n + 1) i)).val = 0 := by        rw [hrot, hx_val, Fin.val_zero, Nat.zero_mul]      have hx_i_pos : 0 < (x i).val := by        rw [hx_val, hi_val]        have : 0 < (z + 1) / 2 := by omega        nlinarith      have hsub : (x (finRotate (n + 1) i) - x i).val = N - n * ((z + 1) / 2) := by        have := circulant_mixed_graph_cycle_g_exists_sub_zero_eq (x i)          (x (finRotate (n + 1) i)) hrot_val hx_i_pos        rw [this, hx_val, hi_val]      by_cases he : Even z      · -- Even z        obtain ⟨he1, he2, he3, he4, he5, he6, he7⟩ :=          circulant_mixed_graph_cycle_g_exists_arith_even z n hz he        have hN_eq : N = z * n + 2 := by dsimp [N]; rw [if_pos he]        have hm_eq : m = (z * n + 2) / 2 := by dsimp [m]; rw [hN_eq]        have hsub' : (x (finRotate (n + 1) i) - x i).val = m + 1 := by          rw [hsub, hN_eq, he5, ← hm_eq]        right        right        rw [hsub', hm_eq]        exact ⟨le_rfl, he6⟩      · -- Odd z        obtain ⟨ho1, ho2, ho3, ho4, ho5, ho6⟩ :=          circulant_mixed_graph_cycle_g_exists_arith_odd z n hz hn he        have hN_eq : N = (z + 1) * n := by dsimp [N]; rw [if_neg he]        have hm_eq : m = ((z + 1) * n) / 2 := by dsimp [m]; rw [hN_eq]        have hsub' : (x (finRotate (n + 1) i) - x i).val = m := by          rw [hsub, hN_eq, ho4, ← hm_eq]        left        rw [SimpleGraph.fromRel_adj]        refine ⟨?_, Or.inl hsub'⟩        intro h_eq        have : (x i).val = (x (finRotate (n + 1) i)).val := congrArg Fin.val h_eq        rw [hx_val, hi_val, hrot_val] at this        have : 0 < n * ((z + 1) / 2) := by          have : 0 < n := by omega          have : 0 < (z + 1) / 2 := by omega          positivity        omega    · -- hi : i ≠ Fin.last n      have hrot : (finRotate (n + 1) i).val = i.val + 1 := coe_finRotate_of_ne_last hi      have hsub : (x (finRotate (n + 1) i) - x i).val = (z + 1) / 2 := by        have hy_eq : (x (finRotate (n + 1) i)).val = (x i).val + (z + 1) / 2 := by          rw [hx_val, hx_val, hrot]          ring        have hN_lt : (x i).val + (z + 1) / 2 < N := by          rw [← hy_eq]          exact (x (finRotate (n + 1) i)).isLt        exact circulant_mixed_graph_cycle_g_exists_sub_eq_of_add_eq (x i)          (x (finRotate (n + 1) i)) ((z + 1) / 2) hy_eq hN_lt      right      left      rw [hsub]      have : 1 ≤ (z + 1) / 2 := by omega      exact ⟨this, le_rfl⟩
See it in the graphDiscuss this resultChallenge it