AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_outneighbors_two_dominate

theoremverified

In a finite loopless source-free digraph, the out-neighborhood of an independent two-step out-dominating set is itself two-step out-dominating.

Statement

theorem digraph_quasikernel_outneighbors_two_dominate
    {α : 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) :
    ∀ v, ∃ b ∈ digraph_quasikernel_outneighbors D Q,
      b = v ∨ D.Adj b v ∨ ∃ w, D.Adj b w ∧ D.Adj w v
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 1
Used by 1

The proof, explained

To show that the out-neighborhood B of an independent two-step dominating set Q is itself two-step dominating, we first establish that any vertex outside Q is one-step dominated by B (either belonging to B or having an in-neighbor in B). For an arbitrary vertex v, we then split on whether v ∈ Q. If v ∉ Q, the one-step domination property applies directly; if v ∈ Q, the source-free condition provides an in-neighbor p of v, which cannot lie in Q due to looplessness and the independence of Q. Applying the one-step property to p ∉ Q then yields a directed path of length 1 or 2 from B to v.

  1. A vertex belongs to the out-neighborhood B = digraph_quasikernel_outneighbors D Q if and only if it is an out-neighbor of some vertex in Q.

    We enable classical reasoning and unfold the definition of digraph_quasikernel_outneighbors, which defines B as the set of all vertices v that have an incoming edge from some vertex q ∈ Q.

    lines 10–12

      classical
      have hmem : ∀ {v}, v ∈ digraph_quasikernel_outneighbors D Q ↔ ∃ q ∈ Q, D.Adj q v := by
        intro v; simp [digraph_quasikernel_outneighbors]
  2. Every vertex outside Q is one-step out-dominated by B: for any y ∉ Q, either y ∈ B or some vertex b ∈ B has an edge b → y.

    Let y ∉ Q. By the two-step domination hypothesis for Q (hcover), there is some q ∈ Q such that q = y, q → y, or q → b → y for some vertex b. Since y ∉ Q, the case q = y is impossible. If q → y, then y ∈ B by definition. If q → b → y, then b ∈ B (as q ∈ Q with q → b), so b provides the required edge b → y from B.

    lines 13–20

    uses Or.inl, Or.inr

      have houtside : ∀ y, y ∉ Q → y ∈ digraph_quasikernel_outneighbors D Q ∨
          ∃ b ∈ digraph_quasikernel_outneighbors D Q, D.Adj b y := by
        intro y hy
        obtain ⟨q,hq,hd⟩ := hcover y
        rcases hd with heq | ha | ⟨b,hqb,hby⟩
        · subst q; exact (hy hq).elim
        · exact Or.inl (hmem.mpr ⟨q,hq,ha⟩)
        · exact Or.inr ⟨b,hmem.mpr ⟨q,hq,hqb⟩,hby⟩
  3. Every vertex v ∈ Q is two-step out-dominated by B.

    Let v ∈ Q. Since the digraph has no sources (hsource), v has an in-neighbor p with p → v. This in-neighbor p cannot belong to Q: if p = v, this would contradict the loopless condition (hloop), and if p ≠ v, the directed edge p → v between distinct elements of Q would contradict independence (hind). Since p ∉ Q, we apply the one-step domination lemma (houtside) to p. This yields either p ∈ B (giving the 1-step edge p → v from B) or some b ∈ B with b → p (giving the 2-step path b → p → v from B).

    lines 21–31

    uses Or.inl, Or.inr

      intro v
      by_cases hv : v ∈ Q
      · obtain ⟨p,hpv⟩ := hsource v
        have hpQ : p ∉ Q := by
          intro hp
          by_cases hpv' : p = v
          · subst p; exact hloop v hpv
          · exact hind p hp v hv hpv' hpv
        rcases houtside p hpQ with hpB | ⟨b,hb,hbp⟩
        · exact ⟨p,hpB,Or.inr (Or.inl hpv)⟩
        · exact ⟨b,hb,Or.inr (Or.inr ⟨p,hbp,hpv⟩)⟩
  4. Every vertex v ∉ Q is two-step out-dominated by B (in fact, in at most one step), completing the proof.

    If v ∉ Q, applying the one-step domination lemma (houtside) directly to v shows that either v ∈ B (a 0-step domination where b = v) or some b ∈ B satisfies b → v (a 1-step domination). In both cases, v is two-step out-dominated by B.

    lines 32–34

    uses Or.inl, Or.inr

      · rcases houtside v hv with hvB | ⟨b,hb,hbv⟩
        · exact ⟨v,hvB,Or.inl rfl⟩
        · exact ⟨b,hb,Or.inr (Or.inl hbv)⟩
Or.inl
Given a proof of a proposition a, proves the disjunction a ∨ b.
Or.inr
Given a proof of a proposition b, proves the disjunction a ∨ b.

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_quasikernel_outneighbors_two_dominate    {α : 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) :    ∀ v, ∃ b ∈ digraph_quasikernel_outneighbors D Q,      b = v ∨ D.Adj b v ∨ ∃ w, D.Adj b w ∧ D.Adj w v := by  classical  have hmem : ∀ {v}, v ∈ digraph_quasikernel_outneighbors D Q ↔ ∃ q ∈ Q, D.Adj q v := by    intro v; simp [digraph_quasikernel_outneighbors]  have houtside : ∀ y, y ∉ Q → y ∈ digraph_quasikernel_outneighbors D Q ∨      ∃ b ∈ digraph_quasikernel_outneighbors D Q, D.Adj b y := by    intro y hy    obtain ⟨q,hq,hd⟩ := hcover y    rcases hd with heq | ha | ⟨b,hqb,hby⟩    · subst q; exact (hy hq).elim    · exact Or.inl (hmem.mpr ⟨q,hq,ha⟩)    · exact Or.inr ⟨b,hmem.mpr ⟨q,hq,hqb⟩,hby⟩  intro v  by_cases hv : v ∈ Q  · obtain ⟨p,hpv⟩ := hsource v    have hpQ : p ∉ Q := by      intro hp      by_cases hpv' : p = v      · subst p; exact hloop v hpv      · exact hind p hp v hv hpv' hpv    rcases houtside p hpQ with hpB | ⟨b,hb,hbp⟩    · exact ⟨p,hpB,Or.inr (Or.inl hpv)⟩    · exact ⟨b,hb,Or.inr (Or.inr ⟨p,hbp,hpv⟩)⟩  · rcases houtside v hv with hvB | ⟨b,hb,hbv⟩    · exact ⟨v,hvB,Or.inl rfl⟩    · exact ⟨b,hb,Or.inr (Or.inl hbv)⟩
See it in the graphDiscuss this resultChallenge it