AFTD Auto-Formalizing Theoretical Domains

simple_graph_exists_maximal_indep_superset

theoremverified

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

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.

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

    lines 4–6

      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]
  2. 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.

    lines 7–8

    uses Finset.exists_max_image, Finset.card, Finset.mem_filter, Finset.mem_univ, true_and

      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
  3. 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$.

    line 9

      refine ⟨Z, hZS.1, hZS.2, fun Z' hZ' hsub => ?_⟩
  4. 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`.

    lines 10–12

    uses Finset.mem_filter, Finset.mem_univ, true_and

      have hZ'S : Z' ∈ S := by
        simp only [S, Finset.mem_filter, Finset.mem_univ, true_and]
        exact ⟨hZS.1.trans hsub, hZ'⟩
  5. $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.

    lines 13–14

    uses Finset.eq_of_subset_of_card_le

      have := 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

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