AFTD Auto-Formalizing Theoretical Domains

cyclic_four_block_col_bound

theoremverified

Step of cyclic_four_block_graph_exists_rich_neighbor_five_coloring: col bound.

Statement

theorem cyclic_four_block_col_bound (m : ℕ) (e : (Fin (2*m+5) × Fin 6)) : cyclic_four_block_col_nat m e < 5
Source
decomposition of cyclic_four_block_graph_exists_rich_neighbor_five_coloring
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • cyclic_four_block_col_natHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the periodic five-colour assignment to indexed edges, as a natural…
Used by 1
  • cyclic_four_block_colHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the periodic five-colouring of indexed edges, valued in Fin 5.

The proof, explained

The theorem establishes that the coloring function $\mathrm{cyclic\_four\_block\_col\_nat}$ always assigns a color strictly less than 5 to any pair $(i, j) \in \mathrm{Fin}(2m+5) \times \mathrm{Fin}(6)$. The proof proceeds by exhaustive case analysis on the finite second coordinate $j \in \{0, \dots, 5\}$. In each case, evaluating the conditional expression yields an explicit integer from $\{0, 1, 2, 3, 4\}$, which is verified to be strictly less than 5 by arithmetic.

  1. Decompose the pair $e$ into its coordinates $(i, j)$.

    Write the pair $e \in \mathrm{Fin}(2m+5) \times \mathrm{Fin}(6)$ as $(i, j)$ so that the second coordinate $j$ can be analyzed directly.

    line 2

      rcases e with ⟨i,j⟩
  2. Reduce the goal to checking the bound for each of the six concrete values of $j \in \{0, 1, 2, 3, 4, 5\}$.

    Since $j$ belongs to the finite type $\mathrm{Fin}(6)$, we split into the six cases $j = 0, 1, 2, 3, 4, 5$ and unfold the definition of the coloring function $\mathrm{cyclic\_four\_block\_col\_nat}$.

    line 3

      fin_cases j <;> dsimp [cyclic_four_block_col_nat]
  3. In every case, the coloring value is strictly less than 5. automation

    For each value of $j$, splitting the `if-then-else` conditions on $i$ reduces the coloring function to a constant integer (each taking values among $0, 1, 2, 3, 4$). Linear integer arithmetic (`omega`) closes each case by verifying that the resulting constant is less than 5.

    line 4

      all_goals split_ifs <;> omega

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_col_bound (m : ℕ) (e : (Fin (2*m+5) × Fin 6)) : cyclic_four_block_col_nat m e < 5 := by  rcases e with ⟨i,j⟩  fin_cases j <;> dsimp [cyclic_four_block_col_nat]  all_goals split_ifs <;> omega
See it in the graphDiscuss this resultChallenge it