AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_outneighbors

def

The first out-neighborhood of a finite set of vertices in a digraph.

Statement

def digraph_quasikernel_outneighbors {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (Q : Finset α) : Finset α
Source
Auxiliary lemma for the OP-337 campaign; standard finite digraph definitions and quasi-kernel exchange.
Verified
03 Nov 2026
Axioms
none listed
Used by 2

Lean source view module on GitHub

def digraph_quasikernel_outneighbors {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (Q : Finset α) : Finset α :=
  Finset.univ.filter fun v => ∃ q ∈ Q, D.Adj q v

-- In a source-free digraph the first out-neighborhood of any quasi-kernel
-- is itself two-step out-dominating, even when it is not independent.
See it in the graphDiscuss this resultChallenge it