AFTD Auto-Formalizing Theoretical Domains

truncation_local_state_internal_cover

theoremverified

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

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.

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

    lines 8–9

      by_contra hno
      push Not at hno
  2. 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.

    lines 10–16

    uses Set.ncard_eq_three.mp, Set.ext_iff.mp, Or.inl, Or.inr

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

    lines 17–37

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

    lines 38–45

      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))
  5. 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.

    lines 46–48

    uses Fintype.card_le_of_injective, Fintype.card_fin

      have := 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.

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