digraph_kernel_perfect_subset_quasikernel_cover
Let D be a finite directed graph, allowing loops. Call a vertex set independent when there is no arc between any two distinct vertices in it, so a loop does not prevent independence. Suppose every subset of S has an independent subset that contains or has an arc to each vertex of that subset. Then D has an independent set Q from which every vertex is reachable in at most two steps, every vertex of S belongs to Q or is reached from Q in one step, and no vertex of Q outside S is reached in one step from S.
Statement
theorem digraph_kernel_perfect_subset_quasikernel_cover {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (S : Finset α) (hkernel : ∀ T : Finset α, T ⊆ S → ∃ K : Finset α, K ⊆ T ∧ (∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) ∧ (∀ v ∈ T, ∃ u ∈ K, 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) ∧ (∀ s ∈ S, ∃ q ∈ Q, q = s ∨ D.Adj q s) ∧ (∀ v ∈ Q, v ∉ S → ¬ ∃ s ∈ S, D.Adj s v)
- Formalizes
- Lemma 14 of A Variable Version of the Quasi-Kernel Conjecture, https://www.combinatorics.org/ojs/index.php/eljc/article/download/v32i2p53/pdf/; all arcs reversed and the external-neighborhood convention made explicit.
- 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 3
- digraph_two_kernel_perfect_sets_weighted_half_coverIf nonnegative integer vertex weights are supported on the union of two kernel-perfect sets of a finite digraph, some quasi-kernel has at…
- digraph_any_two_vertices_quasikernel_coverFor any two vertices of a finite digraph, some quasi-kernel has both vertices in its closed out-neighborhood.
- digraph_quasikernel_weighted_half_cover_support_sixFor any finite loopless digraph and nonnegative integer vertex weights supported on at most six vertices, some quasi-kernel has at least…
Read back from the Lean
Let $α$ be a finite type with decidable equality, let $D$ be a directed graph on $α$ with decidable adjacency relation $D\text{.Adj}$, and let $S$ be a finite subset of $α$ (Finset α).
Assume the hypothesis hkernel: for every subset $T \subseteq S$ (as a Finset α), there exists a subset $K \subseteq T$ such that:
1. $K$ is independent: for all $u, v \in K$, if $u \neq v$, then $\neg D\text{.Adj } u\ v$.
2. $K$ out-dominates $T$: for every $v \in T$, there exists $u \in K$ such that $u = v$ or $D\text{.Adj } u\ v$.
Then there exists a subset $Q \subseteq α$ (Finset α) such that all of the following hold:
1. $Q$ is independent: for all $u, v \in Q$, if $u \neq v$, then $\neg D\text{.Adj } u\ v$.
2. $Q$ is a quasi-kernel for the entire graph: for every vertex $v : α$, there exists $u \in Q$ such that $u = v$, or $D\text{.Adj } u\ v$, or there exists some $w : α$ such that $D\text{.Adj } u\ w$ and $D\text{.Adj } w\ v$ (i.e., every vertex in $α$ is reachable from $Q$ in at most 2 steps).
3. $Q$ out-dominates $S$ in at most 1 step: for every $s \in S$, there exists $q \in Q$ such that $q = s$ or $D\text{.Adj } q\ s$.
4. No vertex in $S$ has an edge to $Q \setminus S$: for every $v \in Q$, if $v \notin S$, then there is no $s \in S$ such that $D\text{.Adj } s\ v$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
We define T as the set of vertices outside S with no incoming arcs from S, and select a quasi-kernel Q ⊆ T of the subgraph induced by T. We then identify the subset U ⊆ S of vertices receiving no arcs from Q, and use the kernel-perfect hypothesis on S to obtain a kernel K ⊆ U. The desired set is P = Q ∪ K. Independence of P holds because no arcs can run between Q and K by construction of T and U, while every vertex of the graph is reachable from P in at most two steps by combining the quasi-kernel property of Q on T with the one-step coverage of S provided by Q and K.
We construct the candidate set P = Q ∪ K from a quasi-kernel Q on the non-out-neighbors of S and a kernel K on the uncovered vertices of S.
We work classically (line 13). We define T as the set of vertices outside S that have no incoming arc from S (line 14). Using `digraph_quasikernel_on_subset`, we obtain a quasi-kernel Q ⊆ T of the subgraph induced by T, meaning Q is independent and reaches every vertex of T in at most two steps (line 15). We then define U ⊆ S as the set of vertices in S that receive no arc from any vertex in Q (line 16). By the hypothesis `hkernel` applied to U ⊆ S (using `Finset.filter_subset`), we obtain a kernel K ⊆ U, which is independent and covers every vertex of U in at most one step (line 17). Finally, we set P = Q ∪ K (line 18).
uses
digraph_quasikernel_on_subset,Finset.filter_subsetclassical let T := Finset.univ.filter fun x => x ∉ S ∧ ¬ ∃ s ∈ S, D.Adj s x obtain ⟨Q,hQT,hQind,hQcov⟩ := digraph_quasikernel_on_subset D T let U := S.filter fun s => ¬ ∃ q ∈ Q, D.Adj q s obtain ⟨K,hKU,hKind,hKcov⟩ := hkernel U (Finset.filter_subset _ _) let P := Q ∪ K
Every vertex in S belongs to P or has an incoming arc from P, and we instantiate the sought set with P.
We prove `hfirst`: for any s ∈ S, either some q ∈ Q has an arc to s, in which case q ∈ P (via `Finset.mem_union_left` and `Or.inr`), or no vertex in Q has an arc to s, which means s ∈ U (via `Finset.mem_filter.mpr`). In the latter case, the kernel property of K provides k ∈ K ⊆ P (via `Finset.mem_union_right`) that either equals s or has an arc to s (lines 20–26). With `hfirst` established, we instantiate the existential goal with P and provide `hfirst` for the third conjunct, reducing the remaining proof to showing independence of P, two-step coverage of the whole graph, and that no arcs go from S to P \ S (line 27).
uses
Finset.mem_union_left,Or.inr,Finset.mem_filter.mpr,Finset.mem_union_righthave hfirst : ∀ s ∈ S, ∃ q ∈ P, q = s ∨ D.Adj q s := by intro s hs by_cases h : ∃ q ∈ Q, D.Adj q s · obtain ⟨q,hq,hqs⟩ := h exact ⟨q,Finset.mem_union_left _ hq,Or.inr hqs⟩ · have hsU : s ∈ U := Finset.mem_filter.mpr ⟨hs,h⟩ obtain ⟨k,hk,hks⟩ := hKcov s hsU exact ⟨k,Finset.mem_union_right _ hk,hks⟩ refine ⟨P, ?_, ?_, hfirst, ?_⟩
The set P is independent.
For any two distinct vertices a, b ∈ P, we decompose a, b ∈ Q ∪ K using `Finset.mem_union.mp` into four cases. If both belong to Q, they are non-adjacent by independence of Q (`hQind`, line 31). If a ∈ Q and b ∈ K, then b ∈ U, which means no vertex in Q has an arc to b (`Finset.mem_filter.mp`, line 32). If a ∈ K and b ∈ Q, then a ∈ S and b ∈ T, which means no vertex in S has an arc to b (`Finset.mem_filter.mp`, line 33). If both belong to K, they are non-adjacent by independence of K (`hKind`, line 34).
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 (hKU hb)).2 ⟨a,ha,h⟩ · exact fun h => (Finset.mem_filter.mp (hQT hb)).2.2 ⟨a,(Finset.mem_filter.mp (hKU ha)).1,h⟩ · exact hKind a ha b hb hab
Every vertex in the graph is reachable from P in at most two steps.
Given an arbitrary vertex v, we split into cases based on whether v ∈ T (lines 35–36). If v ∈ T, the quasi-kernel property of Q (`hQcov`) gives a vertex q ∈ Q ⊆ P (via `Finset.mem_union_left`) that equals v, has an arc to v, or reaches v in two steps via an intermediate vertex w ∈ T (lines 37–42, using `Or.inl` and `Or.inr`). If v ∉ T, we deduce by contradiction that either v ∈ S or there is an arc s → v from some s ∈ S, using `Finset.mem_filter.mpr` and `Finset.mem_univ` together with `push_neg` (lines 43–50). In the subcase v ∈ S, `hfirst` provides a vertex in P that equals v or has an arc to v (lines 52–53). In the subcase s → v with s ∈ S, `hfirst` applied to s provides q ∈ P such that either q = s (yielding a 1-step arc q → v) or q → s (yielding a 2-step path q → s → v), completing the coverage (lines 54–58).
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 ∈ S ∨ ∃ s ∈ S, D.Adj s 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 ⟨s,hs,hsv⟩ => hn.2 s hs hsv⟩ rcases houtside with hs | ⟨s,hs,hsv⟩ · obtain ⟨q,hq,h⟩ := hfirst v hs exact ⟨q,hq,h.elim Or.inl (fun h => Or.inr (Or.inl h))⟩ · obtain ⟨q,hq,h⟩ := hfirst s hs rcases h with h | h · subst q exact ⟨s,hq,Or.inr (Or.inl hsv)⟩ · exact ⟨q,hq,Or.inr (Or.inr ⟨s,h,hsv⟩)⟩
No vertex of P outside S receives an arc from S.
Let v ∈ P with v ∉ S, and suppose for contradiction that there is an arc from some s ∈ S to v (line 60). Unpacking v ∈ Q ∪ K with `Finset.mem_union.mp`, if v ∈ Q, then v ∈ T (since Q ⊆ T), which contradicts the definition of T requiring that no vertex in S has an arc to v (`Finset.mem_filter.mp`, line 62). If v ∈ K, then v ∈ U ⊆ S (`Finset.mem_filter.mp`), contradicting v ∉ S (line 63).
uses
Finset.mem_union.mp,Finset.mem_filter.mp· intro v hv hvS hadj rcases Finset.mem_union.mp hv with hvQ | hvK · exact (Finset.mem_filter.mp (hQT hvQ)).2.2 hadj · exact hvS ((Finset.mem_filter.mp (hKU hvK)).1)
digraph_quasikernel_on_subset- In any finite directed graph, every vertex subset has a quasi-kernel: an independent subset from which every vertex in the subset is reachable in at most two steps via intermediate vertices in that subset.
Finset.filter_subset- Filtering a finite set by a predicate yields a subset of the original set.
Finset.mem_union_left- An element belonging to the left set belongs to the union of the two sets.
Finset.mem_union_right- An element belonging to the right set belongs to the union of the two sets.
Finset.mem_union.mp- If an element belongs to a union of two sets, it belongs to the left set or to the right set.
Finset.mem_filter.mp- An element of a filtered finite set belongs to the original set and satisfies the filtering condition.
Finset.mem_filter.mpr- An element that belongs to a finite set and satisfies a predicate belongs to the filtered set.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set.
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.
- Classical logic is used (enabled via `classical` on line 13) to form set complements and perform case analysis on membership and reachability.
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_kernel_perfect_subset_quasikernel_cover {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (S : Finset α) (hkernel : ∀ T : Finset α, T ⊆ S → ∃ K : Finset α, K ⊆ T ∧ (∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) ∧ (∀ v ∈ T, ∃ u ∈ K, 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) ∧ (∀ s ∈ S, ∃ q ∈ Q, q = s ∨ D.Adj q s) ∧ (∀ v ∈ Q, v ∉ S → ¬ ∃ s ∈ S, D.Adj s v) := by classical let T := Finset.univ.filter fun x => x ∉ S ∧ ¬ ∃ s ∈ S, D.Adj s x obtain ⟨Q,hQT,hQind,hQcov⟩ := digraph_quasikernel_on_subset D T let U := S.filter fun s => ¬ ∃ q ∈ Q, D.Adj q s obtain ⟨K,hKU,hKind,hKcov⟩ := hkernel U (Finset.filter_subset _ _) let P := Q ∪ K have hfirst : ∀ s ∈ S, ∃ q ∈ P, q = s ∨ D.Adj q s := by intro s hs by_cases h : ∃ q ∈ Q, D.Adj q s · obtain ⟨q,hq,hqs⟩ := h exact ⟨q,Finset.mem_union_left _ hq,Or.inr hqs⟩ · have hsU : s ∈ U := Finset.mem_filter.mpr ⟨hs,h⟩ obtain ⟨k,hk,hks⟩ := hKcov s hsU exact ⟨k,Finset.mem_union_right _ hk,hks⟩ 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 (hKU hb)).2 ⟨a,ha,h⟩ · exact fun h => (Finset.mem_filter.mp (hQT hb)).2.2 ⟨a,(Finset.mem_filter.mp (hKU ha)).1,h⟩ · exact hKind a ha b hb 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 ∈ S ∨ ∃ s ∈ S, D.Adj s 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 ⟨s,hs,hsv⟩ => hn.2 s hs hsv⟩ rcases houtside with hs | ⟨s,hs,hsv⟩ · obtain ⟨q,hq,h⟩ := hfirst v hs exact ⟨q,hq,h.elim Or.inl (fun h => Or.inr (Or.inl h))⟩ · obtain ⟨q,hq,h⟩ := hfirst s hs rcases h with h | h · subst q exact ⟨s,hq,Or.inr (Or.inl hsv)⟩ · exact ⟨q,hq,Or.inr (Or.inr ⟨s,h,hsv⟩)⟩ · intro v hv hvS hadj rcases Finset.mem_union.mp hv with hvQ | hvK · exact (Finset.mem_filter.mp (hQT hvQ)).2.2 hadj · exact hvS ((Finset.mem_filter.mp (hKU hvK)).1)