cyclic_four_block_touch_iff
Step of cyclic_four_block_graph_exists_rich_neighbor_five_coloring: touch iff.
Statement
theorem cyclic_four_block_touch_iff (m : ℕ) (e f : (Fin (2*m+5) × Fin 6)) :
cyclic_four_block_touch m e f ↔ ∃ v, v ∈ cyclic_four_block_edge m e ∧ v ∈ cyclic_four_block_edge m f- 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_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_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_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
Two edges in the cyclic four-block graph touch if and only if they share a common vertex. Unfolding the definitions reduces both conditions to matching an endpoint of one edge with an endpoint of the other. The proof checks the resulting four combinations in each direction, converting between endpoint indices in ℕ and vertex coordinates in Fin via Fin.ext and Fin.val.
The equivalence between touching and sharing a vertex reduces to matching an endpoint of e with an endpoint of f.
Unfolding cyclic_four_block_touch and cyclic_four_block_edge expresses touching as a four-way disjunction of equalities between the source and destination indices of e and f. Rewriting with Sym2.mem_iff unpacks membership in the unordered pair representing each edge into being equal to either its source or its destination vertex. Splitting the equivalence with constructor yields the forward and backward implications.
uses
Sym2.mem_iffunfold cyclic_four_block_touch cyclic_four_block_edge simp only [Sym2.mem_iff] constructor
If any endpoint index of e equals an endpoint index of f, then the two edges share a vertex.
We split into four cases depending on which pair of endpoints coincides: (src e = src f), (src e = dst f), (dst e = src f), or (dst e = dst f). In each case, the coinciding endpoint provides the witness for the existential quantifier. The equality of natural numbers is lifted to an equality of Fin vertices via Fin.ext, placing the vertex in both edges.
uses
Fin.ext,Or.inl,Or.inr· rintro (h|h|h|h) · exact ⟨_,Or.inl rfl,Or.inl (Fin.ext h)⟩ · exact ⟨_,Or.inl rfl,Or.inr (Fin.ext h)⟩ · exact ⟨_,Or.inr rfl,Or.inl (Fin.ext h)⟩ · exact ⟨_,Or.inr rfl,Or.inr (Fin.ext h)⟩If a vertex belongs to both edges, then an endpoint index of e equals an endpoint index of f.
Given a common vertex v, case analysis on v's membership in each edge yields four subcases, corresponding to whether v is the source or destination of e, and whether it is the source or destination of f. By transitivity and symmetry, the two corresponding endpoint vertices are equal; projecting this equality to ℕ via congrArg Fin.val establishes the corresponding disjunct of cyclic_four_block_touch.
uses
congrArg,Fin.val,Or.inl,Or.inr· rintro ⟨v,(he|he),(hf|hf)⟩ · exact Or.inl (congrArg Fin.val (he.symm.trans hf)) · exact Or.inr (Or.inl (congrArg Fin.val (he.symm.trans hf))) · exact Or.inr (Or.inr (Or.inl (congrArg Fin.val (he.symm.trans hf)))) · exact Or.inr (Or.inr (Or.inr (congrArg Fin.val (he.symm.trans hf))))
Sym2.mem_iff- An element belongs to an unordered pair s(b, c) if and only if it equals b or equals c.
Fin.ext- Two elements of Fin n are equal if their underlying natural values are equal.
Or.inl- Given a proof of A, establishes the disjunction A ∨ B.
Or.inr- Given a proof of B, establishes the disjunction A ∨ B.
congrArg- Applying a function to equal arguments yields equal results: if a₁ = a₂, then f a₁ = f a₂.
Fin.val- Projects a bounded natural number in Fin n to its underlying value in ℕ.
- The endpoints of an edge are defined as natural numbers in cyclic_four_block_touch, whereas vertices in cyclic_four_block_edge are elements of Fin (4 * (2 * m + 5)). The proof repeatedly translates between equalities in ℕ and equalities in Fin using Fin.ext and Fin.val.
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_touch_iff (m : ℕ) (e f : (Fin (2*m+5) × Fin 6)) : cyclic_four_block_touch m e f ↔ ∃ v, v ∈ cyclic_four_block_edge m e ∧ v ∈ cyclic_four_block_edge m f := by unfold cyclic_four_block_touch cyclic_four_block_edge simp only [Sym2.mem_iff] constructor · rintro (h|h|h|h) · exact ⟨_,Or.inl rfl,Or.inl (Fin.ext h)⟩ · exact ⟨_,Or.inl rfl,Or.inr (Fin.ext h)⟩ · exact ⟨_,Or.inr rfl,Or.inl (Fin.ext h)⟩ · exact ⟨_,Or.inr rfl,Or.inr (Fin.ext h)⟩ · rintro ⟨v,(he|he),(hf|hf)⟩ · exact Or.inl (congrArg Fin.val (he.symm.trans hf)) · exact Or.inr (Or.inl (congrArg Fin.val (he.symm.trans hf))) · exact Or.inr (Or.inr (Or.inl (congrArg Fin.val (he.symm.trans hf)))) · exact Or.inr (Or.inr (Or.inr (congrArg Fin.val (he.symm.trans hf))))