AFTD Auto-Formalizing Theoretical Domains

digraph_delete_dominated_vertex_quasikernel_lift

theoremverified

If a vertex w points to v and every in-neighbor of w also points to v, then every quasi-kernel after deleting v remains a quasi-kernel when v is restored; direct coverage of w also covers v.

Statement

theorem digraph_delete_dominated_vertex_quasikernel_lift
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (v w : α) (hne : w ≠ v)
    (hwv : D.Adj w v) (hin : ∀ z, D.Adj z w → D.Adj z v)
    (Q : Finset α) (hnot : v ∉ Q)
    (hind : ∀ x ∈ Q, ∀ y ∈ Q, x ≠ y → ¬ D.Adj x y)
    (hsub : ∀ x, x ≠ v → ∃ q ∈ Q,
      q = x ∨ D.Adj q x ∨ ∃ z, z ≠ v ∧ D.Adj q z ∧ D.Adj z x) :
    (∀ x ∈ Q, ∀ y ∈ Q, x ≠ y → ¬ D.Adj x y) ∧
    (∀ x, ∃ q ∈ Q, q = x ∨ D.Adj q x ∨ ∃ z, D.Adj q z ∧ D.Adj z x) ∧
    ((∃ q ∈ Q, q = w ∨ D.Adj q w) → ∃ q ∈ Q, q = v ∨ D.Adj q 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

Lean source view module on GitHub

theorem digraph_delete_dominated_vertex_quasikernel_lift
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (v w : α) (hne : w ≠ v)
    (hwv : D.Adj w v) (hin : ∀ z, D.Adj z w → D.Adj z v)
    (Q : Finset α) (hnot : v ∉ Q)
    (hind : ∀ x ∈ Q, ∀ y ∈ Q, x ≠ y → ¬ D.Adj x y)
    (hsub : ∀ x, x ≠ v → ∃ q ∈ Q,
      q = x ∨ D.Adj q x ∨ ∃ z, z ≠ v ∧ D.Adj q z ∧ D.Adj z x) :
    (∀ x ∈ Q, ∀ y ∈ Q, x ≠ y → ¬ D.Adj x y) ∧
    (∀ x, ∃ q ∈ Q, q = x ∨ D.Adj q x ∨ ∃ z, D.Adj q z ∧ D.Adj z x) ∧
    ((∃ q ∈ Q, q = w ∨ D.Adj q w) → ∃ q ∈ Q, q = v ∨ D.Adj q v) := by
  refine ⟨hind, ?_, ?_⟩
  · intro x
    by_cases hx : x = v
    · subst x
      obtain ⟨q, hq, h⟩ := hsub w hne
      rcases h with h | h | ⟨z, _, hqz, hzw⟩
      · subst q
        exact ⟨w, hq, Or.inr (Or.inl hwv)⟩
      · exact ⟨q, hq, Or.inr (Or.inl (hin q h))⟩
      · exact ⟨q, hq, Or.inr (Or.inr ⟨z, hqz, hin z hzw⟩)⟩
    · obtain ⟨q, hq, h⟩ := hsub x hx
      rcases h with h | h | ⟨z, _, hqz, hzx⟩
      · exact ⟨q, hq, Or.inl h⟩
      · exact ⟨q, hq, Or.inr (Or.inl h)⟩
      · exact ⟨q, hq, Or.inr (Or.inr ⟨z, hqz, hzx⟩)⟩
  · rintro ⟨q, hq, h | h⟩
    · subst q
      exact ⟨w, hq, Or.inr hwv⟩
    · exact ⟨q, hq, Or.inr (hin q h)⟩
See it in the graphDiscuss this resultChallenge it