digraph_quasikernel_covers_independent_set
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.
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.
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 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.
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⟩
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.
refine ⟨P, ?_, ?_, hfirst⟩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.
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
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.
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⟩)
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.
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⟩
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.
uses
Or.inl,Or.inrrcases 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
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_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⟩)⟩