simple_graph_exists_maximal_indep_superset
In a finite graph every independent set is contained in a maximal independent set.
Statement
theorem simple_graph_exists_maximal_indep_superset {V : Type*} [Fintype V] [DecidableEq V] (H : SimpleGraph V) (Y : Finset V) (hY : H.IsIndepSet (Y : Set V)) : ∃ Z : Finset V, Y ⊆ Z ∧ Maximal (fun u : Finset V => H.IsIndepSet (u : Set V)) Z
- Source
- Standard; serves simple_graph_power_well_covered_not_ball_union_subset (arXiv:2610.09300 (On graphs whose powers are well-covered), proof of Lemma 2.7).
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_power_well_covered_not_ball_union_subsetLet G be a finite graph and d ≥ 1 with G^d well-covered. Then there are no vertices s, t, w with d_G(s, t) ≥ d + 1 and B_d(s) ∪ B_d(t) ⊆…
The proof, explained
In a finite graph, the collection $S$ of all independent sets containing $Y$ is finite and nonempty since $Y \in S$. We choose an element $Z \in S$ of maximum cardinality. If $Z'$ is any independent superset of $Z$, it also contains $Y$ and thus belongs to $S$, so by cardinality maximality $|Z'| \le |Z|$; combined with $Z \subseteq Z'$, this forces $Z = Z'$, showing that $Z$ is maximal.
The family $S$ of independent supersets of $Y$ is defined, and $Y \in S$.
We work classically and define $S$ to be the finite collection of all subsets of $V$ that contain $Y$ and are independent in $H$. Since $Y \subseteq Y$ and $Y$ is independent by hypothesis, $Y$ belongs to $S$, showing that $S$ is nonempty.
classical set S := (Finset.univ : Finset (Finset V)).filter (fun Z => Y ⊆ Z ∧ H.IsIndepSet (Z : Set V)) have hYS : Y ∈ S := by simp [S, hY]
There exists a set $Z \in S$ of maximum cardinality, which is an independent superset of $Y$.
Because $S$ is nonempty, `Finset.exists_max_image` yields an element $Z \in S$ maximizing `Finset.card`. Unfolding the definition of $S$ via `Finset.mem_filter`, `Finset.mem_univ`, and `true_and` unpacks the membership $Z \in S$ into $Y \subseteq Z$ and the fact that $Z$ is independent.
uses
Finset.exists_max_image,Finset.card,Finset.mem_filter,Finset.mem_univ,true_andobtain ⟨Z, hZS, hZmax⟩ := Finset.exists_max_image S Finset.card ⟨Y, hYS⟩ simp only [S, Finset.mem_filter, Finset.mem_univ, true_and] at hZS
Choosing $Z$ reduces the goal to showing that any independent superset $Z' \supseteq Z$ satisfies $Z' \subseteq Z$.
We provide $Z$ as the witness. We have already established that $Y \subseteq Z$ and that $Z$ is independent. By definition of `Maximal`, it remains to show that whenever $Z'$ is independent and $Z \subseteq Z'$, we have $Z' \subseteq Z$.
refine ⟨Z, hZS.1, hZS.2, fun Z' hZ' hsub => ?_⟩
Any independent superset $Z'$ of $Z$ belongs to $S$.
By transitivity of inclusion, $Y \subseteq Z$ and $Z \subseteq Z'$ imply $Y \subseteq Z'$. Since $Z'$ is also independent, it satisfies the membership condition for $S$ after simplifying with `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hZ'S : Z' ∈ S := by simp only [S, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hZS.1.trans hsub, hZ'⟩
$Z = Z'$, which implies $Z' \subseteq Z$ and completes the proof.
Since $Z' \in S$, the maximality of $Z$ in $S$ implies $|Z'| \le |Z|$. By `Finset.eq_of_subset_of_card_le`, the inclusion $Z \subseteq Z'$ combined with $|Z'| \le |Z|$ forces $Z = Z'$. Substituting this equality into $Z' \subseteq Z$ closes the goal.
uses
Finset.eq_of_subset_of_card_lehave := Finset.eq_of_subset_of_card_le hsub (hZmax Z' hZ'S) rw [this]
Finset.exists_max_image- In any nonempty finite set, a function into a linearly ordered type achieves a maximum at some element.
Finset.card- The cardinality (number of elements) of a finite set as a natural number.
Finset.mem_filter- An element belongs to the filtered set `Finset.filter p s` if and only if it belongs to `s` and satisfies predicate `p`.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and- The proposition `True ∧ p` is logically equivalent to `p`.
Finset.eq_of_subset_of_card_le- If finite sets satisfy `s ⊆ t` and `card t ≤ card s`, then `s = t`.
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_exists_maximal_indep_superset {V : Type*} [Fintype V] [DecidableEq V] (H : SimpleGraph V) (Y : Finset V) (hY : H.IsIndepSet (Y : Set V)) : ∃ Z : Finset V, Y ⊆ Z ∧ Maximal (fun u : Finset V => H.IsIndepSet (u : Set V)) Z := by classical set S := (Finset.univ : Finset (Finset V)).filter (fun Z => Y ⊆ Z ∧ H.IsIndepSet (Z : Set V)) have hYS : Y ∈ S := by simp [S, hY] obtain ⟨Z, hZS, hZmax⟩ := Finset.exists_max_image S Finset.card ⟨Y, hYS⟩ simp only [S, Finset.mem_filter, Finset.mem_univ, true_and] at hZS refine ⟨Z, hZS.1, hZS.2, fun Z' hZ' hsub => ?_⟩ have hZ'S : Z' ∈ S := by simp only [S, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hZS.1.trans hsub, hZ'⟩ have := Finset.eq_of_subset_of_card_le hsub (hZmax Z' hZ'S) rw [this]