AFTD Auto-Formalizing Theoretical Domains

ThreeSATToClique.ThreeSAT_to_Clique_equivalence

theoremverifiedformalizationimported Lean

Correctness of the 3-SAT to Clique reduction. Let $f$ be a 3-CNF formula with $m$ clauses. Then $f$ is satisfiable if and only if its conflict graph has a clique of size $m$; that is, the graph whose vertices are the literal positions of $f$, with two positions adjacent exactly when they lie in different clauses and their literals do not conflict, contains $m$ pairwise-adjacent vertices precisely when some truth assignment satisfies every clause of $f$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
theorem ThreeSATToClique.ThreeSAT_to_Clique_equivalence {V : Type} (f : Formula3 V) :
    is3Satisfiable f ↔ hasClique (toCliqueGraph f) f.length
Formalizes
Correctness of the 3-SAT to Clique reduction, as formalized in TCSlib (`ThreeSATToClique.ThreeSAT_to_Clique_equivalence`)
Lean proof
By Yangshuo Zou, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Yangshuo Zou. 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
Classical.choiceQuot.soundpropext
Built on 8

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
/-- **Equivalence**: a 3-CNF formula is satisfiable if and only if its conflict graph contains a clique of size equal to the number of clauses. -/
theorem ThreeSATToClique.ThreeSAT_to_Clique_equivalence {V : Type} (f : Formula3 V) :
    is3Satisfiable f ↔ hasClique (toCliqueGraph f) f.length :=
  ⟨ThreeSAT_to_Clique_completeness f, ThreeSAT_to_Clique_soundness f⟩
See it in the graphDiscuss this resultChallenge it