AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_neighborhood_preserving_completion

theoremverified

A subset that preserves every first out-neighbor of a quasi-kernel can be uniquely completed to the least quasi-kernel lying between it and the original set; every vertex outside the original set is already two-step reached by that subset.

Statement

theorem digraph_quasikernel_neighborhood_preserving_completion
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (K R : Finset α)
    (hRK : R ⊆ K)
    (hind : ∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v)
    (hcover : ∀ v, ∃ u ∈ K, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v)
    (hpres : ∀ v, (∃ u ∈ K, D.Adj u v) → ∃ u ∈ R, D.Adj u v) :
    ∃ P : Finset α, R ⊆ P ∧ P ⊆ K ∧
      (∀ u ∈ P, ∀ v ∈ P, u ≠ v → ¬ D.Adj u v) ∧
      (∀ v, ∃ u ∈ P, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) ∧
      (∀ v, v ∉ K → ∃ u ∈ R, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) ∧
      (∀ P' : Finset α, R ⊆ P' → P' ⊆ K →
        (∀ v, ∃ u ∈ P', u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) → P ⊆ P')
Source
arXiv:2610.23487, Section 2, and OP-337 campaign; finite neighborhood-preserving completion.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof constructs the completed quasi-kernel explicitly as P = R ∪ Z, where Z consists of all vertices that cannot be reached from R in at most two steps. The neighborhood-preserving hypothesis ensures that every vertex outside K is reached from R in at most two steps, which implies Z ⊆ K and hence R ⊆ P ⊆ K. Independence of P is inherited directly from K, and quasi-domination holds because vertices in Z reach themselves while vertices outside Z are reached by R ⊆ P. Finally, P is minimal because any intermediate quasi-kernel P' contains R and cannot dominate any vertex in Z via an edge without placing that vertex within two steps of R.

  1. Every vertex outside K is reached from R in at most two steps.

    Let v be any vertex outside K. Because K is a quasi-kernel (by hcover), some vertex u ∈ K reaches v in 0, 1, or 2 steps. The 0-step case u = v is impossible since u ∈ K while v ∉ K. In the 1-step case (u → v), the neighborhood-preserving condition (hpres) yields r ∈ R with r → v. In the 2-step case (u → w → v), applying hpres to the intermediate vertex w yields r ∈ R with r → w, which forms the 2-step path r → w → v. Thus, v is always reached from R in at most two steps.

    lines 14–24

    uses Or.inl, Or.inr

      classical
      have houtside : ∀ v, v ∉ K → ∃ u ∈ R,
          u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v := by
        intro v hv
        obtain ⟨u,hu,h⟩ := hcover v
        rcases h with heq | hadj | ⟨w,huw,hwv⟩
        · subst u; exact (hv hu).elim
        · obtain ⟨r,hr,hrv⟩ := hpres v ⟨u,hu,hadj⟩
          exact ⟨r,hr,Or.inr (Or.inl hrv)⟩
        · obtain ⟨r,hr,hrw⟩ := hpres w ⟨u,hu,huw⟩
          exact ⟨r,hr,Or.inr (Or.inr ⟨w,hrw,hwv⟩)⟩
  2. The set Z of vertices not reachable from R in at most two steps is a subset of K.

    Define Z as the set of all vertices from which no path of length 0, 1, or 2 from R exists. For any z ∈ Z, suppose for contradiction that z ∉ K. Then by the previous claim (houtside), z would be reachable from R in at most two steps, contradicting the defining property of Z (via Finset.mem_filter.mp). Hence, z ∈ K.

    lines 25–30

    uses Finset.mem_filter.mp

      let Z := Finset.univ.filter fun v => ¬ ∃ u ∈ R,
          u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v
      have hZK : Z ⊆ K := by
        intro z hz
        by_contra hzK
        exact (Finset.mem_filter.mp hz).2 (houtside z hzK)
  3. The candidate completion P = R ∪ Z satisfies R ⊆ P ⊆ K and reaches every vertex outside K from R in at most two steps.

    By Finset.subset_union_left, R is a subset of R ∪ Z. Because R ⊆ K and Z ⊆ K, their union satisfies R ∪ Z ⊆ K by Finset.union_subset. The reachability of vertices outside K from R is provided by houtside. This reduces the existence goal to checking independence of P, quasi-domination by P, and minimality of P.

    line 31

    uses Finset.subset_union_left, Finset.union_subset

      refine ⟨R ∪ Z, Finset.subset_union_left, Finset.union_subset hRK hZK, ?_, ?_, houtside, ?_⟩
  4. The candidate set P = R ∪ Z is an independent set.

    Let u, v ∈ P be distinct vertices. Since P ⊆ K (by Finset.union_subset), both u and v belong to K. The independence of K (hind) guarantees that there is no directed edge from u to v.

    lines 32–35

    uses Finset.union_subset

      · intro u hu v hv huv
        have huK : u ∈ K := (Finset.union_subset hRK hZK) hu
        have hvK : v ∈ K := (Finset.union_subset hRK hZK) hv
        exact hind u huK v hvK huv
  5. The candidate set P = R ∪ Z quasi-dominates the graph.

    For any vertex v, we consider whether v ∈ Z. If v ∈ Z, then v ∈ P via Finset.mem_union_right, so v reaches itself in 0 steps. If v ∉ Z, then by definition of Z as a filter, the negation of reachability from R fails (Finset.mem_filter.mpr, Finset.mem_univ); eliminating the double negation with Classical.not_not.mp yields an element u ∈ R reaching v in at most two steps. Since u ∈ R ⊆ P (by Finset.mem_union_left), v is reached from P.

    lines 36–44

    uses Finset.mem_union_right, Or.inl, Finset.mem_filter.mpr, Finset.mem_univ, Classical.not_not.mp, Finset.mem_union_left

      · intro v
        by_cases hv : v ∈ Z
        · exact ⟨v,Finset.mem_union_right _ hv,Or.inl rfl⟩
        · have hv' : ¬ ¬ (∃ u ∈ R, u = v ∨ D.Adj u v ∨
              ∃ w, D.Adj u w ∧ D.Adj w v) := by
            intro hn
            exact hv (Finset.mem_filter.mpr ⟨Finset.mem_univ v,hn⟩)
          obtain ⟨u,hu,huv⟩ := Classical.not_not.mp hv'
          exact ⟨u,Finset.mem_union_left _ hu,huv⟩
  6. The candidate set P = R ∪ Z is the least quasi-kernel between R and K.

    Let P' be any set with R ⊆ P' ⊆ K that quasi-dominates the graph. To show P ⊆ P', take any z ∈ P = R ∪ Z. By Finset.mem_union.mp, either z ∈ R or z ∈ Z. If z ∈ R, then z ∈ P' because R ⊆ P'. If z ∈ Z, the quasi-domination hypothesis on P' provides some u ∈ P' reaching z in 0, 1, or 2 steps: if u = z, then z ∈ P' immediately; if u → z, then since u ∈ P' ⊆ K, the neighborhood-preserving condition (hpres) gives r ∈ R with r → z, contradicting z ∈ Z (Finset.mem_filter.mp); if u → w → z, then hpres gives r ∈ R with r → w and hence r → w → z, again contradicting z ∈ Z. Thus z ∈ P' in every non-contradictory case, proving P ⊆ P'.

    lines 46–55

    uses Finset.mem_union.mp, Finset.mem_filter.mp, Or.inr, Or.inl

      · intro P' hRP hPK hdom z hz
        rcases Finset.mem_union.mp hz with hzR | hzZ
        · exact hRP hzR
        · obtain ⟨u,hu,h⟩ := hdom z
          rcases h with heq | hadj | ⟨w,huw,hwz⟩
          · subst u; exact hu
          · obtain ⟨r,hr,hrz⟩ := hpres z ⟨u,hPK hu,hadj⟩
            exact ((Finset.mem_filter.mp hzZ).2 ⟨r,hr,Or.inr (Or.inl hrz)⟩).elim
          · obtain ⟨r,hr,hrw⟩ := hpres w ⟨u,hPK hu,huw⟩
            exact ((Finset.mem_filter.mp hzZ).2 ⟨r,hr,Or.inr (Or.inr ⟨w,hrw,hwz⟩)⟩).elim
