cyclic_four_block_witness
Step of cyclic_four_block_graph_exists_rich_neighbor_five_coloring: witness.
Statement
theorem cyclic_four_block_witness (m : ℕ) (e : (Fin (2*m+5) × Fin 6)) :
cyclic_four_block_edge m e ≠ cyclic_four_block_edge m (cyclic_four_block_W m e) ∧
cyclic_four_block_touch m e (cyclic_four_block_W m e) ∧ cyclic_four_block_good m (cyclic_four_block_W m e)- Source
- decomposition of cyclic_four_block_graph_exists_rich_neighbor_five_coloring
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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_prevHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the previous 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…
- cyclic_four_block_touchHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: two indexed edges share an endpoint (comparison of src/dst values).
- cyclic_four_block_goodHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the indexed edges whose four neighbouring edges receive four…
- cyclic_four_block_WHelper for cyclic_four_block_graph_exists_rich_neighbor_five_coloring: the chosen rich neighbour (a good adjacent edge) of each indexed…
- 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 proves that for any edge e in the cyclic four-block graph, the candidate edge W(e) is distinct from e, shares a vertex with e, and satisfies the 'good' edge property. The proof decomposes e into a block index i and edge type j ∈ Fin 6, and performs an exhaustive case analysis on j. After expanding all graph-theoretic definitions and reducing edge equality to endpoint matching, internal edge cases are dispatched immediately by linear arithmetic, while boundary-crossing edges are resolved by splitting on the cycle wraparound conditions and solving each branch with linear arithmetic.
The edge e is decomposed into a block index i < 2*m + 5 and an intra-block type j ∈ Fin 6.
Deconstruct e into its components (i, j), where i indexes the 4-vertex block along the cycle of length 2*m + 5 and j ∈ {0, ..., 5} selects the edge type within that block. The bound i < 2*m + 5 is recorded from the definition of Fin.
rcases e with ⟨i,j⟩ have hi := i.isLt skip
It suffices to verify the theorem separately for each of the six edge types j ∈ {0, 1, 2, 3, 4, 5}.
Exhaustive case analysis on the finite type Fin 6 via `fin_cases j` splits the proof into six separate cases, corresponding to the possible values 0 through 5 for j.
fin_cases j
In each of the six cases, the edge inequality, adjacency condition, and goodness predicate expand into relations on natural number indices.
For all cases, rewrite the edge inequality into distinctness of endpoints using `Sym2.eq_iff`. Then expand the definitions of the witness mapping `cyclic_four_block_W`, the touching predicate, the goodness condition, vertex sources/destinations, and cyclic predecessors/successors. Equalities of `Fin` values are reduced to equalities of natural numbers using `Fin.ext_iff` and `Fin.mk.injEq`, and truth values are simplified using elementary propositional rules.
uses
ne_eq,Sym2.eq_iff,Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff,and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_trueall_goals simp only [ne_eq,cyclic_four_block_edge,Sym2.eq_iff,Prod.mk.injEq,Fin.mk.injEq] all_goals dsimp [cyclic_four_block_W,cyclic_four_block_touch,cyclic_four_block_good,cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_next,cyclic_four_block_prev] all_goals try simp only [Fin.mk.injEq,Fin.ext_iff] all_goals try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *
All six cases hold across all cycle boundary conditions. automation
For internal edge types j ∈ {0, 1, 2}, no wraparound occurs and the resulting arithmetic statements are closed directly by linear arithmetic (`omega`). For edge types j ∈ {3, 4, 5}, the witness and endpoint definitions contain `if-then-else` conditions corresponding to whether i is at the cycle boundary (e.g., i = 0 or i + 1 = 2*m + 5). A nested search strategy repeatedly splits these boundary cases (`split_ifs`), simplifies the resulting equations, and proves each branch by linear integer arithmetic (`omega`).
uses
Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff,and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_trueall_goals first | omega | ( (try split_ifs at *) <;> (try dsimp at *) <;> (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;> (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;> first | omega | ( (try split_ifs at *) <;> (try dsimp at *) <;> (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;> (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;> first | omega | ( (try split_ifs at *) <;> (try dsimp at *) <;> (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;> (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;> omega)))
ne_eq- The inequality a ≠ b is defined as ¬(a = b).
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) ∨ (x = w ∧ y = z).
Prod.mk.injEq- Two ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
Fin.mk.injEq- Two elements of Fin n formed with explicit bounds are equal if and only if their underlying natural values are equal.
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural values are equal.
and_true- For any proposition p, p ∧ True simplifies to p.
and_false- For any proposition p, p ∧ False simplifies to False.
or_true- For any proposition p, p ∨ True simplifies to True.
or_false- For any proposition p, p ∨ False simplifies to p.
true_and- For any proposition p, True ∧ p simplifies to p.
false_and- For any proposition p, False ∧ p simplifies to False.
true_or- For any proposition p, True ∨ p simplifies to True.
false_or- For any proposition p, False ∨ p simplifies to p.
not_true_eq_false- ¬True simplifies to False.
not_false_eq_true- ¬False simplifies to True.
- The proof relies heavily on tactical automation: `split_ifs` systematically branches on the boundary conditions of the cyclic block structure (such as whether an index is at the beginning or end of the cycle), while `omega` resolves the linear arithmetic inequalities generated 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_witness (m : ℕ) (e : (Fin (2*m+5) × Fin 6)) : cyclic_four_block_edge m e ≠ cyclic_four_block_edge m (cyclic_four_block_W m e) ∧ cyclic_four_block_touch m e (cyclic_four_block_W m e) ∧ cyclic_four_block_good m (cyclic_four_block_W m e) := by rcases e with ⟨i,j⟩ have hi := i.isLt skip fin_cases j all_goals simp only [ne_eq,cyclic_four_block_edge,Sym2.eq_iff,Prod.mk.injEq,Fin.mk.injEq] all_goals dsimp [cyclic_four_block_W,cyclic_four_block_touch,cyclic_four_block_good,cyclic_four_block_src,cyclic_four_block_dst,cyclic_four_block_next,cyclic_four_block_prev] all_goals try simp only [Fin.mk.injEq,Fin.ext_iff] all_goals try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at * all_goals first | omega | ( (try split_ifs at *) <;> (try dsimp at *) <;> (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;> (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;> first | omega | ( (try split_ifs at *) <;> (try dsimp at *) <;> (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;> (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;> first | omega | ( (try split_ifs at *) <;> (try dsimp at *) <;> (try simp only [Prod.mk.injEq,Fin.mk.injEq,Fin.ext_iff] at *) <;> (try simp only [and_true,and_false,or_true,or_false,true_and,false_and,true_or,false_or,not_true_eq_false,not_false_eq_true] at *) <;> omega)))