AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_well_covered

def

A finite graph is well-covered if all its maximal independent sets have the same cardinality (equivalently, all its minimal vertex covers have the same cardinality, since I is a maximal independent set iff V ∖ I is a minimal vertex cover).

Statement

def simple_graph_is_well_covered {V : Type*} [Fintype V] (G : SimpleGraph V) : Prop
Defined in
arXiv:2610.09300 (On graphs whose powers are well-covered), Sec. 2 (well-covered: all minimal vertex covers have the same size; the paper notes the equivalence with maximal independent sets used here).
Verified
11 Oct 2026
Axioms
none listed
Used by 28

Lean source view module on GitHub

def simple_graph_is_well_covered {V : Type*} [Fintype V] (G : SimpleGraph V) : Prop :=
  ∀ s t : Finset V, Maximal (fun u : Finset V => G.IsIndepSet (u : Set V)) s →
    Maximal (fun u : Finset V => G.IsIndepSet (u : Set V)) t → s.card = t.card
See it in the graphDiscuss this resultChallenge it