AFTD Auto-Formalizing Theoretical Domains

cyclic_four_block_bounds

theoremverified

Step of cyclic_four_block_graph_exists_rich_neighbor_five_coloring: bounds.

Statement

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

The proof, explained

The theorem establishes that the source and destination vertex indices of any edge in the cyclic four-block graph are strictly bounded by $4(2m+5)$, ensuring all edges connect valid vertices. The proof unpacks the edge $e$ into its block index $i$ and edge type $j \in \mathrm{Fin}(6)$, and splits into six cases corresponding to each value of $j$. After expanding the definitions and splitting the conditional statements that handle cyclic wrap-around at the boundary, all resulting linear inequalities are resolved by integer arithmetic.

  1. The problem reduces to verifying the source and destination bounds for each of the six edge types $j \in \{0, 1, 2, 3, 4, 5\}$, with the endpoint functions evaluated.

    We unpack the edge $e$ into its block index $i \in \mathrm{Fin}(2m+5)$ and its intra-block edge type $j \in \mathrm{Fin}(6)$. We then perform an exhaustive case analysis on the six possible values of $j$ and simplify each case by unfolding the definitions of cyclic_four_block_src, cyclic_four_block_dst, and cyclic_four_block_next.

    lines 3–4

      rcases e with ⟨i,j⟩
      fin_cases j <;> dsimp [cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_next]
  2. In all six cases, both the source and destination vertex indices are strictly less than $4(2m+5)$. automation

    For each edge type $j$, any conditional expressions arising from the cyclic successor (handling the boundary case where $i + 1 = 2m + 5$) are split into their true and false branches. In every branch, the resulting inequalities on vertex indices follow from linear integer arithmetic (`omega`), since $i < 2m + 5$ and all constant offsets are at most 3.

    line 5

      all_goals (try 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_bounds (m : ℕ) (e : (Fin (2*m+5) × Fin 6)) :    cyclic_four_block_src m e < 4*(2*m+5) ∧ cyclic_four_block_dst m e < 4*(2*m+5) := by  rcases e with ⟨i,j⟩  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