AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_covers_independent_set

theoremverified

For any finite directed graph and any independent vertex set I, there is a quasi-kernel whose closed out-neighborhood contains I.

Statement

theorem digraph_quasikernel_covers_independent_set {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (I : Finset α)
    (hind : ∀ u ∈ I, ∀ v ∈ I, u ≠ v → ¬ D.Adj u v) :
    ∃ Q : Finset α,
      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧
      (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) ∧
      (∀ i ∈ I, ∃ q ∈ Q, q = i ∨ D.Adj q i)
Source
Special case of Lemma 14, https://www.combinatorics.org/ojs/index.php/eljc/article/download/v32i2p53/pdf/, with arcs reversed. Related independent-set recursion: https://arxiv.org/html/2610.29659, Section 2.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • digraph_quasikernel_on_subsetFor 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…

The proof, explained

To find a quasi-kernel covering an independent set I within distance at most 1, we isolate the set T of vertices outside I that receive no directed edges from I, and choose a quasi-kernel Q ⊆ T on T. We then define R ⊆ I to be the vertices of I not dominated by Q, and propose P = Q ∪ R as the desired quasi-kernel. The set P is independent because no edges can run between Q and R by the definitions of R and T. Finally, every vertex in T is reached by Q within two steps, while every vertex outside T either lies in I or is an out-neighbor of I, both of which are reached from P within two steps because P covers I in at most one step.

  1. Define the candidate quasi-kernel P = Q ∪ R, where Q is a quasi-kernel on the subset T of vertices outside I with no incoming edges from I, and R ⊆ I consists of the vertices of I not dominated by Q.

    Let T be the set of vertices x ∉ I such that no vertex of I has a directed edge to x. By digraph_quasikernel_on_subset, T contains a quasi-kernel Q ⊆ T (an independent subset reaching every vertex of T within two steps). Let R ⊆ I be the subset of vertices of I that receive no directed edges from any vertex in Q. We define our candidate set P as Q ∪ R.

    lines 8–12

    uses digraph_quasikernel_on_subset

      classical
      let T := Finset.univ.filter fun x => x ∉ I ∧ ¬ ∃ i ∈ I, D.Adj i x
      obtain ⟨Q,hQT,hQind,hQcov⟩ := digraph_quasikernel_on_subset D T
      let R := I.filter fun i => ¬ ∃ q ∈ Q, D.Adj q i
      let P := Q ∪ R
  2. Every vertex in I is either in P or has an in-neighbor in P.

    For any i ∈ I, we consider whether some vertex in Q points to i. If there is some q ∈ Q with an edge q → i, then q ∈ P (via Finset.mem_union_left) and dominates i. Otherwise, no vertex of Q points to i, which by definition means i ∈ R (via Finset.mem_filter.mpr), so i ∈ P (via Finset.mem_union_right) and covers itself. This establishes hypothesis hfirst.

    lines 13–19

    uses Finset.mem_union_left, Or.inr, Finset.mem_filter.mpr, Finset.mem_union_right, Or.inl

      have hfirst : ∀ i ∈ I, ∃ q ∈ P, q = i ∨ D.Adj q i := by
        intro i hi
        by_cases h : ∃ q ∈ Q, D.Adj q i
        · obtain ⟨q,hq,hqi⟩ := h
          exact ⟨q,Finset.mem_union_left _ hq,Or.inr hqi⟩
        · have hiR : i ∈ R := Finset.mem_filter.mpr ⟨hi,h⟩
          exact ⟨i,Finset.mem_union_right _ hiR,Or.inl rfl⟩
  3. It suffices to show that P is independent and that every vertex of the graph is reachable from P in at most two steps.

    We supply P as the existential witness. The condition that P covers I within distance at most 1 is discharged by hfirst, leaving two goals: the independence of P and the quasi-kernel covering property for all vertices in the graph.

    line 20

      refine ⟨P, ?_, ?_, hfirst⟩
  4. The set P is independent.

    Let a, b ∈ P with a ≠ b. Since P = Q ∪ R, we decompose membership into four cases using Finset.mem_union.mp: 1. a ∈ Q, b ∈ Q: no edge exists from a to b because Q is independent (hQind). 2. a ∈ Q, b ∈ R: an edge a → b would contradict the definition of R (Finset.mem_filter.mp), which excludes vertices having an in-neighbor in Q. 3. a ∈ R, b ∈ Q: since a ∈ R ⊆ I and b ∈ Q ⊆ T, an edge a → b contradicts the definition of T, whose elements receive no directed edges from I. 4. a ∈ R, b ∈ R: since R ⊆ I, no edge exists from a to b by the independence of I (hind). Thus no two distinct vertices in P are adjacent.

    lines 21–27

    uses Finset.mem_union.mp, Finset.mem_filter.mp

      · intro a ha b hb hab
        rcases Finset.mem_union.mp ha with ha | ha <;>
          rcases Finset.mem_union.mp hb with hb | hb
        · exact hQind a ha b hb hab
        · exact fun h => (Finset.mem_filter.mp hb).2 ⟨a,ha,h⟩
        · exact fun h => (Finset.mem_filter.mp (hQT hb)).2.2 ⟨a,(Finset.mem_filter.mp ha).1,h⟩
        · exact hind a (Finset.mem_filter.mp ha).1 b (Finset.mem_filter.mp hb).1 hab
  5. Every vertex in T is reachable from P in at most two steps.

    Let v be an arbitrary vertex. If v ∈ T, then because Q is a quasi-kernel of T (hQcov), there is some q ∈ Q such that q = v, or q → v, or q → w → v for some intermediate vertex w ∈ T. Since Q ⊆ P (by Finset.mem_union_left), this q ∈ P reaches v in at most two steps.

    lines 28–35

    uses Finset.mem_union_left, Or.inl, Or.inr

      · intro v
        by_cases hvT : v ∈ T
        · obtain ⟨q,hq,h⟩ := hQcov v hvT
          refine ⟨q,Finset.mem_union_left _ hq,?_⟩
          rcases h with h | h | ⟨w,_,h1,h2⟩
          · exact Or.inl h
          · exact Or.inr (Or.inl h)
          · exact Or.inr (Or.inr ⟨w,h1,h2⟩)
  6. Every vertex outside T either belongs to I or has an in-neighbor in I.

    By definition, T consists of all vertices in Finset.univ that do not belong to I and receive no directed edges from I. If a vertex v ∉ T were neither in I nor had an in-neighbor in I, it would satisfy the defining predicate of T (via Finset.mem_filter.mpr and Finset.mem_univ), a contradiction. Hence v must either belong to I or be the out-neighbor of some vertex i ∈ I.

    lines 36–43

    uses Finset.mem_filter.mpr, Finset.mem_univ

        · have houtside : v ∈ I ∨ ∃ i ∈ I, D.Adj i v := by
            by_contra hn
            apply hvT
            apply Finset.mem_filter.mpr
            constructor
            · exact Finset.mem_univ v
            · push_neg at hn
              exact ⟨hn.1, fun ⟨i,hi,hiv⟩ => hn.2 i hi hiv⟩
  7. Every vertex outside T is reachable from P in at most two steps, completing the proof.

    For v ∉ T, we split into the two cases from the previous step: - If v ∈ I, then by hfirst there is q ∈ P such that q = v or q → v, so v is reached from P in at most 1 step. - If i → v for some i ∈ I, then by hfirst there is q ∈ P such that q = i or q → i. If q = i, then i ∈ P reaches v in 1 step (i → v). If q → i, then q ∈ P reaches v in 2 steps via the two-edge path q → i → v. Therefore every vertex of the graph is reachable from P in at most two steps.

    lines 44–51

    uses Or.inl, Or.inr

          rcases houtside with hi | ⟨i,hi,hiv⟩
          · obtain ⟨q,hq,h⟩ := hfirst v hi
            exact ⟨q,hq,h.elim Or.inl (fun h => Or.inr (Or.inl h))⟩
          · obtain ⟨q,hq,h⟩ := hfirst i hi
            rcases h with h | h
            · subst q
              exact ⟨i,hq,Or.inr (Or.inl hiv)⟩
            · exact ⟨q,hq,Or.inr (Or.inr ⟨i,h,hiv⟩)⟩
digraph_quasikernel_on_subset
In any finite directed graph, every subset of vertices S contains an independent subset Q ⊆ S that reaches every vertex of S by a path in S of length at most two.
Finset.mem_filter.mp
If an element belongs to the filtered subset {x ∈ s | P(x)}, then it belongs to s and satisfies predicate P.
Finset.mem_filter.mpr
If an element belongs to s and satisfies predicate P, then it belongs to the filtered subset {x ∈ s | P(x)}.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set Finset.univ.
Finset.mem_union.mp
If an element belongs to the union s ∪ t, then it belongs to s or it belongs to t.
Finset.mem_union_left
If an element belongs to a finite set s, then it belongs to the union s ∪ t.
Finset.mem_union_right
If an element belongs to a finite set t, then it belongs to the union s ∪ t.
Or.inl
If proposition A holds, then the disjunction A ∨ B holds.
Or.inr
If proposition B holds, then the disjunction A ∨ B holds.

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_covers_independent_set {α : Type} [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] (I : Finset α)    (hind : ∀ u ∈ I, ∀ v ∈ I, u ≠ v → ¬ D.Adj u v) :    ∃ Q : Finset α,      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧      (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) ∧      (∀ i ∈ I, ∃ q ∈ Q, q = i ∨ D.Adj q i) := by  classical  let T := Finset.univ.filter fun x => x ∉ I ∧ ¬ ∃ i ∈ I, D.Adj i x  obtain ⟨Q,hQT,hQind,hQcov⟩ := digraph_quasikernel_on_subset D T  let R := I.filter fun i => ¬ ∃ q ∈ Q, D.Adj q i  let P := Q ∪ R  have hfirst : ∀ i ∈ I, ∃ q ∈ P, q = i ∨ D.Adj q i := by    intro i hi    by_cases h : ∃ q ∈ Q, D.Adj q i    · obtain ⟨q,hq,hqi⟩ := h      exact ⟨q,Finset.mem_union_left _ hq,Or.inr hqi⟩    · have hiR : i ∈ R := Finset.mem_filter.mpr ⟨hi,h⟩      exact ⟨i,Finset.mem_union_right _ hiR,Or.inl rfl⟩  refine ⟨P, ?_, ?_, hfirst⟩  · intro a ha b hb hab    rcases Finset.mem_union.mp ha with ha | ha <;>      rcases Finset.mem_union.mp hb with hb | hb    · exact hQind a ha b hb hab    · exact fun h => (Finset.mem_filter.mp hb).2 ⟨a,ha,h⟩    · exact fun h => (Finset.mem_filter.mp (hQT hb)).2.2 ⟨a,(Finset.mem_filter.mp ha).1,h⟩    · exact hind a (Finset.mem_filter.mp ha).1 b (Finset.mem_filter.mp hb).1 hab  · intro v    by_cases hvT : v ∈ T    · obtain ⟨q,hq,h⟩ := hQcov v hvT      refine ⟨q,Finset.mem_union_left _ hq,?_⟩      rcases h with h | h | ⟨w,_,h1,h2⟩      · exact Or.inl h      · exact Or.inr (Or.inl h)      · exact Or.inr (Or.inr ⟨w,h1,h2⟩)    · have houtside : v ∈ I ∨ ∃ i ∈ I, D.Adj i v := by        by_contra hn        apply hvT        apply Finset.mem_filter.mpr        constructor        · exact Finset.mem_univ v        · push_neg at hn          exact ⟨hn.1, fun ⟨i,hi,hiv⟩ => hn.2 i hi hiv⟩      rcases houtside with hi | ⟨i,hi,hiv⟩      · obtain ⟨q,hq,h⟩ := hfirst v hi        exact ⟨q,hq,h.elim Or.inl (fun h => Or.inr (Or.inl h))⟩      · obtain ⟨q,hq,h⟩ := hfirst i hi        rcases h with h | h        · subst q          exact ⟨i,hq,Or.inr (Or.inl hiv)⟩        · exact ⟨q,hq,Or.inr (Or.inr ⟨i,h,hiv⟩)⟩
See it in the graphDiscuss this resultChallenge it