clique_to_vertex_cover_equivalence
Let 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 a vertex cover of size |V| - k.
Statement
theorem clique_to_vertex_cover_equivalence {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k : ℕ) (hk : k ≤ Fintype.card V) : ThreeSATToClique.hasClique G k ↔ ∃ s : Finset V, s.card = Fintype.card V - k ∧ Gᶜ.IsVertexCover (s : Set V)
- Formalizes
- Karp (1972), 'Reducibility among combinatorial problems', Theorem 2; Gallai (1959)
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- ThreeSATToClique.hasCliqueA 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…
Read back from the Lean
For any finite type V with decidable equality, any simple graph G on V, and any natural number k satisfying k ≤ Fintype.card V, ThreeSATToClique.hasClique G k holds if and only if there exists a finite subset s of V (s : Finset V) such that:
1. s.card = Fintype.card V - k, and
2. The coercion (s : Set V) is a vertex cover of the complement graph Gᶜ (Gᶜ.IsVertexCover (s : Set V)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The equivalence between a clique of size k in G and a vertex cover of size |V| - k in Gᶜ relies on taking the complement of the vertex set. A set s is a clique in G if and only if it is an independent set in Gᶜ, which holds if and only if its complement sᶜ is a vertex cover in Gᶜ. The cardinalities match because |sᶜ| = |V| - |s| for any subset of the finite vertex set V.
To prove the forward implication, take a clique s of size k in G and consider its complement sᶜ as a candidate vertex cover in Gᶜ.
We split the bi-implication into forward and reverse directions (`constructor`). Assuming G has a clique s of size k (`rintro`), we propose its complement sᶜ as the witness for the vertex cover in Gᶜ (`refine`), leaving two goals: showing that |sᶜ| = |V| - k and that sᶜ is a vertex cover of Gᶜ.
constructor · rintro ⟨s, hs_card, hs_clique⟩ refine ⟨sᶜ, ?_, ?_⟩
The complement sᶜ has size |V| - k.
By `Finset.card_compl`, the cardinality of sᶜ is |V| - |s|. Since |s| = k, this rewrites directly to |V| - k.
uses
Finset.card_compl· rw [Finset.card_compl, hs_card]The complement sᶜ is a vertex cover of Gᶜ.
By `Finset.coe_compl`, the coerced complement is the set-theoretic complement. A set sᶜ is a vertex cover in Gᶜ if and only if s is an independent set in Gᶜ (`SimpleGraph.isVertexCover_compl`), which is equivalent to s being a clique in (Gᶜ)ᶜ (`SimpleGraph.isClique_compl`). Since (Gᶜ)ᶜ = G (`compl_compl`), this reduces to s being a clique in G, which holds by the clique hypothesis on s.
uses
Finset.coe_compl,SimpleGraph.isVertexCover_compl,SimpleGraph.isClique_compl,compl_compl· rw [Finset.coe_compl, SimpleGraph.isVertexCover_compl, ← SimpleGraph.isClique_compl, compl_compl] exact hs_clique
To prove the reverse implication, take a vertex cover t of size |V| - k in Gᶜ and consider its complement tᶜ as a candidate clique in G.
Assuming Gᶜ has a vertex cover t of size |V| - k (`rintro`), we propose its complement tᶜ as the witness for a clique in G (`refine`), leaving two goals: showing that |tᶜ| = k and that tᶜ is a clique in G.
· rintro ⟨t, ht_card, ht_cover⟩ refine ⟨tᶜ, ?_, ?_⟩The complement tᶜ has size k.
By `Finset.card_compl`, the cardinality of tᶜ is |V| - |t| = |V| - (|V| - k). Since k ≤ |V| by hypothesis hk, `Nat.sub_sub_self` simplifies this to k.
uses
Finset.card_compl,Nat.sub_sub_self· rw [Finset.card_compl, ht_card, Nat.sub_sub_self hk]The complement tᶜ is a clique in G.
We rewrite the hypothesis that t is a vertex cover in Gᶜ: expressing t as (tᶜ)ᶜ (`compl_compl`), it is a vertex cover of Gᶜ if and only if tᶜ is an independent set in Gᶜ (`SimpleGraph.isVertexCover_compl`), which is equivalent to tᶜ being a clique in (Gᶜ)ᶜ = G (`SimpleGraph.isClique_compl`). The rewritten hypothesis then directly establishes that tᶜ is a clique in G.
uses
compl_compl,Finset.coe_compl,SimpleGraph.isVertexCover_compl,SimpleGraph.isClique_compl· rw [← compl_compl t, Finset.coe_compl, SimpleGraph.isVertexCover_compl, ← SimpleGraph.isClique_compl, compl_compl] at ht_cover exact ht_cover
Finset.card_compl- In a finite type α, the cardinality of the complement of a finset s is |α| - |s|.
Finset.coe_compl- The coercion of the complement of a finset to a set equals the complement of the coerced set.
SimpleGraph.isVertexCover_compl- The complement cᶜ is a vertex cover of a graph G if and only if c is an independent set in G.
SimpleGraph.isClique_compl- A set s is a clique in the complement graph Gᶜ if and only if s is an independent set in G.
compl_compl- The double complement of an element in a Boolean algebra is the element itself (xᶜᶜ = x).
Nat.sub_sub_self- For natural numbers m ≤ n, n - (n - m) = m.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- A graph G has a clique of size k if and only if its complement graph Gᶜ has a vertex cover of size |V| - k. -/theorem clique_to_vertex_cover_equivalence {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (k : ℕ) (hk : k ≤ Fintype.card V) : ThreeSATToClique.hasClique G k ↔ ∃ s : Finset V, s.card = Fintype.card V - k ∧ Gᶜ.IsVertexCover (s : Set V) := by constructor · rintro ⟨s, hs_card, hs_clique⟩ refine ⟨sᶜ, ?_, ?_⟩ · rw [Finset.card_compl, hs_card] · rw [Finset.coe_compl, SimpleGraph.isVertexCover_compl, ← SimpleGraph.isClique_compl, compl_compl] exact hs_clique · rintro ⟨t, ht_card, ht_cover⟩ refine ⟨tᶜ, ?_, ?_⟩ · rw [Finset.card_compl, ht_card, Nat.sub_sub_self hk] · rw [← compl_compl t, Finset.coe_compl, SimpleGraph.isVertexCover_compl, ← SimpleGraph.isClique_compl, compl_compl] at ht_cover exact ht_cover