AFTD Auto-Formalizing Theoretical Domains

simple_graph_rich_neighbor_five_subdivide_three_palette

theoremverified

Scalar five-color contract for replacing a cubic edge by a four-edge path and three pendant edges: every new internal vertex has an incident rich path edge; both end edges remain rich when the old boundary was rich.

Statement

theorem simple_graph_rich_neighbor_five_subdivide_three_palette
    (x a b c d : Fin 5)
    (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c) (hxd : x ≠ d)
    (hab : a ≠ b) (hcd : c ≠ d) :
    ∃ y z A B C : Fin 5,
      [x,y,A].Pairwise (· ≠ ·) ∧
      [y,z,B].Pairwise (· ≠ ·) ∧
      [z,x,C].Pairwise (· ≠ ·) ∧
      (([a,b,y,A].Pairwise (· ≠ ·)) ∨ ([x,A,z,B].Pairwise (· ≠ ·))) ∧
      (([x,A,z,B].Pairwise (· ≠ ·)) ∨ ([y,B,x,C].Pairwise (· ≠ ·))) ∧
      (([y,B,x,C].Pairwise (· ≠ ·)) ∨ ([z,C,c,d].Pairwise (· ≠ ·))) ∧
      ([a,b,c,d].Pairwise (· ≠ ·) →
        [a,b,y,A].Pairwise (· ≠ ·) ∧ [z,C,c,d].Pairwise (· ≠ ·))
Source
Helper for OP-309 (arXiv:2610.21868, Conjecture 1.1). This is only the local palette contract, without graph transport. All 144 normalized proper boundary cases were independently checked in experiment 4659.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof proceeds by case analysis on whether the boundary colors a, b, c, d are pairwise distinct. If they are, then along with x they exhaust all five elements of Fin 5, and the explicit assignment (c, a, d, b, b) satisfies all conditions. Otherwise, the boundary distinctness implication holds vacuously, and choosing four elements distinct from x via a permutation lemma allows the assignment (y, z, A, B, A) to satisfy all remaining conditions.

  1. For any element x of Fin 5, we can complete it to a list of five distinct elements.

    We consider the permutation σ swapping 0 and x. Since 0, 1, 2, 3, 4 are distinct in Fin 5, applying the injective map σ produces five distinct elements starting with x.

    lines 3–8

      let σ := Equiv.swap (0 : Fin 5) x
      refine ⟨σ 1, σ 2, σ 3, σ 4, ?_⟩
      have hx : σ 0 = x := by simp [σ]
      rw [← hx]
      have h : ([0,1,2,3,4] : List (Fin 5)).Pairwise (· ≠ ·) := by decide
      exact h.map σ (fun _ _ hne => σ.injective.ne hne)
  2. We split into cases based on whether the boundary colors a, b, c, d are all pairwise distinct.

    We perform a case split on the condition that [a, b, c, d] are pairwise distinct.

    line 23

      by_cases h : [a,b,c,d].Pairwise (· ≠ ·)
  3. When a, b, c, d are pairwise distinct, the choice (c, a, d, b, b) satisfies all conditions. automation

    We instantiate (y, z, A, B, C) with (c, a, d, b, b). Because x is distinct from a, b, c, d, these five elements exhaust Fin 5 and are distinct. All required pairwise distinctness conditions and disjunctions reduce to the distinctness of combinations of these elements.

    lines 24–25

    uses List.pairwise_cons, ne_comm

      · refine ⟨c,a,d,b,b, ?_⟩
        simp_all [List.pairwise_cons, ne_comm]
  4. When a, b, c, d are not all distinct, we obtain four elements distinct from x.

    We apply the helper lemma simple_graph_rich_neighbor_five_subdivide_three_palette_distinct to x to obtain y, z, A, B such that [x, y, z, A, B] are pairwise distinct.

    line 26

    uses simple_graph_rich_neighbor_five_subdivide_three_palette_distinct

      · obtain ⟨y,z,A,B,hfive⟩ := simple_graph_rich_neighbor_five_subdivide_three_palette_distinct x
  5. The choice (y, z, A, B, A) satisfies all required conditions. automation

    We instantiate (y, z, A, B, C) with (y, z, A, B, A). Each required triple or quadruple of internal vertices consists of distinct elements chosen from the pairwise distinct list [x, y, z, A, B]. The final implication is vacuously true because [a, b, c, d] are not pairwise distinct.

    lines 27–28

    uses List.pairwise_cons, ne_comm

        refine ⟨y,z,A,B,A, ?_⟩
        simp_all [List.pairwise_cons, ne_comm]
List.pairwise_cons
A non-empty list has pairwise distinct elements if and only if the head is distinct from all elements of the tail and the tail is pairwise distinct.
ne_comm
Inequality is symmetric: a ≠ b is equivalent to b ≠ a.
simple_graph_rich_neighbor_five_subdivide_three_palette_distinct
For any element x of Fin 5, there exist four other elements such that all five elements are pairwise distinct.

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

private lemma simple_graph_rich_neighbor_five_subdivide_three_palette_distinct (x : Fin 5) :    ∃ y z a b : Fin 5, [x,y,z,a,b].Pairwise (· ≠ ·) := by  let σ := Equiv.swap (0 : Fin 5) x  refine ⟨σ 1, σ 2, σ 3, σ 4, ?_⟩  have hx : σ 0 = x := by simp [σ]  rw [← hx]  have h : ([0,1,2,3,4] : List (Fin 5)).Pairwise (· ≠ ·) := by decide  exact h.map σ (fun _ _ hne => σ.injective.ne hne)theorem simple_graph_rich_neighbor_five_subdivide_three_palette    (x a b c d : Fin 5)    (hxa : x ≠ a) (hxb : x ≠ b) (hxc : x ≠ c) (hxd : x ≠ d)    (hab : a ≠ b) (hcd : c ≠ d) :    ∃ y z A B C : Fin 5,      [x,y,A].Pairwise (· ≠ ·) ∧      [y,z,B].Pairwise (· ≠ ·) ∧      [z,x,C].Pairwise (· ≠ ·) ∧      (([a,b,y,A].Pairwise (· ≠ ·)) ∨ ([x,A,z,B].Pairwise (· ≠ ·))) ∧      (([x,A,z,B].Pairwise (· ≠ ·)) ∨ ([y,B,x,C].Pairwise (· ≠ ·))) ∧      (([y,B,x,C].Pairwise (· ≠ ·)) ∨ ([z,C,c,d].Pairwise (· ≠ ·))) ∧      ([a,b,c,d].Pairwise (· ≠ ·) →        [a,b,y,A].Pairwise (· ≠ ·) ∧ [z,C,c,d].Pairwise (· ≠ ·)) := by  by_cases h : [a,b,c,d].Pairwise (· ≠ ·)  · refine ⟨c,a,d,b,b, ?_⟩    simp_all [List.pairwise_cons, ne_comm]  · obtain ⟨y,z,A,B,hfive⟩ := simple_graph_rich_neighbor_five_subdivide_three_palette_distinct x    refine ⟨y,z,A,B,A, ?_⟩    simp_all [List.pairwise_cons, ne_comm]
See it in the graphDiscuss this resultChallenge it