digraph_second_layer_quasikernel_exchange
An independent second-layer set that reaches the vertices outside a set and its first out-neighborhood can replace the original set members it attacks, producing a quasi-kernel.
Statement
theorem digraph_second_layer_quasikernel_exchange {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (Q K : Finset α) (hindQ : ∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) (hindK : ∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) (hKQ : Disjoint K Q) (hQK : ∀ q ∈ Q, ∀ k ∈ K, ¬ D.Adj q k) (hcover : ∀ y, y ∉ Q → (¬ ∃ q ∈ Q, D.Adj q y) → ∃ k ∈ K, k = y ∨ D.Adj k y ∨ ∃ w, D.Adj k w ∧ D.Adj w y) : let R := Q.filter fun q => ¬ ∃ k ∈ K, D.Adj k q let P := R ∪ K (∀ 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)
- Source
- Auxiliary lemma for the OP-337 campaign; Discrete Mathematics 346 (2023), 113435, Observation 4, with arcs reversed.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- digraph_second_layer_exchange_cardinalityIn the second-layer exchange, if the original quasi-kernel is minimum then the second-layer set attacks at most its own number of original…
The proof, explained
The proof constructs a quasi-kernel P = R ∪ K by replacing the vertices of an independent set Q that are attacked by K with K itself, retaining the unattacked subset R ⊆ Q. Independence of P follows by checking pairs across R and K against the independence of Q and K, the absence of edges from Q to K, and the definition of R. Quasi-domination follows by partitioning vertices into those in Q, those in the out-neighborhood of Q, and the rest: the first two groups are reached from R or K in at most two steps via the attack edges, while the remaining vertices are reached from K by the covering hypothesis.
The problem reduces to showing that P = R ∪ K is independent and that P reaches every vertex in at most two steps.
We unfold the definitions of R (the vertices of Q having no in-neighbor in K) and P = R ∪ K, and split the goal into the two defining conditions of a quasi-kernel: independence of P and quasi-domination by P.
classical dsimp only constructor
The set P = R ∪ K is independent.
Given distinct vertices u, v ∈ P, each lies in either R or K. We case split on the four combinations: if both are in R ⊆ Q, they are non-adjacent by independence of Q (hindQ); if u ∈ R and v ∈ K, there is no edge from Q to K by assumption (hQK); if u ∈ K and v ∈ R, an edge from u to v contradicts the definition of R, which excludes vertices attacked by K; and if both are in K, they are non-adjacent by independence of K (hindK).
uses
Finset.mem_union.mp,Finset.mem_filter.mp· intro u hu v hv huv rcases Finset.mem_union.mp hu with hu | hu <;> rcases Finset.mem_union.mp hv with hv | hv · exact hindQ u (Finset.mem_filter.mp hu).1 v (Finset.mem_filter.mp hv).1 huv · exact hQK u (Finset.mem_filter.mp hu).1 v hv · exact fun hadj => (Finset.mem_filter.mp hv).2 ⟨u,hu,hadj⟩ · exact hindK u hu v hv huv
Every vertex v ∈ Q is reached from P in at most one step.
For v ∈ Q, we split on whether v ∈ R. If v ∈ R, then v ∈ P reaches itself in 0 steps. If v ∉ R, then by definition of R some k ∈ K attacks v directly, so k ∈ P dominates v in 1 step.
uses
Finset.mem_union_left,Or.inl,Finset.mem_filter.mpr,Finset.mem_union_right,Or.inr· intro v by_cases hvQ : v ∈ Q · by_cases hvR : v ∈ Q.filter (fun q => ¬ ∃ k ∈ K, D.Adj k q) · exact ⟨v,Finset.mem_union_left _ hvR,Or.inl rfl⟩ · have hex : ∃ k ∈ K, D.Adj k v := by by_contra hn exact hvR (Finset.mem_filter.mpr ⟨hvQ,hn⟩) obtain ⟨k,hk,hkv⟩ := hex exact ⟨k,Finset.mem_union_right _ hk,Or.inr (Or.inl hkv)⟩
Every vertex v ∉ Q that has an in-neighbor in Q is reached from P in at most two steps.
Let q ∈ Q be an in-neighbor of v. If q ∈ R, then q ∈ P reaches v in 1 step. If q ∉ R, then by definition of R some k ∈ K attacks q, yielding a two-step path k → q → v from k ∈ P to v.
uses
Finset.mem_union_left,Or.inr,Or.inl,Finset.mem_filter.mpr,Finset.mem_union_right· by_cases hex : ∃ q ∈ Q, D.Adj q v · obtain ⟨q,hq,hqv⟩ := hex by_cases hqR : q ∈ Q.filter (fun a => ¬ ∃ k ∈ K, D.Adj k a) · exact ⟨q,Finset.mem_union_left _ hqR,Or.inr (Or.inl hqv)⟩ · have hkq : ∃ k ∈ K, D.Adj k q := by by_contra hn exact hqR (Finset.mem_filter.mpr ⟨hq,hn⟩) obtain ⟨k,hk,hkq'⟩ := hkq exact ⟨k,Finset.mem_union_right _ hk,Or.inr (Or.inr ⟨q,hkq',hqv⟩)⟩
Every vertex v ∉ Q with no in-neighbor in Q is reached from P in at most two steps.
When v ∉ Q and no vertex of Q attacks v, the covering hypothesis (hcover) guarantees the existence of some k ∈ K reaching v in at most two steps. Since K ⊆ P, this witness k belongs to P.
uses
Finset.mem_union_right· obtain ⟨k,hk,hd⟩ := hcover v hvQ hex exact ⟨k,Finset.mem_union_right _ hk,hd⟩
Finset.mem_union.mp- If an element belongs to the union s ∪ t, it belongs to s or to t.
Finset.mem_filter.mp- If an element belongs to the filtered set {x ∈ s | P x}, it belongs to s and satisfies property P.
Finset.mem_filter.mpr- If an element belongs to s and satisfies property P, it belongs to the filtered set {x ∈ s | P x}.
Finset.mem_union_left- An element belonging to s also belongs to the union s ∪ t.
Finset.mem_union_right- An element belonging to t also belongs to the union s ∪ t.
Or.inl- From a proposition A, infer the disjunction A ∨ B.
Or.inr- From a proposition B, infer 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_second_layer_quasikernel_exchange {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (Q K : Finset α) (hindQ : ∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) (hindK : ∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) (hKQ : Disjoint K Q) (hQK : ∀ q ∈ Q, ∀ k ∈ K, ¬ D.Adj q k) (hcover : ∀ y, y ∉ Q → (¬ ∃ q ∈ Q, D.Adj q y) → ∃ k ∈ K, k = y ∨ D.Adj k y ∨ ∃ w, D.Adj k w ∧ D.Adj w y) : let R := Q.filter fun q => ¬ ∃ k ∈ K, D.Adj k q let P := R ∪ K (∀ 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) := by classical dsimp only constructor · intro u hu v hv huv rcases Finset.mem_union.mp hu with hu | hu <;> rcases Finset.mem_union.mp hv with hv | hv · exact hindQ u (Finset.mem_filter.mp hu).1 v (Finset.mem_filter.mp hv).1 huv · exact hQK u (Finset.mem_filter.mp hu).1 v hv · exact fun hadj => (Finset.mem_filter.mp hv).2 ⟨u,hu,hadj⟩ · exact hindK u hu v hv huv · intro v by_cases hvQ : v ∈ Q · by_cases hvR : v ∈ Q.filter (fun q => ¬ ∃ k ∈ K, D.Adj k q) · exact ⟨v,Finset.mem_union_left _ hvR,Or.inl rfl⟩ · have hex : ∃ k ∈ K, D.Adj k v := by by_contra hn exact hvR (Finset.mem_filter.mpr ⟨hvQ,hn⟩) obtain ⟨k,hk,hkv⟩ := hex exact ⟨k,Finset.mem_union_right _ hk,Or.inr (Or.inl hkv)⟩ · by_cases hex : ∃ q ∈ Q, D.Adj q v · obtain ⟨q,hq,hqv⟩ := hex by_cases hqR : q ∈ Q.filter (fun a => ¬ ∃ k ∈ K, D.Adj k a) · exact ⟨q,Finset.mem_union_left _ hqR,Or.inr (Or.inl hqv)⟩ · have hkq : ∃ k ∈ K, D.Adj k q := by by_contra hn exact hqR (Finset.mem_filter.mpr ⟨hq,hn⟩) obtain ⟨k,hk,hkq'⟩ := hkq exact ⟨k,Finset.mem_union_right _ hk,Or.inr (Or.inr ⟨q,hkq',hqv⟩)⟩ · obtain ⟨k,hk,hd⟩ := hcover v hvQ hex exact ⟨k,Finset.mem_union_right _ hk,hd⟩-- For minimum Q, the second-layer selection cannot attack more members-- of Q than it contains itself.