AFTD Auto-Formalizing Theoretical Domains

circulant_mixed_graph_valid_and_regular

theoremverified

For 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 m+1..m+⌊z/2⌋ is valid and (1, z)-regular.

Statement

theorem circulant_mixed_graph_valid_and_regular (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_is_valid E A ∧ mixed_graph_is_regular E A 1 z
Source
step towards mixed_cage_order_one_le
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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.
  • 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

The theorem verifies that the circulant mixed graph on $N = N(z, g)$ vertices constructed with antipodal edges of jump $m = N/2$ and directed arc jumps in $1..\lceil z/2 \rceil$ and $m+1..m+\lfloor z/2 \rfloor$ is valid and $(1, z)$-regular. The proof first establishes a general theorem for any $N = 2m$ with $m > z$: validity holds because the arc jump set $T$ avoids 0, is disjoint from its additive inverse (using $(y-x).val + (x-y).val = N$), and avoids the antipodal jump $m$; regularity holds because every vertex has edge degree $|\{m\}| = 1$ and in/out-degree $|T| = \lceil z/2 \rceil + \lfloor z/2 \rfloor = z$ by translation invariance in `Fin N`. Finally, for the specific formula $N(z, g)$ with $z \ge 1$ and $g \ge 3$, a case analysis on the parity of $z$ confirms that $N$ is even and $N \ge 2(z+1)$, which guarantees $z < N/2 = m$.

  1. Modular subtraction followed by addition satisfies $(a + (n - a + z) \bmod n) \bmod n = z$ for $a, z < n$.

    We split into cases on whether $z < a$ or $z \ge a$. If $z < a$, the inner sum $n - a + z$ is strictly less than $n$, so the modulo operation is the identity; adding $a$ yields $z + n$, which reduces to $z$ modulo $n$. If $z \ge a$, we rewrite $n - a + z$ as $(z - a) + n$, which reduces modulo $n$ to $z - a < n$, and adding $a$ produces $z$.

    lines 1–10

    uses Nat.lt_or_ge, Nat.mod_eq_of_lt, Nat.add_mod_right

    theorem circulant_mixed_graph_valid_and_regular_nat_add_mod_sub (n a z : ℕ) (ha : a < n) (hz : z < n) :
        (a + (n - a + z) % n) % n = z := by
      rcases Nat.lt_or_ge z a with h | h
      · have hmod : (n - a + z) % n = n - a + z := Nat.mod_eq_of_lt (by omega)
        rw [hmod]; have : a + (n - a + z) = z + n := by omega
        rw [this, Nat.add_mod_right, Nat.mod_eq_of_lt hz]
      · have h1 : n - a + z = (z - a) + n := by omega
        rw [h1, Nat.add_mod_right]; have h2 : z - a < n := by omega
        rw [Nat.mod_eq_of_lt h2]; have : a + (z - a) = z := by omega
        rw [this, Nat.mod_eq_of_lt hz]
  2. Modular addition followed by subtraction satisfies $(n - a + (a + d) \bmod n) \bmod n = d$ for $a, d < n$.

    We split on whether $a + d < n$ or $a + d \ge n$. In the first case, $(a + d) \bmod n = a + d$, and $n - a + (a + d) = n + d \equiv d \pmod n$. In the second case, $(a + d) \bmod n = a + d - n$, and $n - a + (a + d - n) = d < n$, so the outer modulo leaves $d$.

    lines 11–18

    uses Nat.lt_or_ge, Nat.mod_eq_of_lt, Nat.add_mod_left, Nat.mod_eq_sub_mod

    theorem circulant_mixed_graph_valid_and_regular_nat_sub_add_mod (n a d : ℕ) (ha : a < n) (hd : d < n) :
        (n - a + (a + d) % n) % n = d := by
      rcases Nat.lt_or_ge (a + d) n with h | h
      · rw [Nat.mod_eq_of_lt h]; have : n - a + (a + d) = n + d := by omega
        rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt hd]
      · have h2 : (a + d) % n = a + d - n := by rw [Nat.mod_eq_sub_mod h, Nat.mod_eq_of_lt (by omega)]
        rw [h2]; have : n - a + (a + d - n) = d := by omega
        rw [this, Nat.mod_eq_of_lt hd]
  3. The cancellation identities $x + (y - x) = y$, $(x + d) - x = d$, $(x - d) + d = x$, and $x - (x - d) = d$ hold in `Fin n`.

    By extensionality on `Fin n`, the equality of elements reduces to the equality of their values modulo $n$, which are given by the previous two modular arithmetic lemmas. The remaining two identities follow by commutativity of addition and rewriting $x$ as $(x - d) + d$.

    lines 19–27

    uses Fin.val_add, Fin.val_sub, circulant_mixed_graph_valid_and_regular_nat_add_mod_sub, circulant_mixed_graph_valid_and_regular_nat_sub_add_mod, add_comm, circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel, circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel, circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right

    theorem circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel {n : ℕ} (x y : Fin n) : x + (y - x) = y := by
      ext; rw [Fin.val_add, Fin.val_sub]; exact circulant_mixed_graph_valid_and_regular_nat_add_mod_sub n x.val y.val x.isLt y.isLt
    theorem circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right {n : ℕ} (x d : Fin n) : (x + d) - x = d := by
      ext; rw [Fin.val_sub, Fin.val_add]; exact circulant_mixed_graph_valid_and_regular_nat_sub_add_mod n x.val d.val x.isLt d.isLt
    theorem circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel {n : ℕ} (x d : Fin n) : (x - d) + d = x := by
      rw [add_comm]; exact circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel d x
    theorem circulant_mixed_graph_valid_and_regular_fin_sub_sub_self {n : ℕ} (x d : Fin n) : x - (x - d) = d := by
      have hx : x = (x - d) + d := (circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel x d).symm
      nth_rewrite 1 [hx]; exact circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right (x - d) d
  4. For distinct elements $x \ne y$ in `Fin n`, the values of their opposite differences sum to the modulus: $(y - x).val + (x - y).val = n$.

    Using the integer representation of difference in `Fin n`, $(y - x).val$ equals $y.val - x.val + (\text{if } x \le y \text{ then } 0 \text{ else } n)$. Because $x \ne y$, exactly one of $x \le y$ or $y \le x$ holds. In either case, the terms $x.val$ and $y.val$ cancel out algebraically, leaving $n$, which is then cast back to natural numbers.

    lines 28–40

    uses Fin.intCast_val_sub_eq_sub_add_ite, le_antisymm, if_pos, if_neg, le_of_lt, lt_of_not_ge

    theorem circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub {n : ℕ} (x y : Fin n) (hne : x ≠ y) :
        (y - x).val + (x - y).val = n := by
      have h1 := Fin.intCast_val_sub_eq_sub_add_ite y x
      have h2 := Fin.intCast_val_sub_eq_sub_add_ite x y
      have key : ((y - x).val : ℤ) + ((x - y).val : ℤ) = n := by
        rw [h1, h2]
        by_cases hxy : x ≤ y
        · have hyx : ¬ (y ≤ x) := by intro h; exact hne (le_antisymm hxy h)
          rw [if_pos hxy, if_neg hyx]; ring
        · have hyx : y ≤ x := le_of_lt (lt_of_not_ge hxy)
          rw [if_neg hxy, if_pos hyx]; ring
      have key' : ((y - x).val + (x - y).val : ℤ) = n := by exact key
      exact_mod_cast key'
  5. The cardinality of a coordinate interval $\{d : \text{Fin } N \mid a \le d.val \le b\}$ with $b < N$ is $b + 1 - a$.

    The valuation map $d \mapsto d.val$ defines a bijection between this subset of `Fin N` and the integer interval $[a, b] \subseteq \mathbb{N}$, established using `Set.ncard_congr`. The cardinality then matches the standard formula $b + 1 - a$ for the size of an interval of natural numbers.

    lines 41–49

    uses Set.ncard_congr, Fin.ext, Set.ncard_eq_toFinset_card', Set.toFinset_Icc, Nat.card_Icc

    theorem circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc (N a b : ℕ) (hb : b < N) :
        ({d : Fin N | a ≤ d.val ∧ d.val ≤ b} : Set (Fin N)).ncard = b + 1 - a := by
      have hmain : ({d : Fin N | a ≤ d.val ∧ d.val ≤ b} : Set (Fin N)).ncard = (Set.Icc a b : Set ℕ).ncard := by
        apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ {d : Fin N | a ≤ d.val ∧ d.val ≤ b}) => d.val)
        · intro d hd; simp only [Set.mem_setOf_eq, Set.mem_Icc] at hd ⊢; exact hd
        · intro d1 d2 hd1 hd2 heq; exact Fin.ext heq
        · intro k hk; simp only [Set.mem_Icc] at hk
          refine ⟨⟨k, by omega⟩, ?_, rfl⟩; simp only [Set.mem_setOf_eq]; exact hk
      rw [hmain, Set.ncard_eq_toFinset_card', Set.toFinset_Icc, Nat.card_Icc]
  6. Left and right translations in `Fin N` preserve set cardinality: $|\{y \mid y - x \in S\}| = |S|$ and $|\{y \mid x - y \in S\}| = |S|$.

    For right translation, $d \mapsto x + d$ provides a bijection between $S$ and $\{y \mid y - x \in S\}$ with inverse $y \mapsto y - x$, using the cancellation identities. For left reflection/translation, $d \mapsto x - d$ is an involution providing a bijection between $S$ and $\{y \mid x - y \in S\}$.

    lines 50–69

    uses Set.ncard_congr, circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right, circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel, circulant_mixed_graph_valid_and_regular_fin_sub_sub_self

    theorem circulant_mixed_graph_valid_and_regular_ncard_translate_right (N : ℕ) (x : Fin N) (S : Set (Fin N)) :
        ({y : Fin N | (y - x) ∈ S} : Set (Fin N)).ncard = S.ncard := by
      symm
      apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ S) => x + d)
      · intro d hd; show (x + d - x) ∈ S; rw [circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right]; exact hd
      · intro a b ha hb heq
        calc a = (x + a) - x := (circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right x a).symm
          _ = (x + b) - x := by rw [heq]
          _ = b := circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right x b
      · intro y hy; exact ⟨y - x, hy, circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel x y⟩
    theorem circulant_mixed_graph_valid_and_regular_ncard_sub_left (N : ℕ) (x : Fin N) (S : Set (Fin N)) :
        ({y : Fin N | (x - y) ∈ S} : Set (Fin N)).ncard = S.ncard := by
      symm
      apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ S) => x - d)
      · intro d hd; show (x - (x - d)) ∈ S; rw [circulant_mixed_graph_valid_and_regular_fin_sub_sub_self]; exact hd
      · intro a b ha hb heq
        calc a = x - (x - a) := (circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x a).symm
          _ = x - (x - b) := by rw [heq]
          _ = b := circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x b
      · intro y hy; exact ⟨x - y, hy, circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x y⟩
  7. In the general circulant graph with $N = 2m$ and $z < m$, the arc jump set $T = [1, c_1] \cup [m+1, m+c_2]$ has cardinality $z$.

    Setting $c_1 = \lfloor (z+1)/2 \rfloor$ and $c_2 = \lfloor z/2 \rfloor$, we have $c_1 + c_2 = z$. The two intervals $[1, c_1]$ and $[m+1, m+c_2]$ are disjoint because $c_1 \le z < m < m+1$, and their upper bound satisfies $m + c_2 \le m + z < 2m = N$. Since $T$ is the disjoint union of these two intervals, its cardinality is $c_1 + c_2 = z$.

    lines 71–107

    uses Fin.val_sub, Nat.mod_self, Set.disjoint_left, Set.ncard_union_eq, Set.toFinite, circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc

    theorem circulant_mixed_graph_valid_and_regular_general (N m z : ℕ) (hz : 1 ≤ z) (hm : z < m) (hNm : N = 2 * m) :
        mixed_graph_is_valid (SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m)
          (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_is_regular (SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m)
          (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨
            (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2)) 1 z := by
      set c1 := (z + 1) / 2 with hc1
      set c2 := z / 2 with hc2
      set E : SimpleGraph (Fin N) := SimpleGraph.fromRel (fun (x y : Fin N) => (y - x).val = m) with hE
      set T : Set (Fin N) := {d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1 ∨ m + 1 ≤ d.val ∧ d.val ≤ m + c2} with hT
      set A : Fin N → Fin N → Prop :=
        (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ c1) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + c2)) with hA
      have hc12 : c1 + c2 = z := by omega
      have hmpos : 0 < m := by omega
      have hmN : m < N := by omega
      have hc1z : c1 ≤ z := by omega
      have hc2z : c2 ≤ z := by omega
      have hmc2N : m + c2 < N := by omega
      have hval_self : ∀ w : Fin N, (w - w).val = 0 := by
        intro w
        rw [Fin.val_sub]
        have h : N - w.val + w.val = N := by omega
        rw [h, Nat.mod_self]
      have hTncard : T.ncard = z := by
        have hT_eq : T = {d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} ∪ {d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} := by
          rw [hT]; ext d; simp only [Set.mem_setOf_eq, Set.mem_union]
        have hdisj : Disjoint ({d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} : Set (Fin N))
            {d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} := by
          rw [Set.disjoint_left]; intro d h1 h2
          simp only [Set.mem_setOf_eq] at h1 h2; omega
        rw [hT_eq, Set.ncard_union_eq hdisj (Set.toFinite _) (Set.toFinite _)]
        have hn1 : ({d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} : Set (Fin N)).ncard = c1 := by
          rw [circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N 1 c1 (by omega)]; omega
        have hn2 : ({d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} : Set (Fin N)).ncard = c2 := by
          rw [circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N (m + 1) (m + c2) (by omega)]; omega
        rw [hn1, hn2, hc12]
  8. The circulant mixed graph is valid: it has no self-loops, arcs are asymmetric, and edges and arcs are disjoint.

    Vertices have no self-loops because $(x - x).val = 0$, but all jumps in $T$ are at least 1. For asymmetry, if $y - x \in T$, then $x \ne y$, so $(x - y).val = N - (y - x).val = 2m - (y - x).val$. If $(y - x).val \in [1, c_1]$, then $(x - y).val \in [2m - c_1, 2m - 1]$, which is strictly greater than $m + c_2$ (since $c_1 + c_2 = z < m$), so $x - y \notin T$; the case $(y - x).val \in [m+1, m+c_2]$ is symmetric. Finally, an undirected edge requires $(y - x).val = m$, but $m$ lies strictly between $c_1 \le z < m$ and $m + 1$, so it belongs to neither interval of $T$.

    lines 108–134

    uses circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub, SimpleGraph.fromRel_adj

      constructor
      · refine ⟨?_, ?_, ?_⟩
        · intro x
          simp only [hA]
          have h0 := hval_self x
          omega
        · intro x y hAxy
          simp only [hA] at hAxy ⊢
          rcases hAxy with ⟨hp1, hp2⟩ | ⟨hp1, hp2⟩
          · have hxy : x ≠ y := by
              intro h; subst h; rw [hval_self x] at hp1; omega
            have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hxy
            have hq : (x - y).val = N - (y - x).val := by omega
            rw [hq]; omega
          · have hxy : x ≠ y := by
              intro h; subst h; rw [hval_self x] at hp1; omega
            have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hxy
            have hq : (x - y).val = N - (y - x).val := by omega
            rw [hq]; omega
        · intro x y hExy
          rw [hE, SimpleGraph.fromRel_adj] at hExy
          simp only [hA]
          rcases hExy with ⟨hne, hp | hp⟩
          · rw [hp]; omega
          · have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hne
            have hq : (y - x).val = m := by omega
            rw [hq]; omega
  9. The circulant mixed graph is $(1, z)$-regular: each vertex has undirected degree 1, out-degree $z$, and in-degree $z$.

    An edge incident to $x$ is equivalent to $(y - x).val = m$ because $N = 2m$ implies $(x - y).val = m$ whenever $(y - x).val = m$. The set of neighbors $\{y \mid (y - x).val = m\}$ is a translation of the singleton $\{m\}$, having cardinality $m + 1 - m = 1$. The out-neighborhood $\{y \mid y - x \in T\}$ and in-neighborhood $\{y \mid x - y \in T\}$ are right and left translates of $T$, both having cardinality $|T| = z$.

    lines 135–160

    uses SimpleGraph.fromRel_adj, circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub, Or.inl, circulant_mixed_graph_valid_and_regular_ncard_translate_right, circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc, circulant_mixed_graph_valid_and_regular_ncard_sub_left

      · intro x
        have hEadj : ∀ y : Fin N, E.Adj x y ↔ (y - x).val = m := by
          intro y
          rw [hE, SimpleGraph.fromRel_adj]
          constructor
          · rintro ⟨hne, hp | hp⟩
            · exact hp
            · have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hne; omega
          · intro hp
            refine ⟨?_, Or.inl hp⟩
            intro hxy; rw [hxy] at hp
            have hv := hval_self y; omega
        refine ⟨?_, ?_, ?_⟩
        · have hset : {y : Fin N | E.Adj x y} = {y : Fin N | (y - x) ∈ ({d : Fin N | d.val = m} : Set (Fin N))} := by
            ext y; simp only [Set.mem_setOf_eq]; exact hEadj y
          rw [hset, circulant_mixed_graph_valid_and_regular_ncard_translate_right N x {d : Fin N | d.val = m}]
          have he : ({d : Fin N | d.val = m} : Set (Fin N)) = {d : Fin N | m ≤ d.val ∧ d.val ≤ m} := by
            ext d; simp only [Set.mem_setOf_eq]; omega
          rw [he, circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N m m hmN]; omega
        · have hset : {y : Fin N | A x y} = {y : Fin N | (y - x) ∈ T} := by
            ext y; simp only [hA, hT, Set.mem_setOf_eq]
          rw [hset, circulant_mixed_graph_valid_and_regular_ncard_translate_right N x T]; exact hTncard
        · have hset : {y : Fin N | A y x} = {y : Fin N | (x - y) ∈ T} := by
            ext y; simp only [hA, hT, Set.mem_setOf_eq]
          rw [hset, circulant_mixed_graph_valid_and_regular_ncard_sub_left N x T]; exact hTncard
    
  10. For $z \ge 1$ and $g \ge 3$, the vertex count $N(z, g)$ is even and satisfies $N \ge 2(z+1)$, which implies $z < N/2$ and $N = 2(N/2)$.

    Since $g \ge 3$, $g - 1 \ge 2$. If $z$ is even, $N = z(g-1) + 2$ is the sum of an even product and 2, hence even, and $N \ge 2z + 2 = 2(z+1)$. If $z$ is odd, $z+1$ is even, so $N = (z+1)(g-1)$ is even, and $N \ge 2(z+1)$. In both cases, $N = 2(N/2)$, and dividing $2(z+1) \le N$ by 2 yields $z < z+1 \le N/2$.

    lines 162–194

    uses if_true, Even.add, even_two, if_false, Nat.mul_le_mul_left, Nat.div_two_mul_two_of_even, Nat.div_le_div_right, Nat.mul_div_right

    theorem circulant_mixed_graph_valid_and_regular (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_is_valid E A ∧ mixed_graph_is_regular E A 1 z := by
      dsimp only
      set N := (if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1)) with hN
      have hg1 : 2 ≤ g - 1 := by omega
      have hN_even : Even N := by
        by_cases hze : Even z
        · rw [hN]; simp only [hze, if_true]
          exact Even.add (hze.mul_right (g - 1)) even_two
        · rw [hN]; simp only [hze, if_false]
          have hodd : Odd z := Nat.not_even_iff_odd.mp hze
          exact (hodd.add_one).mul_right (g - 1)
      have hN_ge : 2 * (z + 1) ≤ N := by
        by_cases hze : Even z
        · rw [hN]; simp only [hze, if_true]
          have h2 : z * 2 ≤ z * (g - 1) := Nat.mul_le_mul_left z hg1
          omega
        · rw [hN]; simp only [hze, if_false]
          have h2 : (z + 1) * 2 ≤ (z + 1) * (g - 1) := Nat.mul_le_mul_left (z + 1) hg1
          omega
      have hNm : N = 2 * (N / 2) := by
        have h := Nat.div_two_mul_two_of_even hN_even
        omega
      have hm : z < N / 2 := by
        have h1 : (2 * (z + 1)) / 2 ≤ N / 2 := Nat.div_le_div_right hN_ge
        rw [Nat.mul_div_right (z + 1) (by norm_num : 0 < 2)] at h1
        omega
  11. The circulant mixed graph on $N(z, g)$ vertices is valid and $(1, z)$-regular.

    We invoke the general circulant graph theorem with $m = N/2$, using the established bounds $1 \le z$, $z < m$, and $N = 2m$.

    line 195

    uses circulant_mixed_graph_valid_and_regular_general

      exact circulant_mixed_graph_valid_and_regular_general N (N / 2) z hz hm hNm
