SATtoColor.EdgeRelation
defimported Lean
$\mathrm{EdgeRelation}(f, u, v)$ defines the (undirected) adjacency structure of the reduction graph. The edges are: all pairs of distinct palette nodes; every literal node to the Base palette node; $\mathrm{pos}(x)$ to $\mathrm{neg}(x)$ for each variable $x$; specific pairs of clause gadget nodes within the same clause (encoding two internal triangles on nodes $\{0,1,2\}$ and $\{3,4,5\}$ plus the bridge $2$--$3$); each clause's three literal nodes to gadget nodes $0$, $1$, and $4$ respectively; and gadget node $5$ of every clause to both the Base and the False palette nodes.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in def SATtoColor.EdgeRelation {V : Type} (clauses : Sat3 V) (u v: OutputVertex V) : Prop
- Defined in
- TCSlib, `SATtoColor.EdgeRelation`
- 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.EdgeRelation← SATtoColor.EdgeRelation (TCSlib/Complexity/NPReductions/ThreeSATToColoring.lean:132): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 4
- SATtoColor.OutputVertexThe vertex set of the reduction graph is the inductive type $\mathrm{OutputVertex}(V)$ with three constructors:
•… - SATtoColor.LiteralA literal for switching-lemma formulas: a variable $\mathtt{var} : \mathrm{Fin}\,n$ with a negation flag $\mathtt{neg} : \mathrm{Bool}$…
- 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.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.OutputVertexThe vertex set of the reduction graph is the inductive type $\mathrm{OutputVertex}(V)$ with three constructors:
- Used by 3
- SATtoColor.SATtoColorSoundnessSoundness 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…
- 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…
- SATtoColor.ReductionGraphGiven a 3-SAT instance $f$ over variables $V$, the reduction graph $\mathrm{ReductionGraph}(f)$ is the
SimpleGraphon…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in /-- Edge relation for reduction from 3-SAT to 3-COLORING. -/ def SATtoColor.EdgeRelation {V : Type} (clauses : Sat3 V) (u v: OutputVertex V) : Prop := match u, v with | .palette i, .palette j => i ≠ j | .palette 0, .literalNode _ => True | .literalNode _, .palette 0 => True | .literalNode (.pos x), .literalNode (.neg y) => x = y | .literalNode (.neg x), .literalNode (.pos y) => x = y | .clauseGadget c1 i, .clauseGadget c2 j => c1 = c2 ∧ c1 ∈ clauses ∧ ( (i = 0 ∧ j = 1) ∨ (i = 0 ∧ j = 2) ∨ (i = 1 ∧ j = 2) ∨ (i = 2 ∧ j = 3) ∨ (i = 3 ∧ j = 4) ∨ (i = 3 ∧ j = 5) ∨ (i = 4 ∧ j = 5) ∨ (i = 1 ∧ j = 0) ∨ (i = 2 ∧ j = 0) ∨ (i = 2 ∧ j = 1) ∨ (i = 3 ∧ j = 2) ∨ (i = 4 ∧ j = 3) ∨ (i = 5 ∧ j = 3) ∨ (i = 5 ∧ j = 4) ) | .literalNode z, .clauseGadget c i => ((z = c.l1 ∧ i = 0) ∨ (z = c.l2 ∧ i = 1) ∨ (z = c.l3 ∧ i = 4)) | .clauseGadget c i, .literalNode z => ((z = c.l1 ∧ i = 0) ∨ (z = c.l2 ∧ i = 1) ∨ (z = c.l3 ∧ i = 4)) | .clauseGadget _ 5, .palette 0 => True | .palette 0, .clauseGadget _ 5 => True | .clauseGadget _ 5, .palette 2 => True | .palette 2, .clauseGadget _ 5 => True | _, _ => False