truncation_local_state_internal_cover
With six colours, a local state at v (c v injective on the three edges at v, h v injective there, and no h v e equal to any c v f) has h v mapping onto I_v: every colour ω different from all c v f (f at v) equals h v g for some edge g at v.
Statement
theorem truncation_local_state_internal_cover {V E Ω : Type*} [Fintype Ω] (hΩ : Fintype.card Ω = 6) {ends : E → Sym2 V} (hcubic : ∀ v, Set.ncard {e | v ∈ ends e} = 3) {c h : V → E → Ω} (hc : ∀ v e f, v ∈ ends e → v ∈ ends f → c v e = c v f → e = f) (hh : ∀ v e f, v ∈ ends e → v ∈ ends f → h v e = h v f → e = f) (hch : ∀ v e f, v ∈ ends e → v ∈ ends f → h v e ≠ c v f) {v : V} {ω : Ω} (hω : ∀ f, v ∈ ends f → c v f ≠ ω) : ∃ g, v ∈ ends g ∧ h v g = ω
- Source
- helper for truncation_local_states_strong_coloring_iff (arXiv:2610.41950 Lemma 2.1, PR-677)
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- truncation_local_states_strong_coloring_iffLemma 2.1 of arXiv:2610.41950. Let G be a loopless cubic multigraph, given by ends : E → Sym2 V (no Fintype or Finite instance on V or E…
The proof, explained
The theorem is proved by contradiction using the pigeonhole principle. In a cubic graph, any vertex v is incident to exactly three edges x, y, z, on which the local colorings c v and h v take six distinct values due to injectivity and mutual disjointness. If a color ω is absent from both the c-values and the h-values at v, it can be appended to form a collection of seven pairwise distinct colors in Ω. This yields an injective map from a 7-element set into Ω, contradicting the assumption that Ω has cardinality 6.
Assume for contradiction that no edge incident to v has color ω under h v.
We begin a proof by contradiction (by_contra hno) and push the negation inward (push Not at hno), producing the hypothesis that h v g ≠ ω for every edge g incident to v.
by_contra hno push Not at hno
There exist three distinct edges x, y, z forming the entire set of edges incident to v.
Since the graph is cubic, the set of edges incident to v has cardinality 3. By Set.ncard_eq_three.mp, this set equals {x, y, z} for pairwise distinct edges x, y, z. Using set extensionality (Set.ext_iff.mp) together with Or.inl and Or.inr, we verify that each of x, y, and z is incident to v.
uses
Set.ncard_eq_three.mp,Set.ext_iff.mp,Or.inl,Or.inrobtain ⟨x, y, z, hxy, hxz, hyz, hs⟩ := Set.ncard_eq_three.mp (hcubic v) have mem : ∀ k, v ∈ ends k ↔ k = x ∨ k = y ∨ k = z := fun k => by have := Set.ext_iff.mp hs k simpa using this have hx := (mem x).2 (Or.inl rfl) have hy := (mem y).2 (Or.inr (Or.inl rfl)) have hz := (mem z).2 (Or.inr (Or.inr rfl))
The color ω and the six colors c v x, c v y, c v z, h v x, h v y, h v z are all pairwise distinct.
We establish all 21 pairwise inequalities among these 7 colors: ω differs from the c-colors by the assumption hω (a1–a3); ω differs from the h-colors by the contradiction hypothesis hno (b1–b3); the three c-colors are pairwise distinct by injectivity of c (c1–c3); the three h-colors are pairwise distinct by injectivity of h (d1–d3); and every h-color is distinct from every c-color by the disjointness hypothesis hch (e1–e9).
have a1 := hω x hx have a2 := hω y hy have a3 := hω z hz have b1 := hno x hx have b2 := hno y hy have b3 := hno z hz have c1 : c v x ≠ c v y := fun e => hxy (hc v x y hx hy e) have c2 : c v x ≠ c v z := fun e => hxz (hc v x z hx hz e) have c3 : c v y ≠ c v z := fun e => hyz (hc v y z hy hz e) have d1 : h v x ≠ h v y := fun e => hxy (hh v x y hx hy e) have d2 : h v x ≠ h v z := fun e => hxz (hh v x z hx hz e) have d3 : h v y ≠ h v z := fun e => hyz (hh v y z hy hz e) have e1 := hch v x x hx hx have e2 := hch v x y hx hy have e3 := hch v x z hx hz have e4 := hch v y x hy hx have e5 := hch v y y hy hy have e6 := hch v y z hy hz have e7 := hch v z x hz hx have e8 := hch v z y hz hy have e9 := hch v z z hz hz
The map F : Fin 7 → Ω enumerating ω, the three c-colors, and the three h-colors is injective. automation
We define F as an explicit 7-tuple. Given any indices i, j ∈ Fin 7 with F i = F j, exhaustive case analysis over all 49 pairs using fin_cases resolves i = j trivially by reflexivity and closes every off-diagonal case by finding a contradiction with one of the pairwise inequalities established in the previous step.
let F : Fin 7 → Ω := ![ω, c v x, c v y, c v z, h v x, h v y, h v z] have hF : Function.Injective F := by intro i j hij fin_cases i <;> fin_cases j <;> first | rfl | (simp [F] at hij <;> first | exact absurd hij (by assumption) | exact absurd hij.symm (by assumption))
A contradiction is reached since the existence of an injection from a 7-element set into Ω contradicts |Ω| = 6. automation
By Fintype.card_le_of_injective, the injective map F yields |Fin 7| ≤ |Ω|. Rewriting with Fintype.card_fin and the hypothesis hΩ gives 7 ≤ 6, which omega recognizes as an arithmetic contradiction.
uses
Fintype.card_le_of_injective,Fintype.card_finhave := Fintype.card_le_of_injective F hF rw [Fintype.card_fin, hΩ] at this omega
Set.ncard_eq_three.mp- A finite set with cardinality 3 can be written as {x, y, z} with x, y, and z pairwise distinct.
Set.ext_iff.mp- If two sets are equal, an element belongs to the first if and only if it belongs to the second.
Or.inl- From a proof of P, concludes P ∨ Q.
Or.inr- From a proof of Q, concludes P ∨ Q.
Fintype.card_le_of_injective- An injective map from a finite type α to a finite type β implies |α| ≤ |β|.
Fintype.card_fin- The cardinality of the standard finite set Fin n is n.
- The injectivity of the 7-element vector F is verified formally in Step 4 by finite case analysis (fin_cases), checking all 49 index pairs (i, j) against the pairwise inequality hypotheses.
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 truncation_local_state_internal_cover {V E Ω : Type*} [Fintype Ω] (hΩ : Fintype.card Ω = 6) {ends : E → Sym2 V} (hcubic : ∀ v, Set.ncard {e | v ∈ ends e} = 3) {c h : V → E → Ω} (hc : ∀ v e f, v ∈ ends e → v ∈ ends f → c v e = c v f → e = f) (hh : ∀ v e f, v ∈ ends e → v ∈ ends f → h v e = h v f → e = f) (hch : ∀ v e f, v ∈ ends e → v ∈ ends f → h v e ≠ c v f) {v : V} {ω : Ω} (hω : ∀ f, v ∈ ends f → c v f ≠ ω) : ∃ g, v ∈ ends g ∧ h v g = ω := by by_contra hno push Not at hno obtain ⟨x, y, z, hxy, hxz, hyz, hs⟩ := Set.ncard_eq_three.mp (hcubic v) have mem : ∀ k, v ∈ ends k ↔ k = x ∨ k = y ∨ k = z := fun k => by have := Set.ext_iff.mp hs k simpa using this have hx := (mem x).2 (Or.inl rfl) have hy := (mem y).2 (Or.inr (Or.inl rfl)) have hz := (mem z).2 (Or.inr (Or.inr rfl)) have a1 := hω x hx have a2 := hω y hy have a3 := hω z hz have b1 := hno x hx have b2 := hno y hy have b3 := hno z hz have c1 : c v x ≠ c v y := fun e => hxy (hc v x y hx hy e) have c2 : c v x ≠ c v z := fun e => hxz (hc v x z hx hz e) have c3 : c v y ≠ c v z := fun e => hyz (hc v y z hy hz e) have d1 : h v x ≠ h v y := fun e => hxy (hh v x y hx hy e) have d2 : h v x ≠ h v z := fun e => hxz (hh v x z hx hz e) have d3 : h v y ≠ h v z := fun e => hyz (hh v y z hy hz e) have e1 := hch v x x hx hx have e2 := hch v x y hx hy have e3 := hch v x z hx hz have e4 := hch v y x hy hx have e5 := hch v y y hy hy have e6 := hch v y z hy hz have e7 := hch v z x hz hx have e8 := hch v z y hz hy have e9 := hch v z z hz hz let F : Fin 7 → Ω := ![ω, c v x, c v y, c v z, h v x, h v y, h v z] have hF : Function.Injective F := by intro i j hij fin_cases i <;> fin_cases j <;> first | rfl | (simp [F] at hij <;> first | exact absurd hij (by assumption) | exact absurd hij.symm (by assumption)) have := Fintype.card_le_of_injective F hF rw [Fintype.card_fin, hΩ] at this omega