AFTD Auto-Formalizing Theoretical Domains

cyclic_four_block_witness

theoremverified

Step of cyclic_four_block_graph_exists_rich_neighbor_five_coloring: witness.

Statement

theorem cyclic_four_block_witness (m : ℕ) (e : (Fin (2*m+5) × Fin 6)) :
    cyclic_four_block_edge m e ≠ cyclic_four_block_edge m (cyclic_four_block_W m e) ∧
    cyclic_four_block_touch m e (cyclic_four_block_W m e) ∧ cyclic_four_block_good m (cyclic_four_block_W m e)
Source
decomposition of cyclic_four_block_graph_exists_rich_neighbor_five_coloring
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • cyclic_four_block_nextHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the next block index i+1, cyclically mod n=2m+5.
  • cyclic_four_block_prevHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the previous block index i-1, cyclically mod n=2m+5.
  • cyclic_four_block_srcHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the first endpoint (as a natural number) of the indexed edge (i,j)…
  • cyclic_four_block_dstHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the second endpoint (as a natural number) of the indexed edge (i,j).
  • cyclic_four_block_edgeHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the indexed edge (i,j) of cyclic_four_block_graph m as an unordered…
  • cyclic_four_block_touchHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: two indexed edges share an endpoint (comparison of src/dst values).
  • cyclic_four_block_goodHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the indexed edges whose four neighbouring edges receive four…
  • cyclic_four_block_WHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the chosen rich neighbour (a good adjacent edge) of each indexed…
Used by 1

The proof, explained

The theorem proves that for any edge e in the cyclic four-block graph, the candidate edge W(e) is distinct from e, shares a vertex with e, and satisfies the 'good' edge property. The proof decomposes e into a block index i and edge type j ∈ Fin 6, and performs an exhaustive case analysis on j. After expanding all graph-theoretic definitions and reducing edge equality to endpoint matching, internal edge cases are dispatched immediately by linear arithmetic, while boundary-crossing edges are resolved by splitting on the cycle wraparound conditions and solving each branch with linear arithmetic.

  1. The edge e is decomposed into a block index i < 2*m + 5 and an intra-block type j ∈ Fin 6.

    Deconstruct e into its components (i, j), where i indexes the 4-vertex block along the cycle of length 2*m + 5 and j ∈ {0, ..., 5} selects the edge type within that block. The bound i < 2*m + 5 is recorded from the definition of Fin.

    lines 4–6

      rcases e with ⟨i,j⟩
      have hi := i.isLt
      skip
  2. It suffices to verify the theorem separately for each of the six edge types j ∈ {0, 1, 2, 3, 4, 5}.

    Exhaustive case analysis on the finite type Fin 6 via `fin_cases j` splits the proof into six separate cases, corresponding to the possible values 0 through 5 for j.

    line 7

      fin_cases j
  3. In each of the six cases, the edge inequality, adjacency condition, and goodness predicate expand into relations on natural number indices.

    For all cases, rewrite the edge inequality into distinctness of endpoints using `Sym2.eq_iff`. Then expand the definitions of the witness mapping `cyclic_four_block_W`, the touching predicate, the goodness condition, vertex sources/destinations, and cyclic predecessors/successors. Equalities of `Fin` values are reduced to equalities of natural numbers using `Fin.ext_iff` and `Fin.mk.injEq`, and truth values are simplified using elementary propositional rules.

    lines 8–11

    uses ne_eq, Sym2.eq_iff, Prod.mk.injEq, Fin.mk.injEq, Fin.ext_iff, and_true, and_false, or_true, or_false, true_and, false_and, true_or, false_or, not_true_eq_false, not_false_eq_true

      all_goals simp only [ne_eq,cyclic_four_block_edge,Sym2.eq_iff,Prod.mk.injEq,Fin.mk.injEq]
      all_goals dsimp [cyclic_four_block_W,cyclic_four_block_touch,cyclic_four_block_good,cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_next,cyclic_four_block_prev]
      all_goals try simp only [Fin.mk.injEq,Fin.ext_iff]
      all_goals try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *
  4. All six cases hold across all cycle boundary conditions. automation

    For internal edge types j ∈ {0, 1, 2}, no wraparound occurs and the resulting arithmetic statements are closed directly by linear arithmetic (`omega`). For edge types j ∈ {3, 4, 5}, the witness and endpoint definitions contain `if-then-else` conditions corresponding to whether i is at the cycle boundary (e.g., i = 0 or i + 1 = 2*m + 5). A nested search strategy repeatedly splits these boundary cases (`split_ifs`), simplifies the resulting equations, and proves each branch by linear integer arithmetic (`omega`).

    lines 12–23

    uses Prod.mk.injEq, Fin.mk.injEq, Fin.ext_iff, and_true, and_false, or_true, or_false, true_and, false_and, true_or, false_or, not_true_eq_false, not_false_eq_true

      all_goals first | omega | (
        (try split_ifs at *) <;> (try dsimp at *) <;>
        (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;>
        (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;>
        first | omega | (
          (try split_ifs at *) <;> (try dsimp at *) <;>
          (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;>
          (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;>
          first | omega | (
            (try split_ifs at *) <;> (try dsimp at *) <;>
            (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;>
            (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;> omega)))
ne_eq
The inequality a ≠ b is defined as ¬(a = b).
Sym2.eq_iff
Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) ∨ (x = w ∧ y = z).
Prod.mk.injEq
Two ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
Fin.mk.injEq
Two elements of Fin n formed with explicit bounds are equal if and only if their underlying natural values are equal.
Fin.ext_iff
Two elements of Fin n are equal if and only if their underlying natural values are equal.
and_true
For any proposition p, p ∧ True simplifies to p.
and_false
For any proposition p, p ∧ False simplifies to False.
or_true
For any proposition p, p ∨ True simplifies to True.
or_false
For any proposition p, p ∨ False simplifies to p.
true_and
For any proposition p, True ∧ p simplifies to p.
false_and
For any proposition p, False ∧ p simplifies to False.
true_or
For any proposition p, True ∨ p simplifies to True.
false_or
For any proposition p, False ∨ p simplifies to p.
not_true_eq_false
¬True simplifies to False.
not_false_eq_true
¬False simplifies to True.

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 cyclic_four_block_witness (m : ℕ) (e : (Fin (2*m+5) × Fin 6)) :    cyclic_four_block_edge m e ≠ cyclic_four_block_edge m (cyclic_four_block_W m e) ∧    cyclic_four_block_touch m e (cyclic_four_block_W m e) ∧ cyclic_four_block_good m (cyclic_four_block_W m e) := by  rcases e with ⟨i,j⟩  have hi := i.isLt  skip  fin_cases j  all_goals simp only [ne_eq,cyclic_four_block_edge,Sym2.eq_iff,Prod.mk.injEq,Fin.mk.injEq]  all_goals dsimp [cyclic_four_block_W,cyclic_four_block_touch,cyclic_four_block_good,cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_next,cyclic_four_block_prev]  all_goals try simp only [Fin.mk.injEq,Fin.ext_iff]  all_goals try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *  all_goals first | omega | (    (try split_ifs at *) <;> (try dsimp at *) <;>    (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;>    (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;>    first | omega | (      (try split_ifs at *) <;> (try dsimp at *) <;>      (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;>      (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;>      first | omega | (        (try split_ifs at *) <;> (try dsimp at *) <;>        (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;>        (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;> omega)))
See it in the graphDiscuss this resultChallenge it