digraph_quasikernel_vertex_exchange
One vertex can replace a subset of a quasi-kernel when independence holds and its insertion preserves the first out-neighborhood of each removed vertex; the resulting set is a quasi-kernel with the stated cardinality.
Statement
theorem digraph_quasikernel_vertex_exchange {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (Q C : Finset α) (x : α) (hCQ : C ⊆ Q) (hxQ : x ∉ Q) (hx_in : ∀ q ∈ Q, ¬ D.Adj q x) (hx_out : ∀ q ∈ Q \ C, ¬ D.Adj x q) (hxC : ∀ q ∈ C, D.Adj x q) (hkeep : ∀ q ∈ C, ∀ v, D.Adj q v → ∃ r ∈ insert x (Q \ C), D.Adj r 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) : let P := insert x (Q \ C) (∀ 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) ∧ P.card + C.card = Q.card + 1
- Source
- Auxiliary lemma for the OP-337 campaign; standard finite digraph definitions and quasi-kernel exchange.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- digraph_minimum_quasikernel_exchange_obstructionIf a vertex can independently replace at least two members of a minimum quasi-kernel, then an out-neighbor of the removed members is not…
The proof, explained
To show that replacing a subset C ⊆ Q of a quasi-kernel Q with a single vertex x produces a new quasi-kernel P = insert x (Q \ C), the proof verifies independence, quasi-domination, and the cardinality formula. Independence holds because x has no in-edges from Q and no out-edges to Q \ C, while Q \ C inherits independence from Q. Quasi-domination holds because every vertex covered by a removed vertex u ∈ C is re-covered either directly by x (if u = v) or via the hypothesis hkeep which preserves the first out-neighborhood of C in P. Finally, the cardinality formula |P| + |C| = |Q| + 1 follows directly from x ∉ Q \ C and C ⊆ Q.
x ∉ Q \ C, and the goal reduces to proving independence of P, quasi-domination by P, and the cardinality formula for P.
Unfolding P = insert x (Q \ C), since x ∉ Q by assumption hxQ, x cannot belong to the subset Q \ C (Finset.mem_sdiff.mp). A constructor then splits the goal into the independence of P and the conjunction of the remaining two claims.
uses
Finset.mem_sdiff.mpclassical dsimp only have hxR : x ∉ Q \ C := fun h => hxQ (Finset.mem_sdiff.mp h).1 constructor
For distinct u, v ∈ P, there is no directed edge from u to v when u = x.
Let u, v ∈ P be distinct vertices. Decomposing u ∈ insert x (Q \ C) via Finset.mem_insert.mp, consider the case u = x. Decomposing v similarly, the subcase v = x is impossible since u ≠ v. In the remaining subcase v ∈ Q \ C, hypothesis hx_out directly states that x has no directed edge to any vertex in Q \ C.
uses
Finset.mem_insert.mp· intro u hu v hv huv rcases Finset.mem_insert.mp hu with hu | hu · subst u rcases Finset.mem_insert.mp hv with hv | hv · exact (huv hv.symm).elim · exact hx_out v hv
P is an independent set: for any distinct u, v ∈ P, there is no directed edge from u to v.
Now consider u ∈ Q \ C. If v = x, no edge u → x exists by hx_in because u ∈ Q (Finset.mem_sdiff.mp). If v ∈ Q \ C, both u and v belong to Q with u ≠ v, so u → v is ruled out by the independence of Q (hind). This completes the proof that P is independent.
uses
Finset.mem_insert.mp,Finset.mem_sdiff.mp· rcases Finset.mem_insert.mp hv with hv | hv · subst v; exact hx_in u (Finset.mem_sdiff.mp hu).1 · exact hind u (Finset.mem_sdiff.mp hu).1 v (Finset.mem_sdiff.mp hv).1 huv
To establish quasi-domination of P, let v be an arbitrary vertex; there exists u ∈ Q covering v within distance at most 2.
A constructor separates the quasi-domination goal from the cardinality goal. For any vertex v, the quasi-dominating hypothesis for Q (hcover) guarantees the existence of some u ∈ Q such that u = v, u → v, or u → w → v for some intermediate vertex w.
constructor · intro v obtain ⟨u,hu,hd⟩ := hcover v
P is quasi-dominating: every vertex is covered by a vertex in P within distance at most 2.
We split on whether the covering vertex u belongs to C: • If u ∈ C: - If u = v, then v ∈ C, so x → v by hxC, meaning x ∈ P covers v at distance 1 (Finset.mem_insert_self). - If u → v, hypothesis hkeep supplies r ∈ P with r → v, covering v at distance 1. - If u → w → v, applying hkeep to the edge u → w supplies r ∈ P with r → w, so r → w → v covers v at distance 2. • If u ∉ C: then u ∈ Q \ C ⊆ P by Finset.mem_sdiff.mpr and Finset.mem_insert_of_mem, so u itself is a vertex of P that covers v along the same path.
uses
Finset.mem_insert_self,Finset.mem_sdiff.mpr,Finset.mem_insert_of_memby_cases huC : u ∈ C · rcases hd with heq | ha | ⟨w,haw,hwv⟩ · subst u exact ⟨x, Finset.mem_insert_self _ _, Or.inr (Or.inl (hxC v huC))⟩ · obtain ⟨r,hr,hrv⟩ := hkeep u huC v ha exact ⟨r, hr, Or.inr (Or.inl hrv)⟩ · obtain ⟨r,hr,hrw⟩ := hkeep u huC w haw exact ⟨r, hr, Or.inr (Or.inr ⟨w,hrw,hwv⟩)⟩ · exact ⟨u, Finset.mem_insert_of_mem (Finset.mem_sdiff.mpr ⟨hu,huC⟩),hd⟩
|P| + |C| = |Q| + 1.
Because x ∉ Q \ C, |P| = |Q \ C| + 1 by Finset.card_insert_of_notMem. Since C ⊆ Q, |Q \ C| = |Q| - |C| by Finset.card_sdiff_of_subset. Finally, |C| ≤ |Q| by Finset.card_le_card, allowing linear natural-number arithmetic (omega) to conclude that (|Q| - |C| + 1) + |C| = |Q| + 1.
uses
Finset.card_insert_of_notMem,Finset.card_sdiff_of_subset,Finset.card_le_card· rw [Finset.card_insert_of_notMem hxR, Finset.card_sdiff_of_subset hCQ] have := Finset.card_le_card hCQ omega
Finset.mem_sdiff.mp- An element in a set difference s \ t belongs to s and does not belong to t.
Finset.mem_insert.mp- An element in insert b s is either equal to b or belongs to s.
Finset.mem_insert_self- An element a belongs to insert a s.
Finset.mem_sdiff.mpr- An element that belongs to s and does not belong to t belongs to s \ t.
Finset.mem_insert_of_mem- An element belonging to s also belongs to insert b s.
Finset.card_insert_of_notMem- Inserting an element not in a finite set s increases its cardinality by 1.
Finset.card_sdiff_of_subset- If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
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_vertex_exchange {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (Q C : Finset α) (x : α) (hCQ : C ⊆ Q) (hxQ : x ∉ Q) (hx_in : ∀ q ∈ Q, ¬ D.Adj q x) (hx_out : ∀ q ∈ Q \ C, ¬ D.Adj x q) (hxC : ∀ q ∈ C, D.Adj x q) (hkeep : ∀ q ∈ C, ∀ v, D.Adj q v → ∃ r ∈ insert x (Q \ C), D.Adj r 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) : let P := insert x (Q \ C) (∀ 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) ∧ P.card + C.card = Q.card + 1 := by classical dsimp only have hxR : x ∉ Q \ C := fun h => hxQ (Finset.mem_sdiff.mp h).1 constructor · intro u hu v hv huv rcases Finset.mem_insert.mp hu with hu | hu · subst u rcases Finset.mem_insert.mp hv with hv | hv · exact (huv hv.symm).elim · exact hx_out v hv · rcases Finset.mem_insert.mp hv with hv | hv · subst v; exact hx_in u (Finset.mem_sdiff.mp hu).1 · exact hind u (Finset.mem_sdiff.mp hu).1 v (Finset.mem_sdiff.mp hv).1 huv constructor · intro v obtain ⟨u,hu,hd⟩ := hcover v by_cases huC : u ∈ C · rcases hd with heq | ha | ⟨w,haw,hwv⟩ · subst u exact ⟨x, Finset.mem_insert_self _ _, Or.inr (Or.inl (hxC v huC))⟩ · obtain ⟨r,hr,hrv⟩ := hkeep u huC v ha exact ⟨r, hr, Or.inr (Or.inl hrv)⟩ · obtain ⟨r,hr,hrw⟩ := hkeep u huC w haw exact ⟨r, hr, Or.inr (Or.inr ⟨w,hrw,hwv⟩)⟩ · exact ⟨u, Finset.mem_insert_of_mem (Finset.mem_sdiff.mpr ⟨hu,huC⟩),hd⟩ · rw [Finset.card_insert_of_notMem hxR, Finset.card_sdiff_of_subset hCQ] have := Finset.card_le_card hCQ omega-- In a minimum quasi-kernel every possible replacement of at least two-- members has a first-neighborhood obstruction.