AFTD Auto-Formalizing Theoretical Domains

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.
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)$.
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 SimpleGraph on…

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