AFTD Auto-Formalizing Theoretical Domains

digraph_any_two_vertices_quasikernel_cover

theoremverified

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

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.

  1. 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.

    lines 9–10

      classical
      let S : Finset α := {a,b}
  2. 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.

    lines 11–19

      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
  3. 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.

    lines 20–32

    uses Finset.mem_singleton

        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⟩
  4. 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.

    lines 33–44

    uses Finset.Subset.rfl, Finset.mem_singleton.mp, Or.inl

        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⟩
  5. 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.

    lines 45–56

    uses Or.inl, Or.inr

        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
  6. 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.

    lines 57–68

    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
  7. 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.

    lines 69–77

    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⟩
  8. 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.

    lines 78–79

    uses digraph_kernel_perfect_subset_quasikernel_cover

      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])⟩
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

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

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])⟩
See it in the graphDiscuss this resultChallenge it