cyclic_four_block_nondiag
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
- cyclic_four_block_graph_exists_rich_neighbor_five_coloringFor every m>=0, cyclic_four_block_graph m, on 4(2m+5) vertices, admits a rich-neighbor five-edge-coloring.
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.
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.
uses
Sym2.mk_isDiag_iff,Fin.mk.injEqsimp only [cyclic_four_block_edge,Sym2.mk_isDiag_iff,Fin.mk.injEq]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.
rcases e with ⟨i,j⟩ have hi := i.isLt skip
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.
fin_cases j <;> dsimp [cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_next]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.
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.
- Cases j ∈ {3, 4, 5} correspond to edges between adjacent blocks in the cycle, where the definitions of the destination vertex use conditional expressions (if-then-else) to wrap around at the cycle boundary; split_ifs branches on these conditions before omega dispatches the arithmetic in each branch.
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_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