digraph_quasikernel_outneighbors_two_dominate
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
- digraph_quasikernel_outneighborsThe first out-neighborhood of a finite set of vertices in a digraph.
- Used by 1
- digraph_minimum_quasikernel_independent_outneighbors_boundIf a minimum quasi-kernel in a finite loopless source-free digraph has an independent first out-neighborhood, that neighborhood has at…
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.
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.
classical have hmem : ∀ {v}, v ∈ digraph_quasikernel_outneighbors D Q ↔ ∃ q ∈ Q, D.Adj q v := by intro v; simp [digraph_quasikernel_outneighbors]
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.
uses
Or.inl,Or.inrhave 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⟩
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).
uses
Or.inl,Or.inrintro 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⟩)⟩
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.
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
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_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)⟩