digraph_quasikernel_redundant_neighbor_three_path
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.
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.
uses
Finset.mem_erase.mpr,Or.inl,Or.inrclassical 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⟩
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.
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
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.
obtain ⟨x, hxq⟩ := hsource qThe 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.
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
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}.
uses
Finset.mem_erase.mpr,Or.inrhave 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⟩)⟩
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.
uses
Finset.mem_erase.mprobtain ⟨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
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_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⟩