digraph_quasikernel_neighborhood_preserving_completion
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.
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.
uses
Or.inl,Or.inrclassical 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⟩)⟩
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.
uses
Finset.mem_filter.mplet 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)
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.
uses
Finset.subset_union_left,Finset.union_subsetrefine ⟨R ∪ Z, Finset.subset_union_left, Finset.union_subset hRK hZK, ?_, ?_, houtside, ?_⟩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.
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
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.
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⟩
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'.
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.
- The proof uses classical logic (double negation elimination) to deduce that any vertex not belonging to the filtered set Z must be reached from R in at most two steps.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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