AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_on_subset

theoremverified

For any finite digraph and any finite vertex subset S there is an independent Q contained in S such that every vertex of S is reachable from Q in at most two arcs using intermediate vertices in S.

Statement

theorem digraph_quasikernel_on_subset
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (S : Finset α) :
    ∃ Q : Finset α, Q ⊆ S ∧
      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧
      (∀ v ∈ S, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w ∈ S, D.Adj u w ∧ D.Adj w v)
Source
Standard qualitative quasi-kernel existence construction, recalled in arXiv:2601.11847 Section 1.1; foundational helper for OP-337.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 4

The proof, explained

The theorem is proven by strong induction on the finite set of vertices S (Chvátal's quasi-kernel theorem). If S is empty, the empty set is trivially a quasi-kernel. When S is nonempty, we select an arbitrary vertex v ∈ S and consider the strict subset T ⊂ S of vertices that are neither v nor out-neighbors of v, which admits a quasi-kernel Q by induction. If some vertex in Q points to v, then Q already 2-covers all of S; otherwise, no arcs go between v and Q, so Q ∪ {v} is an independent set that 2-covers all of S.

  1. We set up strong induction on the finite vertex set S.

    We permit classical logic and perform strong induction on S ordered by strict subset inclusion using Finset.strongInduction. The induction hypothesis ih states that the theorem holds for all strict subsets T ⊂ S.

    lines 7–9

    uses Finset.strongInduction

      classical
      induction S using Finset.strongInduction with
      | _ S ih =>
  2. If S is empty, the empty set is a valid quasi-kernel.

    When S = ∅, we choose Q = ∅. The empty set is trivially a subset of S, independence holds vacuously, and the covering condition holds vacuously since S has no elements.

    lines 10–12

        by_cases he : S = ∅
        · subst S
          refine ⟨∅, ?_, ?_, ?_⟩ <;> simp
  3. If S is nonempty, we pick a vertex v ∈ S and define a strict subset T ⊂ S of vertices that are neither v nor out-neighbors of v.

    Since S ≠ ∅, there exists an element v ∈ S by Finset.nonempty_iff_ne_empty.mpr. We let T be the set of elements w ∈ S such that w ≠ v and v has no arc to w, which is a subset of S by Finset.filter_subset. By construction, v ∉ T because v ≠ v is false (Finset.mem_filter.mp), which implies T ≠ S and therefore T ⊂ S is a strict subset by Finset.ssubset_iff_subset_ne.mpr.

    lines 13–21

    uses Finset.nonempty_iff_ne_empty.mpr, Finset.filter_subset, Finset.ssubset_iff_subset_ne.mpr, Finset.mem_filter.mp

        · obtain ⟨v,hv⟩ := Finset.nonempty_iff_ne_empty.mpr he
          let T := S.filter (fun w => w ≠ v ∧ ¬ D.Adj v w)
          have hTS : T ⊆ S := Finset.filter_subset _ _
          have hT : T ⊂ S := by
            apply Finset.ssubset_iff_subset_ne.mpr
            refine ⟨hTS, ?_⟩
            intro eq
            have hvT : v ∈ T := by rw [eq]; exact hv
            exact ((Finset.mem_filter.mp hvT).2.1) rfl
  4. By the induction hypothesis, T has a quasi-kernel Q, and no element of Q is equal to v or receives an arc from v.

    Applying the induction hypothesis to T ⊂ S yields an independent set Q ⊆ T that 2-covers T. Since Q ⊆ T, every u ∈ Q inherits the property that u ≠ v and ¬ D.Adj v u from the definition of T via Finset.mem_filter.mp.

    lines 22–25

    uses Finset.mem_filter.mp

          obtain ⟨Q,hQT,hind,hcover⟩ := ih T hT
          have hqprop : ∀ u ∈ Q, u ≠ v ∧ ¬ D.Adj v u := by
            intro u hu
            exact (Finset.mem_filter.mp (hQT hu)).2
  5. Every vertex in T is reachable from Q in at most two steps using vertices in S.

    By the induction hypothesis, every x ∈ T is covered from Q in at most two steps with intermediate vertices in T (using Or.inl and Or.inr). Since T ⊆ S, any intermediate vertex in T also belongs to S.

    lines 26–34

    uses Or.inl, Or.inr

          have coverT : ∀ x ∈ T, ∃ u ∈ Q,
              u = x ∨ D.Adj u x ∨ ∃ w ∈ S, D.Adj u w ∧ D.Adj w x := by
            intro x hx
            obtain ⟨u,hu,h⟩ := hcover x hx
            refine ⟨u,hu,?_⟩
            rcases h with heq | hsingle | ⟨w,hw,huw,hwx⟩
            · exact Or.inl heq
            · exact Or.inr (Or.inl hsingle)
            · exact Or.inr (Or.inr ⟨w,hTS hw,huw,hwx⟩)
  6. Every vertex in S \ T is either v or an out-neighbor of v.

    Let x ∈ S with x ∉ T. If x = v, the claim holds by Or.inl. If x ≠ v, then v must be adjacent to x; otherwise, x would satisfy all conditions to belong to T by Finset.mem_filter.mpr, contradicting x ∉ T.

    lines 35–41

    uses Or.inl, Finset.mem_filter.mpr

          have outside : ∀ x ∈ S, x ∉ T → x = v ∨ D.Adj v x := by
            intro x hxS hxT
            by_cases hxv : x = v
            · exact Or.inl hxv
            · right
              by_contra hn
              exact hxT (Finset.mem_filter.mpr ⟨hxS,hxv,hn⟩)
  7. Case 1: If some vertex in Q has an arc to v, then Q is a quasi-kernel for all of S.

    Suppose there is some u ∈ Q with D.Adj u v. The set Q is independent and a subset of S. Every x ∈ T is 2-covered by Q. For any x ∈ S \ T, either x = v, which is covered in one step by u → v using Or.inl and Or.inr, or D.Adj v x, which is covered in two steps by u → v → x with intermediate vertex v ∈ S using Or.inr.

    lines 42–50

    uses Or.inl, Or.inr

          by_cases hex : ∃ u ∈ Q, D.Adj u v
          · refine ⟨Q,hQT.trans hTS,hind,?_⟩
            intro x hxS
            by_cases hxT : x ∈ T
            · exact coverT x hxT
            · obtain ⟨u,hu,huv⟩ := hex
              rcases outside x hxS hxT with hxv | hvx
              · subst x; exact ⟨u,hu,Or.inr (Or.inl huv)⟩
              · exact ⟨u,hu,Or.inr (Or.inr ⟨v,hv,huv,hvx⟩)⟩
  8. Case 2: If no vertex in Q has an arc to v, then Q ∪ {v} is an independent subset of S.

    We consider insert v Q. Since v ∈ S and Q ⊆ S, insert v Q ⊆ S by Finset.insert_subset. For independence, let a, b ∈ insert v Q with a ≠ b. Using Finset.mem_insert.mp, if a = v then b ∈ Q, so v → b does not hold by definition of T; if b = v then a ∈ Q, so a → v does not hold by the case assumption; and if a, b ∈ Q, independence holds from Q being independent.

    lines 51–61

    uses Finset.insert_subset, Finset.mem_insert.mp

          · refine ⟨insert v Q, ?_, ?_, ?_⟩
            · exact Finset.insert_subset hv (hQT.trans hTS)
            · intro a ha b hb hab
              rcases Finset.mem_insert.mp ha with haV | haQ
              · subst a
                rcases Finset.mem_insert.mp hb with hbV | hbQ
                · subst b; exact (hab rfl).elim
                · exact (hqprop b hbQ).2
              · rcases Finset.mem_insert.mp hb with hbV | hbQ
                · subst b; intro hav; exact hex ⟨a,haQ,hav⟩
                · exact hind a haQ b hbQ hab
  9. The set Q ∪ {v} 2-covers all vertices of S, completing the proof.

    For any x ∈ S, if x ∈ T, it is 2-covered by some u ∈ Q, and u ∈ insert v Q by Finset.mem_insert_of_mem. If x ∈ S \ T, then either x = v, which is in insert v Q (Finset.mem_insert_self and Or.inl), or v → x, so x is reached in one step from v ∈ insert v Q (Finset.mem_insert_self, Or.inr, and Or.inl).

    lines 62–68

    uses Finset.mem_insert_of_mem, Finset.mem_insert_self, Or.inl, Or.inr

            · intro x hxS
              by_cases hxT : x ∈ T
              · obtain ⟨u,hu,h⟩ := coverT x hxT
                exact ⟨u,Finset.mem_insert_of_mem hu,h⟩
              · rcases outside x hxS hxT with hxv | hvx
                · subst x; exact ⟨v,Finset.mem_insert_self _ _,Or.inl rfl⟩
                · exact ⟨v,Finset.mem_insert_self _ _,Or.inr (Or.inl hvx)⟩
Finset.strongInduction
Strong induction on finite sets: a property holds for all finite sets if it holds for any set whenever it holds for all its strict subsets.
Finset.nonempty_iff_ne_empty.mpr
A finite set is nonempty if and only if it is not equal to the empty set; this direction produces an element from the assumption that the set is non-empty.
Finset.filter_subset
Filtering a finite set by a predicate produces a subset of the original set.
Finset.ssubset_iff_subset_ne.mpr
A set is a strict subset of another if it is a subset and not equal to it.
Finset.mem_filter.mp
An element belongs to a filtered set only if it belongs to the original set and satisfies the filtering predicate.
Finset.mem_filter.mpr
An element belongs to a filtered set if it belongs to the original set and satisfies the filtering predicate.
Or.inl
The left injection into a disjunction: if A holds, then A ∨ B holds.
Or.inr
The right injection into a disjunction: if B holds, then A ∨ B holds.
Finset.insert_subset
Inserting an element into a set yields a subset of a target set, provided the element and the original set are both contained in the target set.
Finset.mem_insert.mp
An element belongs to insert a s only if it equals a or belongs to s.
Finset.mem_insert_of_mem
If an element belongs to s, it belongs to insert a s.
Finset.mem_insert_self
An element always belongs to the set formed by inserting it into any 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 digraph_quasikernel_on_subset    {α : Type} [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] (S : Finset α) :    ∃ Q : Finset α, Q ⊆ S ∧      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧      (∀ v ∈ S, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w ∈ S, D.Adj u w ∧ D.Adj w v) := by  classical  induction S using Finset.strongInduction with  | _ S ih =>    by_cases he : S = ∅    · subst S      refine ⟨∅, ?_, ?_, ?_⟩ <;> simp    · obtain ⟨v,hv⟩ := Finset.nonempty_iff_ne_empty.mpr he      let T := S.filter (fun w => w ≠ v ∧ ¬ D.Adj v w)      have hTS : T ⊆ S := Finset.filter_subset _ _      have hT : T ⊂ S := by        apply Finset.ssubset_iff_subset_ne.mpr        refine ⟨hTS, ?_⟩        intro eq        have hvT : v ∈ T := by rw [eq]; exact hv        exact ((Finset.mem_filter.mp hvT).2.1) rfl      obtain ⟨Q,hQT,hind,hcover⟩ := ih T hT      have hqprop : ∀ u ∈ Q, u ≠ v ∧ ¬ D.Adj v u := by        intro u hu        exact (Finset.mem_filter.mp (hQT hu)).2      have coverT : ∀ x ∈ T, ∃ u ∈ Q,          u = x ∨ D.Adj u x ∨ ∃ w ∈ S, D.Adj u w ∧ D.Adj w x := by        intro x hx        obtain ⟨u,hu,h⟩ := hcover x hx        refine ⟨u,hu,?_⟩        rcases h with heq | hsingle | ⟨w,hw,huw,hwx⟩        · exact Or.inl heq        · exact Or.inr (Or.inl hsingle)        · exact Or.inr (Or.inr ⟨w,hTS hw,huw,hwx⟩)      have outside : ∀ x ∈ S, x ∉ T → x = v ∨ D.Adj v x := by        intro x hxS hxT        by_cases hxv : x = v        · exact Or.inl hxv        · right          by_contra hn          exact hxT (Finset.mem_filter.mpr ⟨hxS,hxv,hn⟩)      by_cases hex : ∃ u ∈ Q, D.Adj u v      · refine ⟨Q,hQT.trans hTS,hind,?_⟩        intro x hxS        by_cases hxT : x ∈ T        · exact coverT x hxT        · obtain ⟨u,hu,huv⟩ := hex          rcases outside x hxS hxT with hxv | hvx          · subst x; exact ⟨u,hu,Or.inr (Or.inl huv)⟩          · exact ⟨u,hu,Or.inr (Or.inr ⟨v,hv,huv,hvx⟩)⟩      · refine ⟨insert v Q, ?_, ?_, ?_⟩        · exact Finset.insert_subset hv (hQT.trans hTS)        · intro a ha b hb hab          rcases Finset.mem_insert.mp ha with haV | haQ          · subst a            rcases Finset.mem_insert.mp hb with hbV | hbQ            · subst b; exact (hab rfl).elim            · exact (hqprop b hbQ).2          · rcases Finset.mem_insert.mp hb with hbV | hbQ            · subst b; intro hav; exact hex ⟨a,haQ,hav⟩            · exact hind a haQ b hbQ hab        · intro x hxS          by_cases hxT : x ∈ T          · obtain ⟨u,hu,h⟩ := coverT x hxT            exact ⟨u,Finset.mem_insert_of_mem hu,h⟩          · rcases outside x hxS hxT with hxv | hvx            · subst x; exact ⟨v,Finset.mem_insert_self _ _,Or.inl rfl⟩            · exact ⟨v,Finset.mem_insert_self _ _,Or.inr (Or.inl hvx)⟩
See it in the graphDiscuss this resultChallenge it