circulant_mixed_graph_cycle_g_exists
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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.
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.
uses
Fin.sub_def,Nat.add_mod_left,Nat.mod_eq_of_ltlemma 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]
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.
uses
Fin.sub_def,Nat.mod_eq_of_ltlemma 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
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.
uses
Nat.mul_div_right,Nat.mul_le_mul_rightlemma 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
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.
uses
Nat.not_even_iff_odd.mp,Nat.mul_div_right,Nat.mul_le_mul_rightlemma 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
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.
/-- 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, ?_⟩
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.
uses
circulant_mixed_graph_cycle_g_exists_arith_even,circulant_mixed_graph_cycle_g_exists_arith_oddhave 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, ?_, ?_⟩
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.
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)
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).
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]
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.
uses
circulant_mixed_graph_cycle_g_exists_arith_even,if_pos,le_rflby_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⟩
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.
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
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.
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.
- The helper lemmas circulant_mixed_graph_cycle_g_exists_sub_eq_of_add_eq and circulant_mixed_graph_cycle_g_exists_sub_zero_eq handle Lean's modular subtraction in Fin N, which is defined as (N - x + y) % N, reducing it to standard integer arithmetic when no wraparound occurs or when subtracting from zero.
- Throughout the proofs, linear integer inequalities, polynomial expansions, and divisibility identities are closed by automation tactics (omega, ring, linarith, nlinarith, positivity).
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.
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⟩