AFTD Auto-Formalizing Theoretical Domains

digraph_kernel_perfect_subset_quasikernel_cover

theoremverifiedformalization

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

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.

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

    lines 13–18

    uses digraph_quasikernel_on_subset, Finset.filter_subset

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

    lines 19–27

    uses Finset.mem_union_left, Or.inr, Finset.mem_filter.mpr, Finset.mem_union_right

      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, ?_⟩
  3. 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).

    lines 28–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
  4. 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).

    lines 35–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⟩)⟩
  5. 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).

    lines 60–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.

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