AFTD Auto-Formalizing Theoretical Domains

clique_to_vertex_cover_equivalence

theoremverifiedformalization

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.

  1. 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ᶜ.

    lines 6–8

      constructor
      · rintro ⟨s, hs_card, hs_clique⟩
        refine ⟨sᶜ, ?_, ?_⟩
  2. 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.

    line 9

    uses Finset.card_compl

        · rw [Finset.card_compl, hs_card]
  3. 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.

    lines 10–11

    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
  4. 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.

    lines 12–13

      · rintro ⟨t, ht_card, ht_cover⟩
        refine ⟨tᶜ, ?_, ?_⟩
  5. 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.

    line 14

    uses Finset.card_compl, Nat.sub_sub_self

        · rw [Finset.card_compl, ht_card, Nat.sub_sub_self hk]
  6. 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.

    lines 15–17

    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

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