AFTD Auto-Formalizing Theoretical Domains

digraph_minimum_quasikernel_independent_outneighbors_bound

theoremverified

If a minimum quasi-kernel in a finite loopless source-free digraph has an independent first out-neighborhood, that neighborhood has at least as many vertices as the quasi-kernel.

Statement

theorem digraph_minimum_quasikernel_independent_outneighbors_bound
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (Q : Finset α)
    (hloop : ∀ v, ¬ D.Adj v v)
    (hsource : ∀ v, ∃ u, D.Adj u v)
    (hind : ∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v)
    (hcover : ∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v)
    (hmin : ∀ P : Finset α,
      (∀ u ∈ P, ∀ v ∈ P, u ≠ v → ¬ D.Adj u v) →
      (∀ v, ∃ u ∈ P, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) →
      Q.card ≤ P.card)
    (hNind : ∀ u ∈ digraph_quasikernel_outneighbors D Q,
      ∀ v ∈ digraph_quasikernel_outneighbors D Q, u ≠ v → ¬ D.Adj u v) :
    Q.card ≤ (digraph_quasikernel_outneighbors D Q).card
Source
Auxiliary lemma for the OP-337 campaign; standard finite digraph definitions and quasi-kernel exchange.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

To show that the out-neighborhood N⁺(Q) has cardinality at least |Q|, we observe that N⁺(Q) is itself a quasi-kernel. By digraph_quasikernel_outneighbors_two_dominate, the out-neighborhood of a quasi-kernel in a loopless, source-free digraph is always two-step dominating. Since N⁺(Q) is additionally assumed to be independent, it satisfies the definition of a quasi-kernel, and the minimality of Q immediately yields |Q| ≤ |N⁺(Q)|.

  1. The cardinality of Q is at most the cardinality of its first out-neighborhood N⁺(Q).

    By the minimality assumption hmin, any independent set that two-step dominates the digraph has cardinality at least |Q|. The out-neighborhood N⁺(Q) is assumed to be independent by hNind, and by digraph_quasikernel_outneighbors_two_dominate, it is two-step dominating in any loopless, source-free digraph. Thus, N⁺(Q) is itself a quasi-kernel, so applying hmin with P = N⁺(Q) yields |Q| ≤ |N⁺(Q)|.

    line 15

    uses digraph_quasikernel_outneighbors_two_dominate

      exact hmin _ hNind (digraph_quasikernel_outneighbors_two_dominate D Q hloop hsource hind hcover)
digraph_quasikernel_outneighbors_two_dominate
In a finite, loopless, source-free directed graph, the first out-neighborhood of any quasi-kernel is two-step dominating.

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_minimum_quasikernel_independent_outneighbors_bound    {α : Type} [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] (Q : Finset α)    (hloop : ∀ v, ¬ D.Adj v v)    (hsource : ∀ v, ∃ u, D.Adj u v)    (hind : ∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v)    (hcover : ∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v)    (hmin : ∀ P : Finset α,      (∀ u ∈ P, ∀ v ∈ P, u ≠ v → ¬ D.Adj u v) →      (∀ v, ∃ u ∈ P, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) →      Q.card ≤ P.card)    (hNind : ∀ u ∈ digraph_quasikernel_outneighbors D Q,      ∀ v ∈ digraph_quasikernel_outneighbors D Q, u ≠ v → ¬ D.Adj u v) :    Q.card ≤ (digraph_quasikernel_outneighbors D Q).card := by  exact hmin _ hNind (digraph_quasikernel_outneighbors_two_dominate D Q hloop hsource hind hcover)
See it in the graphDiscuss this resultChallenge it