ThreeSATToClique.hasClique
defimported Lean
A graph $G$ on vertex type $V$ has a $k$-clique if there exists a finite set $s \subseteq V$ of $k$ vertices that are pairwise adjacent in $G$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in def ThreeSATToClique.hasClique {V : Type} (G : SimpleGraph V) (k : Nat) : Prop
- Defined in
- TCSlib, `ThreeSATToClique.hasClique`
- 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.ThreeSATToClique.hasClique← ThreeSATToClique.hasClique (TCSlib/Complexity/NPReductions/ThreeSATToClique.lean:165): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 4
- ThreeSATToClique.ThreeSAT_to_Clique_soundnessSoundness of the 3-SAT to clique reduction. Let $f$ be a 3-CNF formula consisting of $m$ clauses. If the conflict graph of $f$ has an…
- ThreeSATToClique.ThreeSAT_to_Clique_equivalenceCorrectness 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…
- clique_to_vertex_cover_equivalenceLet G be a finite simple graph on vertex type V and let k ≤ |V|. Then G has a clique of size k if and only if the complement graph Gᶜ has…
- ThreeSATToClique.ThreeSAT_to_Clique_completenessCompleteness of the 3-SAT to clique reduction. Let $f$ be a 3-CNF formula consisting of $m$ clauses, and let its conflict graph be the…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in /-- A graph `G` has a **`k`-clique** if there exists a set of `k` pairwise adjacent vertices. -/ def ThreeSATToClique.hasClique {V : Type} (G : SimpleGraph V) (k : Nat) : Prop := ∃ (s : Finset V), s.card = k ∧ G.IsClique s -- ============================================================= -- Section 4. Auxiliary lemmas -- =============================================================