AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_redundant_neighbor_three_path

theoremverified

For an inclusion-minimal quasi-kernel in a source-free loopless digraph, a member whose first out-neighbors are all shared with other members is reached from another member by a directed three-step walk whose penultimate vertex lies outside the quasi-kernel and its first out-neighborhood.

Statement

theorem digraph_quasikernel_redundant_neighbor_three_path
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (Q : Finset α) (q : α)
    (hq : q ∈ Q)
    (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 : ¬ ∀ v, ∃ u ∈ Q.erase q,
        u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v)
    (hredundant : ∀ b, D.Adj q b → ∃ r ∈ Q.erase q, D.Adj r b) :
    ∃ r ∈ Q.erase q, ∃ b x, D.Adj r b ∧ D.Adj b x ∧ D.Adj x q ∧
       x ∉ Q ∧ (∀ s ∈ Q, ¬ D.Adj s x)
Source
Auxiliary lemma for the OP-337 campaign; standard finite digraph definitions and quasi-kernel exchange.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

Because Q \\ {q} cannot quasi-cover the digraph by minimality, but covers every vertex other than q due to the redundancy of q's out-neighbors, q itself cannot be reached from Q \\ {q} in two or fewer steps. Since the digraph has no sources, q has an in-neighbor x, which cannot lie in Q by independence and cannot be pointed to by any vertex in Q without placing q within two steps of Q \\ {q}. Therefore, when Q covers x, it must do so via a two-step path through some vertex b, which (after replacing q by a redundant partner if needed) completes a directed three-step walk from Q \\ {q} to q whose penultimate vertex x is outside Q and has no in-neighbors in Q.

  1. Every vertex other than q is reached from Q \\ {q} in at most two steps.

    By the quasi-covering hypothesis (hcover), any vertex v ≠ q is reached in at most two steps from some u ∈ Q. If u ≠ q, then u ∈ Q \\ {q} and already covers v. If u = q, then v cannot equal q since v ≠ q. If q has an edge to v, the redundancy hypothesis (hredundant) provides an r ∈ Q \\ {q} adjacent to v. If q reaches v via a two-step path q → w → v, redundancy on w provides an r ∈ Q \\ {q} adjacent to w, yielding a two-step path r → w → v from Q \\ {q} to v.

    lines 14–27

    uses Finset.mem_erase.mpr, Or.inl, Or.inr

      classical
      have hother : ∀ v, v ≠ q → ∃ u ∈ Q.erase q,
          u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v := by
        intro v hv
        obtain ⟨u, hu, hd⟩ := hcover v
        by_cases huq : u = q
        · subst u
          rcases hd with heq | ha | ⟨w, haw, hwv⟩
          · exact (hv heq.symm).elim
          · obtain ⟨r, hr, hrv⟩ := hredundant v ha
            exact ⟨r, hr, Or.inr (Or.inl hrv)⟩
          · obtain ⟨r, hr, hrw⟩ := hredundant w haw
            exact ⟨r, hr, Or.inr (Or.inr ⟨w, hrw, hwv⟩)⟩
        · exact ⟨u, Finset.mem_erase.mpr ⟨huq, hu⟩, hd⟩
  2. The vertex q cannot be reached from Q \\ {q} in at most two steps.

    Suppose for contradiction that some u ∈ Q \\ {q} reaches q in at most two steps. Combining this with the previous step showing that every v ≠ q is covered by Q \\ {q}, all vertices of the digraph would be quasi-covered by Q \\ {q}. This contradicts the minimality hypothesis (hmin), which states that Q \\ {q} does not quasi-cover the digraph.

    lines 28–35

      have hqnot : ¬ ∃ u ∈ Q.erase q,
          u = q ∨ D.Adj u q ∨ ∃ w, D.Adj u w ∧ D.Adj w q := by
        intro h
        apply hmin
        intro v
        by_cases hv : v = q
        · simpa [hv] using h
        · exact hother v hv
  3. There exists an in-neighbor x of q (an edge x → q).

    Because the digraph has no sources (hsource), there is at least one vertex x with a directed edge x → q.

    line 36

      obtain ⟨x, hxq⟩ := hsource q
  4. The in-neighbor x does not belong to Q.

    Suppose x ∈ Q. If x = q, the edge x → q is a self-loop at q, contradicting looplessness (hloop). If x ≠ q, then x and q are distinct vertices in Q with an edge x → q, contradicting the independent set property of Q (hind). Therefore, x ∉ Q.

    lines 37–41

      have hxQ : x ∉ Q := by
        intro hx
        by_cases hxq' : x = q
        · subst x; exact hloop q hxq
        · exact hind x hx q hq hxq' hxq
  5. No vertex in Q has a directed edge to x.

    Suppose some s ∈ Q is adjacent to x (s → x). If s = q, redundancy of q's out-neighbors (hredundant) yields some r ∈ Q \\ {q} with r → x, giving a two-step path r → x → q. If s ≠ q, then s ∈ Q \\ {q} already gives a two-step path s → x → q. In either case, q is reached from Q \\ {q} in two steps, contradicting the fact that q cannot be quasi-covered by Q \\ {q}.

    lines 42–49

    uses Finset.mem_erase.mpr, Or.inr

      have hxfirst : ∀ s ∈ Q, ¬ D.Adj s x := by
        intro s hs hsx
        by_cases hsq : s = q
        · subst s
          obtain ⟨r, hr, hrx⟩ := hredundant x hsx
          exact hqnot ⟨r, hr, Or.inr (Or.inr ⟨x, hrx, hxq⟩)⟩
        · exact hqnot ⟨s, Finset.mem_erase.mpr ⟨hsq, hs⟩,
            Or.inr (Or.inr ⟨x, hsx, hxq⟩)⟩
  6. There exist r ∈ Q \\ {q} and vertices b, x forming a directed three-step walk r → b → x → q, where x ∉ Q and no vertex in Q points to x.

    Applying the quasi-covering hypothesis (hcover) to x, some s ∈ Q must reach x in 0, 1, or 2 steps. The distance cannot be 0 because x ∉ Q, nor 1 because no vertex in Q points to x. Thus s reaches x in two steps via some intermediate vertex b, giving s → b → x. If s ≠ q, then s ∈ Q \\ {q} and the walk s → b → x → q satisfies all conditions. If s = q, redundancy on b yields an r ∈ Q \\ {q} with r → b, giving the walk r → b → x → q.

    lines 50–59

    uses Finset.mem_erase.mpr

      obtain ⟨s, hs, hsx⟩ := hcover x
      rcases hsx with heq | ha | ⟨b, hsb, hbx⟩
      · subst s; exact (hxQ hs).elim
      · exact (hxfirst s hs ha).elim
      · by_cases hsq : s = q
        · subst s
          obtain ⟨r, hr, hrb⟩ := hredundant b hsb
          exact ⟨r, hr, b, x, hrb, hbx, hxq, hxQ, hxfirst⟩
        · exact ⟨s, Finset.mem_erase.mpr ⟨hsq, hs⟩, b, x,
            hsb, hbx, hxq, hxQ, hxfirst⟩
