AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_independent_cover_avoids_outneighbors

theoremverified

In a finite loopless digraph, every independent set is contained in the closed out-neighborhood of a quasi-kernel that contains none of its open out-neighbors.

Statement

theorem digraph_quasikernel_independent_cover_avoids_outneighbors {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (I : Finset α)
    (hind : ∀ u ∈ I, ∀ v ∈ I, u ≠ v → ¬ D.Adj u v)
    (hloop : ∀ v, ¬ D.Adj v 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) ∧
      (∀ v ∈ Q, ¬ ∃ i ∈ I, D.Adj i v)
Source
Special case of Lemma 14 of https://www.combinatorics.org/ojs/index.php/eljc/article/download/v32i2p53/pdf/, with arcs reversed; independently formalized by the independent-set recursion in 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…
Used by 1

The proof, explained

The proof constructs a quasi-kernel P for the whole digraph by combining a quasi-kernel Q on the subdigraph away from I with the uncovered vertices of I. First, it defines T as the set of vertices outside I with no incoming edges from I and obtains a quasi-kernel Q ⊆ T via digraph_quasikernel_on_subset. It then adds the set R ⊆ I of vertices not dominated by Q to form P = Q ∪ R. Finally, it verifies that P is independent, reaches every vertex of the digraph in at most two steps, dominates I in at most one step, and contains no out-neighbors of I.

  1. Construct the candidate quasi-kernel P = Q ∪ R by taking a quasi-kernel Q on the set T of vertices outside I ∪ N⁺(I) and adding the subset R ⊆ I of vertices not dominated by Q.

    Working classically, we define T to be the set of all vertices outside I that receive no directed edges from I. By digraph_quasikernel_on_subset applied to T, there exists an independent set Q ⊆ T that reaches every vertex of T in at most two steps. We then define R ⊆ I as the vertices of I not dominated by any vertex in Q, and set P = Q ∪ R as our candidate quasi-kernel.

    lines 10–14

    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 q ∈ Q has an edge q → i. If so, then q ∈ P dominates i in one step, using Finset.mem_union_left and Or.inr. If no such q exists, then by definition of R we have i ∈ R (via Finset.mem_filter.mpr), so i ∈ P using Finset.mem_union_right and Or.inl.

    lines 15–21

    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. P is an independent set.

    Using refine, we provide P as the witness, supplying the helper hfirst for the coverage of I. To prove P is independent, let a, b ∈ P = Q ∪ R be distinct. By Finset.mem_union.mp, there are four cases: if both are in Q, independence follows from Q being independent; if a ∈ Q and b ∈ R, an edge a → b contradicts the definition of R (via Finset.mem_filter.mp); if a ∈ R and b ∈ Q, then a ∈ I and b ∈ T, but vertices in T have no incoming edges from I; and if both are in R ⊆ I, an edge a → b contradicts the independence of I.

    lines 22–29

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

      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
  4. Every vertex of the digraph is reachable from P in at most two steps.

    For an arbitrary vertex v, we split on whether v ∈ T. If v ∈ T, the quasi-kernel coverage property of Q reaches v in 0, 1, or 2 steps (using Finset.mem_union_left, Or.inl, and Or.inr). If v ∉ T, we deduce by contradiction (using Finset.mem_filter.mpr and Finset.mem_univ) that v ∈ I or v has an in-neighbor i ∈ I. If v ∈ I, the helper hfirst shows v is reached from P in at most 1 step. If i ∈ I has an edge to v, hfirst gives a vertex q ∈ P reaching i in 0 or 1 steps: if q = i, then i ∈ P reaches v in 1 step; if q → i, then q ∈ P reaches v in 2 steps via i.

    lines 30–53

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

      · 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⟩)⟩
  5. No vertex in P is an out-neighbor of any vertex in I.

    Suppose for contradiction that v ∈ P has an incoming edge from some i ∈ I. By Finset.mem_union.mp, either v ∈ Q or v ∈ R. If v ∈ Q ⊆ T, this contradicts the definition of T, which has no incoming edges from I (via Finset.mem_filter.mp). If v ∈ R ⊆ I, then both i, v ∈ I; if i = v, this contradicts the loopless hypothesis hloop, and if i ≠ v, this contradicts the independence of I.

    lines 55–62

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

      · intro v hv ⟨i,hi,hiv⟩
        rcases Finset.mem_union.mp hv with hv | hv
        · exact (Finset.mem_filter.mp (hQT hv)).2.2 ⟨i,hi,hiv⟩
        · have hvI : v ∈ I := (Finset.mem_filter.mp hv).1
          by_cases h : i = v
          · subst i
            exact hloop v hiv
          · exact hind i hi v hvI h hiv
digraph_quasikernel_on_subset
In any finite digraph, every subset of vertices S contains an independent set Q ⊆ S such that every vertex in S is reachable from Q in at most two steps via vertices in S.
Finset.mem_filter.mp
If an element belongs to the filtered subset {x ∈ s | p(x)}, then it belongs to s and satisfies the predicate p.
Finset.mem_filter.mpr
If an element belongs to s and satisfies the 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 s, then it belongs to the union s ∪ t.
Finset.mem_union_right
If an element belongs to t, then it belongs to the union s ∪ t.
Or.inl
From a proof of A, infer the disjunction A ∨ B.
Or.inr
From a proof of B, infer the disjunction A ∨ B.

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_independent_cover_avoids_outneighbors {α : Type} [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] (I : Finset α)    (hind : ∀ u ∈ I, ∀ v ∈ I, u ≠ v → ¬ D.Adj u v)    (hloop : ∀ v, ¬ D.Adj v 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) ∧      (∀ v ∈ Q, ¬ ∃ i ∈ I, D.Adj i v) := 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⟩)⟩  · intro v hv ⟨i,hi,hiv⟩    rcases Finset.mem_union.mp hv with hv | hv    · exact (Finset.mem_filter.mp (hQT hv)).2.2 ⟨i,hi,hiv⟩    · have hvI : v ∈ I := (Finset.mem_filter.mp hv).1      by_cases h : i = v      · subst i        exact hloop v hiv      · exact hind i hi v hvI h hiv
See it in the graphDiscuss this resultChallenge it