simple_graph_rich_neighbor_five_subdivide_three_palette
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.
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.
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)
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.
by_cases h : [a,b,c,d].Pairwise (· ≠ ·)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.
uses
List.pairwise_cons,ne_comm· refine ⟨c,a,d,b,b, ?_⟩ simp_all [List.pairwise_cons, ne_comm]
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.
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 xThe 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.
uses
List.pairwise_cons,ne_commrefine ⟨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
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.
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]