Classical.not_not.mp
Double negation elimination: ¬¬a implies a.
Finset.mem_filter.mp
An element of the filtered set {x ∈ s | p x} belongs to s and satisfies p.
Finset.mem_filter.mpr
If an element belongs to s and satisfies p, then it belongs to the filtered set {x ∈ s | p x}.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
Finset.mem_union.mp
If an element belongs to 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 s ∪ t.
Finset.mem_union_right
If an element belongs to t, then it belongs to s ∪ t.
Finset.subset_union_left
Any finite set is a subset of its union with another set: s ⊆ s ∪ t.
Finset.union_subset
If s ⊆ u and t ⊆ u, then s ∪ t ⊆ u.
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_neighborhood_preserving_completion    {α : Type} [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] (K R : Finset α)    (hRK : R ⊆ K)    (hind : ∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v)    (hcover : ∀ v, ∃ u ∈ K, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v)    (hpres : ∀ v, (∃ u ∈ K, D.Adj u v) → ∃ u ∈ R, D.Adj u v) :    ∃ P : Finset α, R ⊆ P ∧ P ⊆ K ∧      (∀ u ∈ P, ∀ v ∈ P, u ≠ v → ¬ D.Adj u v) ∧      (∀ v, ∃ u ∈ P, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) ∧      (∀ v, v ∉ K → ∃ u ∈ R, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) ∧      (∀ P' : Finset α, R ⊆ P' → P' ⊆ K →        (∀ v, ∃ u ∈ P', u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) → P ⊆ P') := by  classical  have houtside : ∀ v, v ∉ K → ∃ u ∈ R,      u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v := by    intro v hv    obtain ⟨u,hu,h⟩ := hcover v    rcases h with heq | hadj | ⟨w,huw,hwv⟩    · subst u; exact (hv hu).elim    · obtain ⟨r,hr,hrv⟩ := hpres v ⟨u,hu,hadj⟩      exact ⟨r,hr,Or.inr (Or.inl hrv)⟩    · obtain ⟨r,hr,hrw⟩ := hpres w ⟨u,hu,huw⟩      exact ⟨r,hr,Or.inr (Or.inr ⟨w,hrw,hwv⟩)⟩  let Z := Finset.univ.filter fun v => ¬ ∃ u ∈ R,      u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v  have hZK : Z ⊆ K := by    intro z hz    by_contra hzK    exact (Finset.mem_filter.mp hz).2 (houtside z hzK)  refine ⟨R ∪ Z, Finset.subset_union_left, Finset.union_subset hRK hZK, ?_, ?_, houtside, ?_⟩  · intro u hu v hv huv    have huK : u ∈ K := (Finset.union_subset hRK hZK) hu    have hvK : v ∈ K := (Finset.union_subset hRK hZK) hv    exact hind u huK v hvK huv  · intro v    by_cases hv : v ∈ Z    · exact ⟨v,Finset.mem_union_right _ hv,Or.inl rfl⟩    · have hv' : ¬ ¬ (∃ u ∈ R, u = v ∨ D.Adj u v ∨          ∃ w, D.Adj u w ∧ D.Adj w v) := by        intro hn        exact hv (Finset.mem_filter.mpr ⟨Finset.mem_univ v,hn⟩)      obtain ⟨u,hu,huv⟩ := Classical.not_not.mp hv'      exact ⟨u,Finset.mem_union_left _ hu,huv⟩  · intro P' hRP hPK hdom z hz    rcases Finset.mem_union.mp hz with hzR | hzZ    · exact hRP hzR    · obtain ⟨u,hu,h⟩ := hdom z      rcases h with heq | hadj | ⟨w,huw,hwz⟩      · subst u; exact hu      · obtain ⟨r,hr,hrz⟩ := hpres z ⟨u,hPK hu,hadj⟩        exact ((Finset.mem_filter.mp hzZ).2 ⟨r,hr,Or.inr (Or.inl hrz)⟩).elim      · obtain ⟨r,hr,hrw⟩ := hpres w ⟨u,hPK hu,huw⟩        exact ((Finset.mem_filter.mp hzZ).2 ⟨r,hr,Or.inr (Or.inr ⟨w,hrw,hwz⟩)⟩).elim
See it in the graphDiscuss this resultChallenge it