SATtoColor.SATtoColorSoundness
theoremverifiedimported Lean
Soundness of the 3-SAT to 3-colouring reduction. Let $f$ be a 3-SAT instance over a variable type $V$, that is, a list of clauses, each clause a triple of literals (positive or negative occurrences of variables). If the reduction graph $\mathrm{ReductionGraph}(f)$ admits a proper $3$-colouring, then $f$ is satisfiable: there exists a Boolean assignment $\mathrm{assign} \colon V \to \{\mathrm{true}, \mathrm{false}\}$ under which every clause of $f$ has at least one literal evaluating to $\mathrm{true}$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in lemma SATtoColor.SATtoColorSoundness {V : Type} (f : Sat3 V) : Is3Colorable (ReductionGraph f) → IsSatisfiable f
- Source
- TCSlib, `SATtoColor.SATtoColorSoundness`
- Lean proof
- By CS 294-268 course staff (UC Berkeley, Spring 2026), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 UC Berkeley CS 294. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.SATtoColor.SATtoColorSoundness← SATtoColor.SATtoColorSoundness (TCSlib/Complexity/NPReductions/ThreeSATToColoring.lean:286): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- SATtoColor.SatisfiesSat3An assignment $\mathrm{assign}$ satisfies a 3-SAT instance $f$ if every clause in the list $f$ is satisfied by $\mathrm{assign}$,…
- SATtoColor.EdgeRelation$\mathrm{EdgeRelation}(f, u, v)$ defines the (undirected) adjacency structure of the reduction graph. The edges are: all pairs of distinct…
- SATtoColor.OutputVertexThe vertex set of the reduction graph is the inductive type $\mathrm{OutputVertex}(V)$ with three constructors:
•… - SATtoColor.IsSatisfiableA 3-SAT instance $f$ is satisfiable if there exists a Boolean assignment that satisfies it:…
- SATtoColor.LiteralA literal for switching-lemma formulas: a variable $\mathtt{var} : \mathrm{Fin}\,n$ with a negation flag $\mathtt{neg} : \mathrm{Bool}$…
- SATtoColor.Is3ColorableA simple graph $G$ on vertex type $V'$ is 3-colorable if there exists a proper graph coloring with colors $\mathrm{Fin}\,3$, i.e.\…
- SATtoColor.SatisfiesClauseUnder assignment $\mathrm{assign}$, a clause $c$ is satisfied if at least one of its three literals evaluates to
true:… - SATtoColor.SatisfiesLiteralGiven a Boolean assignment $\mathrm{assign} : V \to \mathrm{Bool}$, the function $\texttt{SATtoColor.SatisfiesLiteral}$ evaluates a…
- SATtoColor.ClauseA clause over a variable type $V$ is a structure bundling exactly three literals $\ell_1, \ell_2, \ell_3 : \mathrm{Literal}\,V$.…
- SATtoColor.ReductionGraphGiven a 3-SAT instance $f$ over variables $V$, the reduction graph $\mathrm{ReductionGraph}(f)$ is the
SimpleGraphon… - SATtoColor.Sat3A 3-SAT instance over variable type $V$ is defined as a list of clauses, i.e.\ $\mathrm{Sat3}(V) := \mathrm{List}(\mathrm{Clause}\,V)$.
- SATtoColor.SATtoColorCompletenessCompleteness of the 3-SAT to 3-coloring reduction. Let $f$ be a 3-SAT instance over a variable type $V$, that is, a list of clauses, each…
- Used by 1
- SATtoColor.SATtoColorReductionCorrectness of the 3-SAT to 3-coloring reduction. Let $f$ be a 3-SAT instance over a variable type $V$: a list of clauses, each clause an…
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.
set_option relaxedAutoImplicit false inset_option autoImplicit false in/-- Soundness of reduction from 3-SAT to 3-Coloring. -/lemma SATtoColor.SATtoColorSoundness {V : Type} (f : Sat3 V) : Is3Colorable (ReductionGraph f) → IsSatisfiable f := by intro ⟨⟨col, hcol⟩⟩ simp only [SimpleGraph.top_adj] at hcol have colNe : ∀ {u v : OutputVertex V}, u ≠ v → (EdgeRelation f u v ∨ EdgeRelation f v u) → col u ≠ col v := fun hne hedge => hcol ⟨hne, hedge⟩ have hP01 : col (.palette 0) ≠ col (.palette 1) := colNe (by simp) (Or.inl (by simp [EdgeRelation])) have hP02 : col (.palette 0) ≠ col (.palette 2) := colNe (by simp) (Or.inl (by simp [EdgeRelation])) have hP12 : col (.palette 1) ≠ col (.palette 2) := colNe (by simp) (Or.inl (by simp [EdgeRelation])) have hLB : ∀ l : Literal V, col (.literalNode l) ≠ col (.palette 0) := fun l => colNe (by simp) (Or.inr trivial) have hPN : ∀ x : V, col (.literalNode (.pos x)) ≠ col (.literalNode (.neg x)) := fun x => colNe (by simp) (Or.inl rfl) have hG5B : ∀ c' : Clause V, col (.clauseGadget c' 5) ≠ col (.palette 0) := fun c' => colNe (by simp) (Or.inl trivial) have hG5F : ∀ c' : Clause V, col (.clauseGadget c' 5) ≠ col (.palette 2) := fun c' => colNe (by simp) (Or.inl trivial) let assign := fun v : V => decide (col (.literalNode (.pos v)) = col (.palette 1)) have hLFT : ∀ l : Literal V, SatisfiesLiteral assign l = false → col (.literalNode l) ≠ col (.palette 1) := by intro l hl cases l with | pos v => simp only [SatisfiesLiteral] at hl exact of_decide_eq_false hl | neg v => simp only [SatisfiesLiteral] at hl have hav : col (.literalNode (.pos v)) = col (.palette 1) := by apply of_decide_eq_true cases h : assign v · exfalso; simp [h] at hl · exact h intro hcontra exact hPN v (hav.trans hcontra.symm) refine ⟨assign, ?_⟩ simp only [SatisfiesSat3, List.all_eq_true] intro c hcIn by_contra hFalse have hSatF : SatisfiesClause assign c = false := by cases h : SatisfiesClause assign c with | true => exact absurd h hFalse | false => rfl simp only [SatisfiesClause] at hSatF have hl1F : SatisfiesLiteral assign c.l1 = false := by cases h : SatisfiesLiteral assign c.l1 <;> simp_all have hl2F : SatisfiesLiteral assign c.l2 = false := by cases h : SatisfiesLiteral assign c.l2 <;> simp_all have hl3F : SatisfiesLiteral assign c.l3 = false := by cases h : SatisfiesLiteral assign c.l3 <;> simp_all have hL1neT := hLFT c.l1 hl1F have hL2neT := hLFT c.l2 hl2F have hL3neT := hLFT c.l3 hl3F have hG5T : col (.clauseGadget c 5) = col (.palette 1) := by apply Fin.ext have i0 := (col (.clauseGadget c 5)).isLt have i1 := (col (.palette 0)).isLt have i2 := (col (.palette 1)).isLt have i3 := (col (.palette 2)).isLt have h1 : (col (.clauseGadget c 5)).val ≠ (col (.palette 0)).val := fun h => hG5B c (Fin.ext h) have h2 : (col (.clauseGadget c 5)).val ≠ (col (.palette 2)).val := fun h => hG5F c (Fin.ext h) have h3 : (col (.palette 0)).val ≠ (col (.palette 1)).val := fun h => hP01 (Fin.ext h) have h4 : (col (.palette 0)).val ≠ (col (.palette 2)).val := fun h => hP02 (Fin.ext h) have h5 : (col (.palette 1)).val ≠ (col (.palette 2)).val := fun h => hP12 (Fin.ext h) omega have hG01 : col (.clauseGadget c 0) ≠ col (.clauseGadget c 1) := colNe (by simp) (Or.inl ⟨rfl, hcIn, Or.inl ⟨rfl, rfl⟩⟩) have hG02 : col (.clauseGadget c 0) ≠ col (.clauseGadget c 2) := colNe (by simp) (Or.inl ⟨rfl, hcIn, Or.inr (Or.inl ⟨rfl, rfl⟩)⟩) have hG12 : col (.clauseGadget c 1) ≠ col (.clauseGadget c 2) := colNe (by simp) (Or.inl ⟨rfl, hcIn, Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩))⟩) have hG23 : col (.clauseGadget c 2) ≠ col (.clauseGadget c 3) := colNe (by simp) (Or.inl ⟨rfl, hcIn, Or.inr (Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩)))⟩) have hG34 : col (.clauseGadget c 3) ≠ col (.clauseGadget c 4) := colNe (by simp) (Or.inl ⟨rfl, hcIn, Or.inr (Or.inr (Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩))))⟩) have hG35 : col (.clauseGadget c 3) ≠ col (.clauseGadget c 5) := colNe (by simp) (Or.inl ⟨rfl, hcIn, Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩)))))⟩) have hG45 : col (.clauseGadget c 4) ≠ col (.clauseGadget c 5) := colNe (by simp) (Or.inl ⟨rfl, hcIn, Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl ⟨rfl, rfl⟩))))))⟩) have hL1G0 : col (.literalNode c.l1) ≠ col (.clauseGadget c 0) := colNe (by simp) (Or.inl (by simp [EdgeRelation])) have hL2G1 : col (.literalNode c.l2) ≠ col (.clauseGadget c 1) := colNe (by simp) (Or.inl (by simp [EdgeRelation])) have hL3G4 : col (.literalNode c.l3) ≠ col (.clauseGadget c 4) := colNe (by simp) (Or.inl (by simp [EdgeRelation])) have vp0 := (col (.palette 0)).isLt; have vp1 := (col (.palette 1)).isLt have vp2 := (col (.palette 2)).isLt have vg0 := (col (.clauseGadget c 0)).isLt; have vg1 := (col (.clauseGadget c 1)).isLt have vg2 := (col (.clauseGadget c 2)).isLt; have vg3 := (col (.clauseGadget c 3)).isLt have vg4 := (col (.clauseGadget c 4)).isLt; have vg5 := (col (.clauseGadget c 5)).isLt have vl1 := (col (.literalNode c.l1)).isLt; have vl2 := (col (.literalNode c.l2)).isLt have vl3 := (col (.literalNode c.l3)).isLt have hp01 : (col (.palette 0)).val ≠ (col (.palette 1)).val := fun h => hP01 (Fin.ext h) have hp02 : (col (.palette 0)).val ≠ (col (.palette 2)).val := fun h => hP02 (Fin.ext h) have hp12 : (col (.palette 1)).val ≠ (col (.palette 2)).val := fun h => hP12 (Fin.ext h) have hl1b : (col (.literalNode c.l1)).val ≠ (col (.palette 0)).val := fun h => hLB c.l1 (Fin.ext h) have hl2b : (col (.literalNode c.l2)).val ≠ (col (.palette 0)).val := fun h => hLB c.l2 (Fin.ext h) have hl3b : (col (.literalNode c.l3)).val ≠ (col (.palette 0)).val := fun h => hLB c.l3 (Fin.ext h) have hl1t : (col (.literalNode c.l1)).val ≠ (col (.palette 1)).val := fun h => hL1neT (Fin.ext h) have hl2t : (col (.literalNode c.l2)).val ≠ (col (.palette 1)).val := fun h => hL2neT (Fin.ext h) have hl3t : (col (.literalNode c.l3)).val ≠ (col (.palette 1)).val := fun h => hL3neT (Fin.ext h) have hl1g0 : (col (.literalNode c.l1)).val ≠ (col (.clauseGadget c 0)).val := fun h => hL1G0 (Fin.ext h) have hl2g1 : (col (.literalNode c.l2)).val ≠ (col (.clauseGadget c 1)).val := fun h => hL2G1 (Fin.ext h) have hl3g4 : (col (.literalNode c.l3)).val ≠ (col (.clauseGadget c 4)).val := fun h => hL3G4 (Fin.ext h) have hg01 : (col (.clauseGadget c 0)).val ≠ (col (.clauseGadget c 1)).val := fun h => hG01 (Fin.ext h) have hg02 : (col (.clauseGadget c 0)).val ≠ (col (.clauseGadget c 2)).val := fun h => hG02 (Fin.ext h) have hg12 : (col (.clauseGadget c 1)).val ≠ (col (.clauseGadget c 2)).val := fun h => hG12 (Fin.ext h) have hg23 : (col (.clauseGadget c 2)).val ≠ (col (.clauseGadget c 3)).val := fun h => hG23 (Fin.ext h) have hg34 : (col (.clauseGadget c 3)).val ≠ (col (.clauseGadget c 4)).val := fun h => hG34 (Fin.ext h) have hg35 : (col (.clauseGadget c 3)).val ≠ (col (.clauseGadget c 5)).val := fun h => hG35 (Fin.ext h) have hg45 : (col (.clauseGadget c 4)).val ≠ (col (.clauseGadget c 5)).val := fun h => hG45 (Fin.ext h) have hg5t : (col (.clauseGadget c 5)).val = (col (.palette 1)).val := congrArg Fin.val hG5T omega