AFTD Auto-Formalizing Theoretical Domains

cyclic_four_block_nondiag

theoremverified

Step of cyclic_four_block_graph_exists_rich_neighbor_five_coloring: nondiag.

Statement

theorem cyclic_four_block_nondiag (m : ℕ) (e : (Fin (2*m+5) × Fin 6)) :
    ¬ (cyclic_four_block_edge m e).IsDiag
Source
decomposition of cyclic_four_block_graph_exists_rich_neighbor_five_coloring
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_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…
Used by 1

The proof, explained

The theorem asserts that no edge of the cyclic four-block graph is a self-loop (diagonal in Sym2). Unfolding definitions and applying Sym2.mk_isDiag_iff reduces this to showing that the source and destination vertex indices are distinct for every edge e = (i, j). Exhaustive case analysis on the within-block index j ∈ {0, ..., 5} produces six explicit inequalities. Finally, splitting on the cycle wrap-around condition and applying linear arithmetic (omega) confirms that source and destination differ in every case.

  1. The edge e is non-diagonal if and only if its source and destination vertex indices are distinct.

    Unfolding the definition of cyclic_four_block_edge, the edge is represented as the unordered pair s(src, dst) in Sym2 (Fin (4 * (2 * m + 5))). Applying Sym2.mk_isDiag_iff reduces the non-diagonality of s(src, dst) to the distinctness src ≠ dst, and Fin.mk.injEq reduces inequality of Fin elements to inequality of their underlying natural numbers.

    line 3

    uses Sym2.mk_isDiag_iff, Fin.mk.injEq

      simp only [cyclic_four_block_edge,Sym2.mk_isDiag_iff,Fin.mk.injEq]
  2. Decompose the edge index e into a block index i and a within-block edge index j.

    We unpack e as a pair (i, j) with i ∈ Fin (2 * m + 5) and j ∈ Fin 6, and record the bound i.val < 2 * m + 5 as hypothesis hi from i.isLt. The subsequent skip tactic is a no-op that leaves the goal state unchanged.

    lines 4–6

      rcases e with ⟨i,j⟩
      have hi := i.isLt
      skip
  3. Branch into six cases according to the within-block edge index j ∈ Fin 6.

    Exhaustive case analysis on j via fin_cases produces six subgoals for j ∈ {0, 1, 2, 3, 4, 5}. In each case, definitional simplification (dsimp) unfolds cyclic_four_block_src, cyclic_four_block_dst, and cyclic_four_block_next, replacing vector indexing by explicit arithmetic expressions in the block index i.

    line 7

      fin_cases j <;> dsimp [cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_next]
  4. Establish the inequality between source and destination in all six cases.

    For j ∈ {0, 1, 2}, the source and destination indices are within the same block, yielding the inequalities 4i ≠ 4i + 1, 4i ≠ 4i + 2, and 4i ≠ 4i + 3. For j ∈ {3, 4, 5}, the destination connects to the next block, so split_ifs splits on the cycle wrap-around condition (whether i + 1 < 2m + 5 or i + 1 = 2m + 5). In every branch, linear arithmetic (omega) dispatches the goal using the hypothesis hi : i < 2m + 5.

    line 8

      all_goals (try split_ifs) <;> omega
Sym2.mk_isDiag_iff
An unordered pair s(x, y) is diagonal (i.e. represents a self-loop) if and only if x = y.
Fin.mk.injEq
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.

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_nondiag (m : ℕ) (e : (Fin (2*m+5) × Fin 6)) :    ¬ (cyclic_four_block_edge m e).IsDiag := by  simp only [cyclic_four_block_edge,Sym2.mk_isDiag_iff,Fin.mk.injEq]  rcases e with ⟨i,j⟩  have hi := i.isLt  skip  fin_cases j <;> dsimp [cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_next]  all_goals (try split_ifs) <;> omega
See it in the graphDiscuss this resultChallenge it