digraph_quasikernel_on_subset
For 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 from Q in at most two arcs using intermediate vertices in S.
Statement
theorem digraph_quasikernel_on_subset {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (S : Finset α) : ∃ Q : Finset α, Q ⊆ S ∧ (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧ (∀ v ∈ S, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w ∈ S, D.Adj u w ∧ D.Adj w v)
- Source
- Standard qualitative quasi-kernel existence construction, recalled in arXiv:2601.11847 Section 1.1; foundational helper for OP-337.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 4
- digraph_kernel_perfect_subset_quasikernel_coverLet D be a finite directed graph, allowing loops. Call a vertex set independent when there is no arc between any two distinct vertices in…
- digraph_quasikernel_independent_cover_avoids_outneighborsIn a finite loopless digraph, every independent set is contained in the closed out-neighborhood of a quasi-kernel that contains none of…
- digraph_quasikernel_covers_independent_setFor any finite directed graph and any independent vertex set I, there is a quasi-kernel whose closed out-neighborhood contains I.
- digraph_quasikernel_existsEvery finite digraph contains an independent set from which every vertex is reachable in at most two directed arcs.
The proof, explained
The theorem is proven by strong induction on the finite set of vertices S (Chvátal's quasi-kernel theorem). If S is empty, the empty set is trivially a quasi-kernel. When S is nonempty, we select an arbitrary vertex v ∈ S and consider the strict subset T ⊂ S of vertices that are neither v nor out-neighbors of v, which admits a quasi-kernel Q by induction. If some vertex in Q points to v, then Q already 2-covers all of S; otherwise, no arcs go between v and Q, so Q ∪ {v} is an independent set that 2-covers all of S.
We set up strong induction on the finite vertex set S.
We permit classical logic and perform strong induction on S ordered by strict subset inclusion using Finset.strongInduction. The induction hypothesis ih states that the theorem holds for all strict subsets T ⊂ S.
uses
Finset.strongInductionclassical induction S using Finset.strongInduction with | _ S ih =>
If S is empty, the empty set is a valid quasi-kernel.
When S = ∅, we choose Q = ∅. The empty set is trivially a subset of S, independence holds vacuously, and the covering condition holds vacuously since S has no elements.
by_cases he : S = ∅ · subst S refine ⟨∅, ?_, ?_, ?_⟩ <;> simp
If S is nonempty, we pick a vertex v ∈ S and define a strict subset T ⊂ S of vertices that are neither v nor out-neighbors of v.
Since S ≠ ∅, there exists an element v ∈ S by Finset.nonempty_iff_ne_empty.mpr. We let T be the set of elements w ∈ S such that w ≠ v and v has no arc to w, which is a subset of S by Finset.filter_subset. By construction, v ∉ T because v ≠ v is false (Finset.mem_filter.mp), which implies T ≠ S and therefore T ⊂ S is a strict subset by Finset.ssubset_iff_subset_ne.mpr.
uses
Finset.nonempty_iff_ne_empty.mpr,Finset.filter_subset,Finset.ssubset_iff_subset_ne.mpr,Finset.mem_filter.mp· obtain ⟨v,hv⟩ := Finset.nonempty_iff_ne_empty.mpr he let T := S.filter (fun w => w ≠ v ∧ ¬ D.Adj v w) have hTS : T ⊆ S := Finset.filter_subset _ _ have hT : T ⊂ S := by apply Finset.ssubset_iff_subset_ne.mpr refine ⟨hTS, ?_⟩ intro eq have hvT : v ∈ T := by rw [eq]; exact hv exact ((Finset.mem_filter.mp hvT).2.1) rfl
By the induction hypothesis, T has a quasi-kernel Q, and no element of Q is equal to v or receives an arc from v.
Applying the induction hypothesis to T ⊂ S yields an independent set Q ⊆ T that 2-covers T. Since Q ⊆ T, every u ∈ Q inherits the property that u ≠ v and ¬ D.Adj v u from the definition of T via Finset.mem_filter.mp.
uses
Finset.mem_filter.mpobtain ⟨Q,hQT,hind,hcover⟩ := ih T hT have hqprop : ∀ u ∈ Q, u ≠ v ∧ ¬ D.Adj v u := by intro u hu exact (Finset.mem_filter.mp (hQT hu)).2
Every vertex in T is reachable from Q in at most two steps using vertices in S.
By the induction hypothesis, every x ∈ T is covered from Q in at most two steps with intermediate vertices in T (using Or.inl and Or.inr). Since T ⊆ S, any intermediate vertex in T also belongs to S.
uses
Or.inl,Or.inrhave coverT : ∀ x ∈ T, ∃ u ∈ Q, u = x ∨ D.Adj u x ∨ ∃ w ∈ S, D.Adj u w ∧ D.Adj w x := by intro x hx obtain ⟨u,hu,h⟩ := hcover x hx refine ⟨u,hu,?_⟩ rcases h with heq | hsingle | ⟨w,hw,huw,hwx⟩ · exact Or.inl heq · exact Or.inr (Or.inl hsingle) · exact Or.inr (Or.inr ⟨w,hTS hw,huw,hwx⟩)
Every vertex in S \ T is either v or an out-neighbor of v.
Let x ∈ S with x ∉ T. If x = v, the claim holds by Or.inl. If x ≠ v, then v must be adjacent to x; otherwise, x would satisfy all conditions to belong to T by Finset.mem_filter.mpr, contradicting x ∉ T.
uses
Or.inl,Finset.mem_filter.mprhave outside : ∀ x ∈ S, x ∉ T → x = v ∨ D.Adj v x := by intro x hxS hxT by_cases hxv : x = v · exact Or.inl hxv · right by_contra hn exact hxT (Finset.mem_filter.mpr ⟨hxS,hxv,hn⟩)
Case 1: If some vertex in Q has an arc to v, then Q is a quasi-kernel for all of S.
Suppose there is some u ∈ Q with D.Adj u v. The set Q is independent and a subset of S. Every x ∈ T is 2-covered by Q. For any x ∈ S \ T, either x = v, which is covered in one step by u → v using Or.inl and Or.inr, or D.Adj v x, which is covered in two steps by u → v → x with intermediate vertex v ∈ S using Or.inr.
uses
Or.inl,Or.inrby_cases hex : ∃ u ∈ Q, D.Adj u v · refine ⟨Q,hQT.trans hTS,hind,?_⟩ intro x hxS by_cases hxT : x ∈ T · exact coverT x hxT · obtain ⟨u,hu,huv⟩ := hex rcases outside x hxS hxT with hxv | hvx · subst x; exact ⟨u,hu,Or.inr (Or.inl huv)⟩ · exact ⟨u,hu,Or.inr (Or.inr ⟨v,hv,huv,hvx⟩)⟩
Case 2: If no vertex in Q has an arc to v, then Q ∪ {v} is an independent subset of S.
We consider insert v Q. Since v ∈ S and Q ⊆ S, insert v Q ⊆ S by Finset.insert_subset. For independence, let a, b ∈ insert v Q with a ≠ b. Using Finset.mem_insert.mp, if a = v then b ∈ Q, so v → b does not hold by definition of T; if b = v then a ∈ Q, so a → v does not hold by the case assumption; and if a, b ∈ Q, independence holds from Q being independent.
uses
Finset.insert_subset,Finset.mem_insert.mp· refine ⟨insert v Q, ?_, ?_, ?_⟩ · exact Finset.insert_subset hv (hQT.trans hTS) · intro a ha b hb hab rcases Finset.mem_insert.mp ha with haV | haQ · subst a rcases Finset.mem_insert.mp hb with hbV | hbQ · subst b; exact (hab rfl).elim · exact (hqprop b hbQ).2 · rcases Finset.mem_insert.mp hb with hbV | hbQ · subst b; intro hav; exact hex ⟨a,haQ,hav⟩ · exact hind a haQ b hbQ hab
The set Q ∪ {v} 2-covers all vertices of S, completing the proof.
For any x ∈ S, if x ∈ T, it is 2-covered by some u ∈ Q, and u ∈ insert v Q by Finset.mem_insert_of_mem. If x ∈ S \ T, then either x = v, which is in insert v Q (Finset.mem_insert_self and Or.inl), or v → x, so x is reached in one step from v ∈ insert v Q (Finset.mem_insert_self, Or.inr, and Or.inl).
uses
Finset.mem_insert_of_mem,Finset.mem_insert_self,Or.inl,Or.inr· intro x hxS by_cases hxT : x ∈ T · obtain ⟨u,hu,h⟩ := coverT x hxT exact ⟨u,Finset.mem_insert_of_mem hu,h⟩ · rcases outside x hxS hxT with hxv | hvx · subst x; exact ⟨v,Finset.mem_insert_self _ _,Or.inl rfl⟩ · exact ⟨v,Finset.mem_insert_self _ _,Or.inr (Or.inl hvx)⟩
Finset.strongInduction- Strong induction on finite sets: a property holds for all finite sets if it holds for any set whenever it holds for all its strict subsets.
Finset.nonempty_iff_ne_empty.mpr- A finite set is nonempty if and only if it is not equal to the empty set; this direction produces an element from the assumption that the set is non-empty.
Finset.filter_subset- Filtering a finite set by a predicate produces a subset of the original set.
Finset.ssubset_iff_subset_ne.mpr- A set is a strict subset of another if it is a subset and not equal to it.
Finset.mem_filter.mp- An element belongs to a filtered set only if it belongs to the original set and satisfies the filtering predicate.
Finset.mem_filter.mpr- An element belongs to a filtered set if it belongs to the original set and satisfies the filtering predicate.
Or.inl- The left injection into a disjunction: if A holds, then A ∨ B holds.
Or.inr- The right injection into a disjunction: if B holds, then A ∨ B holds.
Finset.insert_subset- Inserting an element into a set yields a subset of a target set, provided the element and the original set are both contained in the target set.
Finset.mem_insert.mp- An element belongs to insert a s only if it equals a or belongs to s.
Finset.mem_insert_of_mem- If an element belongs to s, it belongs to insert a s.
Finset.mem_insert_self- An element always belongs to the set formed by inserting it into any set.
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_on_subset {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (S : Finset α) : ∃ Q : Finset α, Q ⊆ S ∧ (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧ (∀ v ∈ S, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w ∈ S, D.Adj u w ∧ D.Adj w v) := by classical induction S using Finset.strongInduction with | _ S ih => by_cases he : S = ∅ · subst S refine ⟨∅, ?_, ?_, ?_⟩ <;> simp · obtain ⟨v,hv⟩ := Finset.nonempty_iff_ne_empty.mpr he let T := S.filter (fun w => w ≠ v ∧ ¬ D.Adj v w) have hTS : T ⊆ S := Finset.filter_subset _ _ have hT : T ⊂ S := by apply Finset.ssubset_iff_subset_ne.mpr refine ⟨hTS, ?_⟩ intro eq have hvT : v ∈ T := by rw [eq]; exact hv exact ((Finset.mem_filter.mp hvT).2.1) rfl obtain ⟨Q,hQT,hind,hcover⟩ := ih T hT have hqprop : ∀ u ∈ Q, u ≠ v ∧ ¬ D.Adj v u := by intro u hu exact (Finset.mem_filter.mp (hQT hu)).2 have coverT : ∀ x ∈ T, ∃ u ∈ Q, u = x ∨ D.Adj u x ∨ ∃ w ∈ S, D.Adj u w ∧ D.Adj w x := by intro x hx obtain ⟨u,hu,h⟩ := hcover x hx refine ⟨u,hu,?_⟩ rcases h with heq | hsingle | ⟨w,hw,huw,hwx⟩ · exact Or.inl heq · exact Or.inr (Or.inl hsingle) · exact Or.inr (Or.inr ⟨w,hTS hw,huw,hwx⟩) have outside : ∀ x ∈ S, x ∉ T → x = v ∨ D.Adj v x := by intro x hxS hxT by_cases hxv : x = v · exact Or.inl hxv · right by_contra hn exact hxT (Finset.mem_filter.mpr ⟨hxS,hxv,hn⟩) by_cases hex : ∃ u ∈ Q, D.Adj u v · refine ⟨Q,hQT.trans hTS,hind,?_⟩ intro x hxS by_cases hxT : x ∈ T · exact coverT x hxT · obtain ⟨u,hu,huv⟩ := hex rcases outside x hxS hxT with hxv | hvx · subst x; exact ⟨u,hu,Or.inr (Or.inl huv)⟩ · exact ⟨u,hu,Or.inr (Or.inr ⟨v,hv,huv,hvx⟩)⟩ · refine ⟨insert v Q, ?_, ?_, ?_⟩ · exact Finset.insert_subset hv (hQT.trans hTS) · intro a ha b hb hab rcases Finset.mem_insert.mp ha with haV | haQ · subst a rcases Finset.mem_insert.mp hb with hbV | hbQ · subst b; exact (hab rfl).elim · exact (hqprop b hbQ).2 · rcases Finset.mem_insert.mp hb with hbV | hbQ · subst b; intro hav; exact hex ⟨a,haQ,hav⟩ · exact hind a haQ b hbQ hab · intro x hxS by_cases hxT : x ∈ T · obtain ⟨u,hu,h⟩ := coverT x hxT exact ⟨u,Finset.mem_insert_of_mem hu,h⟩ · rcases outside x hxS hxT with hxv | hvx · subst x; exact ⟨v,Finset.mem_insert_self _ _,Or.inl rfl⟩ · exact ⟨v,Finset.mem_insert_self _ _,Or.inr (Or.inl hvx)⟩