digraph_nonneighbor_kernel_or_dominating_vertex
theoremverified
Given an out-kernel K of the non-neighbors of a vertex v, either {v}∪K is a quasi-kernel or there is a distinct vertex w pointing to v whose in-neighbors all point to v too.
Statement
theorem digraph_nonneighbor_kernel_or_dominating_vertex {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (v : α) (K : Finset α) (hK : ∀ x ∈ K, x ≠ v ∧ ¬ D.Adj x v ∧ ¬ D.Adj v x) (hind : ∀ x ∈ K, ∀ y ∈ K, x ≠ y → ¬ D.Adj x y) (hdom : ∀ x, x ≠ v → ¬ D.Adj x v → ¬ D.Adj v x → ∃ k ∈ K, k = x ∨ D.Adj k x) : ((∀ x ∈ insert v K, ∀ y ∈ insert v K, x ≠ y → ¬ D.Adj x y) ∧ (∀ x, ∃ q ∈ insert v K, q = x ∨ D.Adj q x ∨ ∃ z, D.Adj q z ∧ D.Adj z x)) ∨ ∃ w, w ≠ v ∧ D.Adj w v ∧ ∀ z, D.Adj z w → D.Adj z v
- Source
- Proof of Theorem 3.4, step (1), in https://people.maths.ox.ac.uk/~scott/Papers/2kernels.pdf; only the kernel of the non-neighborhood is used, and no novelty is claimed.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- digraph_nonneighborhood_kernel_neighborhood_liftIn a finite loopless oriented graph where the non-neighbors of every vertex admit an out-kernel, every vertex has a quasi-kernel whose…
- digraph_nonneighborhood_kernels_weighted_half_coverIn a finite loopless oriented graph in which the induced non-neighborhood of every vertex has an out-kernel, every nonnegative integer…
Lean source view module on GitHub
theorem digraph_nonneighbor_kernel_or_dominating_vertex {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (v : α) (K : Finset α) (hK : ∀ x ∈ K, x ≠ v ∧ ¬ D.Adj x v ∧ ¬ D.Adj v x) (hind : ∀ x ∈ K, ∀ y ∈ K, x ≠ y → ¬ D.Adj x y) (hdom : ∀ x, x ≠ v → ¬ D.Adj x v → ¬ D.Adj v x → ∃ k ∈ K, k = x ∨ D.Adj k x) : ((∀ x ∈ insert v K, ∀ y ∈ insert v K, x ≠ y → ¬ D.Adj x y) ∧ (∀ x, ∃ q ∈ insert v K, q = x ∨ D.Adj q x ∨ ∃ z, D.Adj q z ∧ D.Adj z x)) ∨ ∃ w, w ≠ v ∧ D.Adj w v ∧ ∀ z, D.Adj z w → D.Adj z v := by classical by_cases hq : ∀ x, ∃ q ∈ insert v K, q = x ∨ D.Adj q x ∨ ∃ z, D.Adj q z ∧ D.Adj z x · left refine ⟨?_, hq⟩ intro x hx y hy hxy rcases Finset.mem_insert.mp hx with hxv | hxK · subst x rcases Finset.mem_insert.mp hy with hyv | hyK · subst y exact (hxy rfl).elim · exact (hK y hyK).2.2 · rcases Finset.mem_insert.mp hy with hyv | hyK · subst y exact (hK x hxK).2.1 · exact hind x hxK y hyK hxy · right obtain ⟨w, hw⟩ := not_forall.mp hq have hne : w ≠ v := by intro h subst w apply hw exact ⟨v, by simp, Or.inl rfl⟩ have hvw : ¬ D.Adj v w := by intro h apply hw exact ⟨v, by simp, Or.inr (Or.inl h)⟩ have hwv : D.Adj w v := by by_contra h obtain ⟨k, hk, hkw⟩ := hdom w hne h hvw apply hw exact ⟨k, Finset.mem_insert_of_mem hk, hkw.elim Or.inl (fun h => Or.inr (Or.inl h))⟩ refine ⟨w, hne, hwv, ?_⟩ intro z hzw by_contra hzv have hzneq : z ≠ v := by intro h subst z exact hvw hzw have hvz : ¬ D.Adj v z := by intro h apply hw exact ⟨v, by simp, Or.inr (Or.inr ⟨z, h, hzw⟩)⟩ obtain ⟨k, hk, hkz⟩ := hdom z hzneq hzv hvz apply hw refine ⟨k, Finset.mem_insert_of_mem hk, ?_⟩ rcases hkz with rfl | hkz · exact Or.inr (Or.inl hzw) · exact Or.inr (Or.inr ⟨z, hkz, hzw⟩)