cyclic_four_block_bounds
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.
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.
rcases e with ⟨i,j⟩ fin_cases j <;> dsimp [cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_next]
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.
all_goals (try split_ifs) <;> omega
- The arithmetic bounds across all cases and conditional branches are verified automatically by the `omega` decision procedure for Presburger arithmetic.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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