digraph_minimum_quasikernel_independent_outneighbors_bound
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
- digraph_quasikernel_outneighborsThe first out-neighborhood of a finite set of vertices in a digraph.
- digraph_quasikernel_outneighbors_two_dominateIn a finite loopless source-free digraph, the out-neighborhood of an independent two-step out-dominating set is itself two-step…
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)|.
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)|.
uses
digraph_quasikernel_outneighbors_two_dominateexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)