AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_well_covered_bot

theoremverified

The edgeless graph on a finite vertex set is well-covered (its only maximal independent set is the whole vertex set).

Statement

theorem simple_graph_is_well_covered_bot {V : Type*} [Fintype V] :
    simple_graph_is_well_covered (⊥ : SimpleGraph V)
Source
Sanity lemma for simple_graph_is_well_covered (arXiv:2610.09300 (On graphs whose powers are well-covered)).
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_is_well_coveredA finite graph is well-covered if all its maximal independent sets have the same cardinality (equivalently, all its minimal vertex covers…
Used by 1

The proof, explained

To show that the edgeless graph is well-covered, the proof shows that its only maximal independent set is the entire vertex set. In an edgeless graph, there are no edges, so the whole vertex set is trivially independent. Any maximal independent set is contained in the whole vertex set and therefore must equal it by maximality. Thus, all maximal independent sets are equal to the entire vertex set, and in particular have the same cardinality.

  1. It suffices to show that any two maximal independent sets $s$ and $t$ of the edgeless graph have the same cardinality ($|s| = |t|$).

    By definition, a graph is well-covered if all its maximal independent sets have the same cardinality. We introduce two arbitrary maximal independent sets $s$ and $t$ with maximality hypotheses $hs$ and $ht$.

    line 3

      intro s t hs ht
  2. Any maximal independent set $u$ of the edgeless graph is the universal set ($u = \mathrm{univ}$).

    In the edgeless graph $\bot$, no edges exist between any pair of vertices, so the universal set $\mathrm{univ}$ is vacuously an independent set. Since every subset is contained in the universal set by `Finset.subset_univ`, the maximality of $u$ forces $u = \mathrm{univ}$.

    lines 4–7

    uses SimpleGraph.IsIndepSet, Set.Pairwise, Finset.subset_univ

      have key : ∀ u : Finset V, Maximal (fun u : Finset V => (⊥ : SimpleGraph V).IsIndepSet (u : Set V)) u →
          u = Finset.univ := by
        intro u hu
        exact hu.eq_of_le (by simp [SimpleGraph.IsIndepSet, Set.Pairwise]) (Finset.subset_univ u)
  3. $s$ and $t$ have the same cardinality ($|s| = |t|$).

    Applying the key lemma to both $s$ and $t$ shows that $s = \mathrm{univ}$ and $t = \mathrm{univ}$. Rewriting both sides transforms $|s| = |t|$ into $|\mathrm{univ}| = |\mathrm{univ}|$, which holds trivially.

    line 8

      rw [key s hs, key t ht]
Finset.subset_univ
Every finite set in a finite type is a subset of the universal set of all elements.
SimpleGraph.IsIndepSet
A set of vertices is an independent set in a graph if no two distinct vertices in the set are adjacent.
Set.Pairwise
A binary relation holds pairwise on a set if it holds between every pair of distinct elements in the set.

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

theorem simple_graph_is_well_covered_bot {V : Type*} [Fintype V] :    simple_graph_is_well_covered (⊥ : SimpleGraph V) := by  intro s t hs ht  have key : ∀ u : Finset V, Maximal (fun u : Finset V => (⊥ : SimpleGraph V).IsIndepSet (u : Set V)) u →      u = Finset.univ := by    intro u hu    exact hu.eq_of_le (by simp [SimpleGraph.IsIndepSet, Set.Pairwise]) (Finset.subset_univ u)  rw [key s hs, key t ht]
See it in the graphDiscuss this resultChallenge it