simple_graph_is_well_covered_bot
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
- boxProd_completeGraph_all_powers_well_coveredLet G be a finite connected nontrivial graph, and let t be an integer with t > |V(G)|. If every positive power G^d (d ≥ 1) is…
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.
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$.
intro s t hs htAny 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}$.
uses
SimpleGraph.IsIndepSet,Set.Pairwise,Finset.subset_univhave 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)
$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.
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
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.
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]