Nat.lt_or_ge
For any two natural numbers $n$ and $m$, either $n < m$ or $n \ge m$.
Nat.mod_eq_of_lt
If $a < b$, then $a \bmod b = a$.
Nat.add_mod_right
For any $x$ and $z$, $(x + z) \bmod z = x \bmod z$.
Nat.add_mod_left
For any $x$ and $z$, $(x + z) \bmod x = z \bmod x$.
Nat.mod_eq_sub_mod
If $a \ge b$, then $a \bmod b = (a - b) \bmod b$.
Fin.val_add
In `Fin n`, the underlying value of $a + b$ is $(a.val + b.val) \bmod n$.
Fin.val_sub
In `Fin n`, the underlying value of $a - b$ is $(n - b.val + a.val) \bmod n$.
circulant_mixed_graph_valid_and_regular_nat_add_mod_sub
For $a, z < n$, $(a + (n - a + z) \bmod n) \bmod n = z$.
circulant_mixed_graph_valid_and_regular_nat_sub_add_mod
For $a, d < n$, $(n - a + (a + d) \bmod n) \bmod n = d$.
add_comm
Addition is commutative: $a + b = b + a$.
circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel
In `Fin n`, $x + (y - x) = y$.
circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel
In `Fin n`, $(x - d) + d = x$.
circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right
In `Fin n`, $(x + d) - x = d$.
circulant_mixed_graph_valid_and_regular_fin_sub_sub_self
In `Fin n`, $x - (x - d) = d$.
Fin.intCast_val_sub_eq_sub_add_ite
In $\mathbb{Z}$, the difference $(a - b).val$ in `Fin n` is $a.val - b.val + (\text{if } b \le a \text{ then } 0 \text{ else } n)$.
le_antisymm
If $a \le b$ and $b \le a$, then $a = b$.
if_pos
If $c$ holds, then $(\text{if } c \text{ then } t \text{ else } e) = t$.
if_neg
If $c$ does not hold, then $(\text{if } c \text{ then } t \text{ else } e) = e$.
le_of_lt
If $a < b$, then $a \le b$.
lt_of_not_ge
If not $b \le a$, then $a < b$.
circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub
For distinct elements $x \ne y$ in `Fin n`, $(y - x).val + (x - y).val = n$.
Set.ncard_congr
If there is a bijection between subsets $s$ and $t$, then their cardinalities are equal.
Fin.ext
Two elements of `Fin n` are equal if and only if their underlying values are equal.
Set.ncard_eq_toFinset_card'
The cardinality of a finite set equals the cardinality of its coerced finset.
Set.toFinset_Icc
The finset of an interval of integers is the interval Finset.Icc.
Nat.card_Icc
The number of integers in the closed interval $[a, b]$ is $b + 1 - a$.
circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc
For $b < N$, the number of elements in `Fin N` with values in $[a, b]$ is $b + 1 - a$.
circulant_mixed_graph_valid_and_regular_ncard_translate_right
Right translation preserves subset cardinality in `Fin N`: $|\{y \mid y - x \in S\}| = |S|$.
circulant_mixed_graph_valid_and_regular_ncard_sub_left
Left reflection and translation preserves subset cardinality in `Fin N`: $|\{y \mid x - y \in S\}| = |S|$.
Nat.mod_self
For any $n$, $n \bmod n = 0$.
Set.disjoint_left
Two sets are disjoint if no element of the first belongs to the second.
Set.ncard_union_eq
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Set.toFinite
Any set in a finite type is finite.
SimpleGraph.fromRel_adj
Two vertices are adjacent in a graph induced by a relation iff they are distinct and the relation holds in at least one direction.
Or.inl
From $a$, infer $a \lor b$.
if_true
Evaluating an `if-then-else` on `True` yields the `then` branch.
Even.add
The sum of two even numbers is even.
even_two
The number 2 is even.
if_false
Evaluating an `if-then-else` on `False` yields the `else` branch.
Nat.mul_le_mul_left
If $n \le m$, then $k \cdot n \le k \cdot m$.
Nat.div_two_mul_two_of_even
If $n$ is even, then $(n / 2) \cdot 2 = n$.
Nat.div_le_div_right
If $a \le b$, then $a / c \le b / c$.
Nat.mul_div_right
For $m > 0$, $(m \cdot n) / m = n$.
circulant_mixed_graph_valid_and_regular_general
The circulant mixed graph with antipodal jump $m$ and arc jumps in $1..\lceil z/2 \rceil$ and $m+1..m+\lfloor z/2 \rfloor$ is valid and $(1, z)$-regular whenever $1 \le z < m$ and $N = 2m$.

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 circulant_mixed_graph_valid_and_regular_nat_add_mod_sub (n a z : ℕ) (ha : a < n) (hz : z < n) :    (a + (n - a + z) % n) % n = z := by  rcases Nat.lt_or_ge z a with h | h  · have hmod : (n - a + z) % n = n - a + z := Nat.mod_eq_of_lt (by omega)    rw [hmod]; have : a + (n - a + z) = z + n := by omega    rw [this, Nat.add_mod_right, Nat.mod_eq_of_lt hz]  · have h1 : n - a + z = (z - a) + n := by omega    rw [h1, Nat.add_mod_right]; have h2 : z - a < n := by omega    rw [Nat.mod_eq_of_lt h2]; have : a + (z - a) = z := by omega    rw [this, Nat.mod_eq_of_lt hz]theorem circulant_mixed_graph_valid_and_regular_nat_sub_add_mod (n a d : ℕ) (ha : a < n) (hd : d < n) :    (n - a + (a + d) % n) % n = d := by  rcases Nat.lt_or_ge (a + d) n with h | h  · rw [Nat.mod_eq_of_lt h]; have : n - a + (a + d) = n + d := by omega    rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt hd]  · have h2 : (a + d) % n = a + d - n := by rw [Nat.mod_eq_sub_mod h, Nat.mod_eq_of_lt (by omega)]    rw [h2]; have : n - a + (a + d - n) = d := by omega    rw [this, Nat.mod_eq_of_lt hd]theorem circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel {n : ℕ} (x y : Fin n) : x + (y - x) = y := by  ext; rw [Fin.val_add, Fin.val_sub]; exact circulant_mixed_graph_valid_and_regular_nat_add_mod_sub n x.val y.val x.isLt y.isLttheorem circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right {n : ℕ} (x d : Fin n) : (x + d) - x = d := by  ext; rw [Fin.val_sub, Fin.val_add]; exact circulant_mixed_graph_valid_and_regular_nat_sub_add_mod n x.val d.val x.isLt d.isLttheorem circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel {n : ℕ} (x d : Fin n) : (x - d) + d = x := by  rw [add_comm]; exact circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel d xtheorem circulant_mixed_graph_valid_and_regular_fin_sub_sub_self {n : ℕ} (x d : Fin n) : x - (x - d) = d := by  have hx : x = (x - d) + d := (circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel x d).symm  nth_rewrite 1 [hx]; exact circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right (x - d) dtheorem circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub {n : ℕ} (x y : Fin n) (hne : x ≠ y) :    (y - x).val + (x - y).val = n := by  have h1 := Fin.intCast_val_sub_eq_sub_add_ite y x  have h2 := Fin.intCast_val_sub_eq_sub_add_ite x y  have key : ((y - x).val : ℤ) + ((x - y).val : ℤ) = n := by    rw [h1, h2]    by_cases hxy : x ≤ y    · have hyx : ¬ (y ≤ x) := by intro h; exact hne (le_antisymm hxy h)      rw [if_pos hxy, if_neg hyx]; ring    · have hyx : y ≤ x := le_of_lt (lt_of_not_ge hxy)      rw [if_neg hxy, if_pos hyx]; ring  have key' : ((y - x).val + (x - y).val : ℤ) = n := by exact key  exact_mod_cast key'theorem circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc (N a b : ℕ) (hb : b < N) :    ({d : Fin N | a ≤ d.val ∧ d.val ≤ b} : Set (Fin N)).ncard = b + 1 - a := by  have hmain : ({d : Fin N | a ≤ d.val ∧ d.val ≤ b} : Set (Fin N)).ncard = (Set.Icc a b : Set ℕ).ncard := by    apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ {d : Fin N | a ≤ d.val ∧ d.val ≤ b}) => d.val)    · intro d hd; simp only [Set.mem_setOf_eq, Set.mem_Icc] at hd ⊢; exact hd    · intro d1 d2 hd1 hd2 heq; exact Fin.ext heq    · intro k hk; simp only [Set.mem_Icc] at hk      refine ⟨⟨k, by omega⟩, ?_, rfl⟩; simp only [Set.mem_setOf_eq]; exact hk  rw [hmain, Set.ncard_eq_toFinset_card', Set.toFinset_Icc, Nat.card_Icc]theorem circulant_mixed_graph_valid_and_regular_ncard_translate_right (N : ℕ) (x : Fin N) (S : Set (Fin N)) :    ({y : Fin N | (y - x) ∈ S} : Set (Fin N)).ncard = S.ncard := by  symm  apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ S) => x + d)  · intro d hd; show (x + d - x) ∈ S; rw [circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right]; exact hd  · intro a b ha hb heq    calc a = (x + a) - x := (circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right x a).symm      _ = (x + b) - x := by rw [heq]      _ = b := circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right x b  · intro y hy; exact ⟨y - x, hy, circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel x y⟩theorem circulant_mixed_graph_valid_and_regular_ncard_sub_left (N : ℕ) (x : Fin N) (S : Set (Fin N)) :    ({y : Fin N | (x - y) ∈ S} : Set (Fin N)).ncard = S.ncard := by  symm  apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ S) => x - d)  · intro d hd; show (x - (x - d)) ∈ S; rw [circulant_mixed_graph_valid_and_regular_fin_sub_sub_self]; exact hd  · intro a b ha hb heq    calc a = x - (x - a) := (circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x a).symm      _ = x - (x - b) := by rw [heq]      _ = b := circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x b  · intro y hy; exact ⟨x - y, hy, circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x y⟩theorem circulant_mixed_graph_valid_and_regular_general (N m z : ℕ) (hz : 1 ≤ z) (hm : z < m) (hNm : N = 2 * m) :    mixed_graph_is_valid (SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m)      (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_is_regular (SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m)      (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨        (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2)) 1 z := by  set c1 := (z + 1) / 2 with hc1  set c2 := z / 2 with hc2  set E : SimpleGraph (Fin N) := SimpleGraph.fromRel (fun (x y : Fin N) => (y - x).val = m) with hE  set T : Set (Fin N) := {d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1 ∨ m + 1 ≤ d.val ∧ d.val ≤ m + c2} with hT  set A : Fin N → Fin N → Prop :=    (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ c1) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + c2)) with hA  have hc12 : c1 + c2 = z := by omega  have hmpos : 0 < m := by omega  have hmN : m < N := by omega  have hc1z : c1 ≤ z := by omega  have hc2z : c2 ≤ z := by omega  have hmc2N : m + c2 < N := by omega  have hval_self : ∀ w : Fin N, (w - w).val = 0 := by    intro w    rw [Fin.val_sub]    have h : N - w.val + w.val = N := by omega    rw [h, Nat.mod_self]  have hTncard : T.ncard = z := by    have hT_eq : T = {d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} ∪ {d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} := by      rw [hT]; ext d; simp only [Set.mem_setOf_eq, Set.mem_union]    have hdisj : Disjoint ({d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} : Set (Fin N))        {d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} := by      rw [Set.disjoint_left]; intro d h1 h2      simp only [Set.mem_setOf_eq] at h1 h2; omega    rw [hT_eq, Set.ncard_union_eq hdisj (Set.toFinite _) (Set.toFinite _)]    have hn1 : ({d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} : Set (Fin N)).ncard = c1 := by      rw [circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N 1 c1 (by omega)]; omega    have hn2 : ({d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} : Set (Fin N)).ncard = c2 := by      rw [circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N (m + 1) (m + c2) (by omega)]; omega    rw [hn1, hn2, hc12]  constructor  · refine ⟨?_, ?_, ?_⟩    · intro x      simp only [hA]      have h0 := hval_self x      omega    · intro x y hAxy      simp only [hA] at hAxy ⊢      rcases hAxy with ⟨hp1, hp2⟩ | ⟨hp1, hp2⟩      · have hxy : x ≠ y := by          intro h; subst h; rw [hval_self x] at hp1; omega        have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hxy        have hq : (x - y).val = N - (y - x).val := by omega        rw [hq]; omega      · have hxy : x ≠ y := by          intro h; subst h; rw [hval_self x] at hp1; omega        have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hxy        have hq : (x - y).val = N - (y - x).val := by omega        rw [hq]; omega    · intro x y hExy      rw [hE, SimpleGraph.fromRel_adj] at hExy      simp only [hA]      rcases hExy with ⟨hne, hp | hp⟩      · rw [hp]; omega      · have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hne        have hq : (y - x).val = m := by omega        rw [hq]; omega  · intro x    have hEadj : ∀ y : Fin N, E.Adj x y ↔ (y - x).val = m := by      intro y      rw [hE, SimpleGraph.fromRel_adj]      constructor      · rintro ⟨hne, hp | hp⟩        · exact hp        · have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hne; omega      · intro hp        refine ⟨?_, Or.inl hp⟩        intro hxy; rw [hxy] at hp        have hv := hval_self y; omega    refine ⟨?_, ?_, ?_⟩    · have hset : {y : Fin N | E.Adj x y} = {y : Fin N | (y - x) ∈ ({d : Fin N | d.val = m} : Set (Fin N))} := by        ext y; simp only [Set.mem_setOf_eq]; exact hEadj y      rw [hset, circulant_mixed_graph_valid_and_regular_ncard_translate_right N x {d : Fin N | d.val = m}]      have he : ({d : Fin N | d.val = m} : Set (Fin N)) = {d : Fin N | m ≤ d.val ∧ d.val ≤ m} := by        ext d; simp only [Set.mem_setOf_eq]; omega      rw [he, circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N m m hmN]; omega    · have hset : {y : Fin N | A x y} = {y : Fin N | (y - x) ∈ T} := by        ext y; simp only [hA, hT, Set.mem_setOf_eq]      rw [hset, circulant_mixed_graph_valid_and_regular_ncard_translate_right N x T]; exact hTncard    · have hset : {y : Fin N | A y x} = {y : Fin N | (x - y) ∈ T} := by        ext y; simp only [hA, hT, Set.mem_setOf_eq]      rw [hset, circulant_mixed_graph_valid_and_regular_ncard_sub_left N x T]; exact hTncard/-- The circulant mixed graph M(z, g) on N(z, g) vertices is valid (loopless, asymmetric arcs, disjoint edge and arc sets) and (1, z)-regular. -/theorem circulant_mixed_graph_valid_and_regular (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_is_valid E A ∧ mixed_graph_is_regular E A 1 z := by  dsimp only  set N := (if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1)) with hN  have hg1 : 2 ≤ g - 1 := by omega  have hN_even : Even N := by    by_cases hze : Even z    · rw [hN]; simp only [hze, if_true]      exact Even.add (hze.mul_right (g - 1)) even_two    · rw [hN]; simp only [hze, if_false]      have hodd : Odd z := Nat.not_even_iff_odd.mp hze      exact (hodd.add_one).mul_right (g - 1)  have hN_ge : 2 * (z + 1) ≤ N := by    by_cases hze : Even z    · rw [hN]; simp only [hze, if_true]      have h2 : z * 2 ≤ z * (g - 1) := Nat.mul_le_mul_left z hg1      omega    · rw [hN]; simp only [hze, if_false]      have h2 : (z + 1) * 2 ≤ (z + 1) * (g - 1) := Nat.mul_le_mul_left (z + 1) hg1      omega  have hNm : N = 2 * (N / 2) := by    have h := Nat.div_two_mul_two_of_even hN_even    omega  have hm : z < N / 2 := by    have h1 : (2 * (z + 1)) / 2 ≤ N / 2 := Nat.div_le_div_right hN_ge    rw [Nat.mul_div_right (z + 1) (by norm_num : 0 < 2)] at h1    omega  exact circulant_mixed_graph_valid_and_regular_general N (N / 2) z hz hm hNm
See it in the graphDiscuss this resultChallenge it