digraph_second_layer_exchange_cardinality
In the second-layer exchange, if the original quasi-kernel is minimum then the second-layer set attacks at most its own number of original members.
Statement
theorem digraph_second_layer_exchange_cardinality {α : 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) (hmin : ∀ P : Finset α, (∀ 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) → Q.card ≤ P.card) : (Q.filter fun q => ∃ k ∈ K, D.Adj k q).card ≤ K.card
- 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- Built on 1
- digraph_second_layer_quasikernel_exchangeAn independent second-layer set that reaches the vertices outside a set and its first out-neighborhood can replace the original set…
The proof, explained
The proof constructs an alternative quasi-kernel by replacing the vertices of Q attacked by K with K itself, defining R as the remaining unattacked vertices of Q. By the quasi-kernel exchange lemma, R ∪ K is an independent quasi-kernel, so by minimality of Q we have |Q| ≤ |R ∪ K| = |R| + |K| since R and K are disjoint. Partitioning Q into the attacked vertices and R gives |Q| = |{q ∈ Q | ∃ k ∈ K, k → q}| + |R|, which immediately implies that the number of attacked vertices is at most |K|.
Define R as the vertices of Q not attacked by K, and establish that R and K are disjoint.
Under classical logic, define R as the subset of vertices in Q that have no incoming edge from any vertex in K. To show R and K are disjoint, suppose x is in both R and K; since x ∈ R, it must belong to Q, but Q and K are assumed to be disjoint, which is a contradiction.
uses
Finset.disjoint_left.mpr,Finset.disjoint_left.mp,Finset.mem_filter.mpclassical let R := Q.filter fun q => ¬ ∃ k ∈ K, D.Adj k q have hdisj : Disjoint R K := by apply Finset.disjoint_left.mpr intro x hxR hxK exact (Finset.disjoint_left.mp hKQ) hxK (Finset.mem_filter.mp hxR).1
The set R ∪ K is an independent quasi-kernel of D.
Applying the quasi-kernel exchange lemma (digraph_second_layer_quasikernel_exchange) with the given hypotheses shows that the union R ∪ K is independent and 2-dominates the entire graph.
uses
digraph_second_layer_quasikernel_exchangehave h := digraph_second_layer_quasikernel_exchange D Q K hindQ hindK hKQ hQK hcover change (∀ u ∈ R ∪ K, ∀ v ∈ R ∪ K, u ≠ v → ¬ D.Adj u v) ∧ (∀ v, ∃ u ∈ R ∪ K, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) at h
|Q| ≤ |R| + |K|.
Since Q is a quasi-kernel of minimum cardinality, its size cannot exceed that of R ∪ K, giving |Q| ≤ |R ∪ K|. Because R and K are disjoint, |R ∪ K| = |R| + |K|.
uses
Finset.card_union_of_disjointhave hbound := hmin (R ∪ K) h.1 h.2 rw [Finset.card_union_of_disjoint hdisj] at hbound
The attacked and unattacked vertices partition Q, so |{q ∈ Q | ∃ k ∈ K, k → q}| + |R| = |Q|.
Partitioning Q according to whether a vertex has an incoming edge from K or not expresses |Q| as the sum of the cardinalities of the attacked vertices and R.
uses
Finset.card_filter_add_card_filter_nothave hsplit := Finset.card_filter_add_card_filter_not (s := Q) (fun q => ∃ k ∈ K, D.Adj k q) change (Q.filter fun q => ∃ k ∈ K, D.Adj k q).card + R.card = Q.card at hsplit
The number of vertices in Q attacked by K is at most |K|.
Substituting the partition of |Q| into the bound |Q| ≤ |R| + |K| and canceling |R| leaves the desired inequality by basic linear arithmetic.
omega
Finset.disjoint_left.mpr- A set is disjoint from another if every element of the first does not belong to the second.
Finset.disjoint_left.mp- If two sets are disjoint, then any element of the first does not belong to the second.
Finset.mem_filter.mp- If an element is in a filtered set, then it belongs to the original set and satisfies the predicate.
digraph_second_layer_quasikernel_exchange- Under the second-layer exchange conditions, replacing the vertices of Q that are attacked by K with K yields an independent quasi-kernel.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_filter_add_card_filter_not- The size of the subset of elements satisfying a predicate plus the size of the subset not satisfying it equals the cardinality of the ambient set.
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_exchange_cardinality {α : 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) (hmin : ∀ P : Finset α, (∀ 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) → Q.card ≤ P.card) : (Q.filter fun q => ∃ k ∈ K, D.Adj k q).card ≤ K.card := by classical let R := Q.filter fun q => ¬ ∃ k ∈ K, D.Adj k q have hdisj : Disjoint R K := by apply Finset.disjoint_left.mpr intro x hxR hxK exact (Finset.disjoint_left.mp hKQ) hxK (Finset.mem_filter.mp hxR).1 have h := digraph_second_layer_quasikernel_exchange D Q K hindQ hindK hKQ hQK hcover change (∀ u ∈ R ∪ K, ∀ v ∈ R ∪ K, u ≠ v → ¬ D.Adj u v) ∧ (∀ v, ∃ u ∈ R ∪ K, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) at h have hbound := hmin (R ∪ K) h.1 h.2 rw [Finset.card_union_of_disjoint hdisj] at hbound have hsplit := Finset.card_filter_add_card_filter_not (s := Q) (fun q => ∃ k ∈ K, D.Adj k q) change (Q.filter fun q => ∃ k ∈ K, D.Adj k q).card + R.card = Q.card at hsplit omega