Finset.mem_erase.mpr
If a ≠ b and a ∈ s, then a ∈ s \\ {b}.
Or.inl
If a holds, then a ∨ b holds.
Or.inr
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_quasikernel_redundant_neighbor_three_path    {α : Type} [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] (Q : Finset α) (q : α)    (hq : q ∈ Q)    (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 : ¬ ∀ v, ∃ u ∈ Q.erase q,        u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v)    (hredundant : ∀ b, D.Adj q b → ∃ r ∈ Q.erase q, D.Adj r b) :    ∃ r ∈ Q.erase q, ∃ b x, D.Adj r b ∧ D.Adj b x ∧ D.Adj x q ∧       x ∉ Q ∧ (∀ s ∈ Q, ¬ D.Adj s x) := by  classical  have hother : ∀ v, v ≠ q → ∃ u ∈ Q.erase q,      u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v := by    intro v hv    obtain ⟨u, hu, hd⟩ := hcover v    by_cases huq : u = q    · subst u      rcases hd with heq | ha | ⟨w, haw, hwv⟩      · exact (hv heq.symm).elim      · obtain ⟨r, hr, hrv⟩ := hredundant v ha        exact ⟨r, hr, Or.inr (Or.inl hrv)⟩      · obtain ⟨r, hr, hrw⟩ := hredundant w haw        exact ⟨r, hr, Or.inr (Or.inr ⟨w, hrw, hwv⟩)⟩    · exact ⟨u, Finset.mem_erase.mpr ⟨huq, hu⟩, hd⟩  have hqnot : ¬ ∃ u ∈ Q.erase q,      u = q ∨ D.Adj u q ∨ ∃ w, D.Adj u w ∧ D.Adj w q := by    intro h    apply hmin    intro v    by_cases hv : v = q    · simpa [hv] using h    · exact hother v hv  obtain ⟨x, hxq⟩ := hsource q  have hxQ : x ∉ Q := by    intro hx    by_cases hxq' : x = q    · subst x; exact hloop q hxq    · exact hind x hx q hq hxq' hxq  have hxfirst : ∀ s ∈ Q, ¬ D.Adj s x := by    intro s hs hsx    by_cases hsq : s = q    · subst s      obtain ⟨r, hr, hrx⟩ := hredundant x hsx      exact hqnot ⟨r, hr, Or.inr (Or.inr ⟨x, hrx, hxq⟩)⟩    · exact hqnot ⟨s, Finset.mem_erase.mpr ⟨hsq, hs⟩,        Or.inr (Or.inr ⟨x, hsx, hxq⟩)⟩  obtain ⟨s, hs, hsx⟩ := hcover x  rcases hsx with heq | ha | ⟨b, hsb, hbx⟩  · subst s; exact (hxQ hs).elim  · exact (hxfirst s hs ha).elim  · by_cases hsq : s = q    · subst s      obtain ⟨r, hr, hrb⟩ := hredundant b hsb      exact ⟨r, hr, b, x, hrb, hbx, hxq, hxQ, hxfirst⟩    · exact ⟨s, Finset.mem_erase.mpr ⟨hsq, hs⟩, b, x,        hsb, hbx, hxq, hxQ, hxfirst⟩
See it in the graphDiscuss this resultChallenge it