digraph_quasikernel_independent_cover_avoids_outneighbors
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
- digraph_two_vertex_avoidance_obstruction_parent_adjacencyIf every quasi-kernel of a finite loopless digraph contains at least one of two specified vertices, then each in-neighbor of the first…
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.
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.
uses
digraph_quasikernel_on_subsetclassical 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
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.
uses
Finset.mem_union_left,Or.inr,Finset.mem_filter.mpr,Finset.mem_union_right,Or.inlhave 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⟩
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.
uses
Finset.mem_union.mp,Finset.mem_filter.mprefine ⟨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
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.
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⟩)⟩
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.
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
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_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