digraph_any_two_vertices_quasikernel_cover
For any two vertices of a finite digraph, some quasi-kernel has both vertices in its closed out-neighborhood.
Statement
theorem digraph_any_two_vertices_quasikernel_cover {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (a b : α) : ∃ Q : Finset α, (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧ (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ z, D.Adj u z ∧ D.Adj z v) ∧ (∃ u ∈ Q, u = a ∨ D.Adj u a) ∧ (∃ u ∈ Q, u = b ∨ D.Adj u b)
- Source
- Two-vertex consequence of Lemma 14 of https://www.combinatorics.org/ojs/index.php/eljc/article/download/v32i2p53/pdf/, with arcs reversed.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
The proof, explained
To show that any two vertices a, b are covered in at most one step by some quasi-kernel, we set S = {a, b} and apply digraph_kernel_perfect_subset_quasikernel_cover, which guarantees such a quasi-kernel whenever every subset of S has a kernel. Since |S| ≤ 2, any subset T ⊆ S has at most two vertices, reducing kernel-perfection on S to a finite case split on edges between a and b. If an edge exists between them, the source vertex forms a dominating singleton kernel for T (or the remaining vertex does if the source is absent from T). If neither edge exists, T contains no edges at all, so T itself serves as an independent dominating kernel.
Let S be the two-element set of vertices {a, b}.
We define S = {a, b} to be the set of the two target vertices and enable classical reasoning for case analysis on edges and set memberships.
classical let S : Finset α := {a,b}Every element of any subset T ⊆ S is either a or b.
We fix an arbitrary subset T ⊆ S. Since S = {a, b}, any vertex v ∈ T belongs to S and therefore must satisfy v = a or v = b.
have hker : ∀ 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) := by intro T hT have hm : ∀ v ∈ T, v = a ∨ v = b := by intro v hv have hvS := hT hv simpa [S] using hvS
If some vertex x ∈ T dominates all vertices of T, then the singleton {x} is a kernel of T.
Choosing K = {x}, the inclusion {x} ⊆ T holds because x ∈ T. The singleton is independent because any two distinct vertices in {x} would have to be equal by Finset.mem_singleton, a contradiction. Furthermore, x dominates every vertex in T by assumption.
uses
Finset.mem_singletonhave hsingle : ∀ x ∈ T, (∀ v ∈ T, x = v ∨ D.Adj x v) → ∃ K : Finset α, K ⊆ T ∧ (∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) ∧ (∀ v ∈ T, ∃ u ∈ K, u = v ∨ D.Adj u v) := by intro x hx hdom refine ⟨{x}, ?_, ?_, ?_⟩ · simpa using hx · intro u hu v hv huv simp only [Finset.mem_singleton] at hu hv subst u; subst v exact (huv rfl).elim · intro v hv exact ⟨x,by simp,hdom v hv⟩
If T is contained in a singleton set {x}, then T itself is a kernel of T.
Setting K = T, the inclusion T ⊆ T holds by reflexivity (Finset.Subset.rfl). Distinct vertices in T cannot exist since Finset.mem_singleton.mp would force both to equal x. Finally, every vertex in T trivially dominates itself via Or.inl.
uses
Finset.Subset.rfl,Finset.mem_singleton.mp,Or.inlhave hsub : ∀ x, T ⊆ {x} → ∃ K : Finset α, K ⊆ T ∧ (∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) ∧ (∀ v ∈ T, ∃ u ∈ K, u = v ∨ D.Adj u v) := by intro x hTx refine ⟨T,Finset.Subset.rfl,?_,?_⟩ · intro u hu v hv huv have hu' : u = x := Finset.mem_singleton.mp (hTx hu) have hv' : v = x := Finset.mem_singleton.mp (hTx hv) subst u; subst v exact (huv rfl).elim · intro v hv exact ⟨v,hv,Or.inl rfl⟩
If there is a directed edge from a to b, then T has a kernel.
We split on whether a ∈ T. If a ∈ T, then a dominates all vertices in T (equal to a via Or.inl, or adjacent to b via Or.inr), so {a} is a kernel. If a ∉ T, then every vertex in T must be b, so T ⊆ {b}, and T itself is a kernel.
uses
Or.inl,Or.inrby_cases hab : D.Adj a b · by_cases ha : a ∈ T · apply hsingle a ha intro v hv rcases hm v hv with rfl | rfl · exact Or.inl rfl · exact Or.inr hab · apply hsub b intro v hv rcases hm v hv with rfl | rfl · exact (ha hv).elim · simp
If there is no edge from a to b but an edge from b to a, then T has a kernel.
Symmetrically, we split on whether b ∈ T. If b ∈ T, then b dominates all vertices in T (adjacent to a via Or.inr, or equal to b via Or.inl), so {b} is a kernel. If b ∉ T, then T ⊆ {a}, so T itself is a kernel.
uses
Or.inl,Or.inr· by_cases hba : D.Adj b a · by_cases hb : b ∈ T · apply hsingle b hb intro v hv rcases hm v hv with rfl | rfl · exact Or.inr hba · exact Or.inl rfl · apply hsub a intro v hv rcases hm v hv with rfl | rfl · simp · exact (hb hv).elim
If there are no directed edges between a and b in either direction, then T itself is a kernel of T, completing the proof that every subset of S has a kernel.
Taking K = T (with T ⊆ T by Finset.Subset.rfl), any edge between distinct vertices would require an edge between a and b, contradicting the absence of edges in both directions. Since every vertex dominates itself via Or.inl, T is independent and dominating.
uses
Finset.Subset.rfl,Or.inl· refine ⟨T,Finset.Subset.rfl,?_,?_⟩ · intro u hu v hv huv hadj rcases hm u hu with rfl | rfl <;> rcases hm v hv with rfl | rfl · exact (huv rfl).elim · exact hab hadj · exact hba hadj · exact (huv rfl).elim · intro v hv exact ⟨v,hv,Or.inl rfl⟩
There exists a quasi-kernel Q whose closed out-neighborhood contains both a and b.
By digraph_kernel_perfect_subset_quasikernel_cover, since every subset of S has a kernel, there is a quasi-kernel Q whose closed out-neighborhood contains all of S. Specializing this coverage to a ∈ S and b ∈ S proves the theorem.
uses
digraph_kernel_perfect_subset_quasikernel_coverobtain ⟨Q,hind,hcov,hfirst,_⟩ := digraph_kernel_perfect_subset_quasikernel_cover D S hker exact ⟨Q,hind,hcov,hfirst a (by simp [S]),hfirst b (by simp [S])⟩
Finset.mem_singleton- an element belongs to a singleton set {a} if and only if it equals a
Finset.mem_singleton.mp- if an element belongs to the singleton {x}, then it equals x
Finset.Subset.rfl- subset inclusion is reflexive for finite sets (s ⊆ s)
Or.inl- proves a disjunction A ∨ B from a proof of the left disjunct A
Or.inr- proves a disjunction A ∨ B from a proof of the right disjunct B
digraph_kernel_perfect_subset_quasikernel_cover- if every subdigraph induced by a subset of S has a kernel, then there exists a quasi-kernel of D covering all of S in at most one step
- The theorem relies on the auxiliary result `digraph_kernel_perfect_subset_quasikernel_cover`, which generalizes the classical kernel-perfection theorem by showing that any subset whose induced subdigraphs all admit kernels can be covered within distance at most 1 by a global quasi-kernel.
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_any_two_vertices_quasikernel_cover {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (a b : α) : ∃ Q : Finset α, (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧ (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ z, D.Adj u z ∧ D.Adj z v) ∧ (∃ u ∈ Q, u = a ∨ D.Adj u a) ∧ (∃ u ∈ Q, u = b ∨ D.Adj u b) := by classical let S : Finset α := {a,b} have hker : ∀ 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) := by intro T hT have hm : ∀ v ∈ T, v = a ∨ v = b := by intro v hv have hvS := hT hv simpa [S] using hvS have hsingle : ∀ x ∈ T, (∀ v ∈ T, x = v ∨ D.Adj x v) → ∃ K : Finset α, K ⊆ T ∧ (∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) ∧ (∀ v ∈ T, ∃ u ∈ K, u = v ∨ D.Adj u v) := by intro x hx hdom refine ⟨{x}, ?_, ?_, ?_⟩ · simpa using hx · intro u hu v hv huv simp only [Finset.mem_singleton] at hu hv subst u; subst v exact (huv rfl).elim · intro v hv exact ⟨x,by simp,hdom v hv⟩ have hsub : ∀ x, T ⊆ {x} → ∃ K : Finset α, K ⊆ T ∧ (∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) ∧ (∀ v ∈ T, ∃ u ∈ K, u = v ∨ D.Adj u v) := by intro x hTx refine ⟨T,Finset.Subset.rfl,?_,?_⟩ · intro u hu v hv huv have hu' : u = x := Finset.mem_singleton.mp (hTx hu) have hv' : v = x := Finset.mem_singleton.mp (hTx hv) subst u; subst v exact (huv rfl).elim · intro v hv exact ⟨v,hv,Or.inl rfl⟩ by_cases hab : D.Adj a b · by_cases ha : a ∈ T · apply hsingle a ha intro v hv rcases hm v hv with rfl | rfl · exact Or.inl rfl · exact Or.inr hab · apply hsub b intro v hv rcases hm v hv with rfl | rfl · exact (ha hv).elim · simp · by_cases hba : D.Adj b a · by_cases hb : b ∈ T · apply hsingle b hb intro v hv rcases hm v hv with rfl | rfl · exact Or.inr hba · exact Or.inl rfl · apply hsub a intro v hv rcases hm v hv with rfl | rfl · simp · exact (hb hv).elim · refine ⟨T,Finset.Subset.rfl,?_,?_⟩ · intro u hu v hv huv hadj rcases hm u hu with rfl | rfl <;> rcases hm v hv with rfl | rfl · exact (huv rfl).elim · exact hab hadj · exact hba hadj · exact (huv rfl).elim · intro v hv exact ⟨v,hv,Or.inl rfl⟩ obtain ⟨Q,hind,hcov,hfirst,_⟩ := digraph_kernel_perfect_subset_quasikernel_cover D S hker exact ⟨Q,hind,hcov,hfirst a (by simp [S]),hfirst b (by simp [S])⟩