AFTD Auto-Formalizing Theoretical Domains

cyclic_four_block_touch_iff

theoremverified

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

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.

  1. 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.

    lines 3–5

    uses Sym2.mem_iff

      unfold cyclic_four_block_touch cyclic_four_block_edge
      simp only [Sym2.mem_iff]
      constructor
  2. 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.

    lines 6–10

    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)⟩
  3. 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.

    lines 11–15

    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 ℕ.

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_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))))
See it in the graphDiscuss this resultChallenge it