digraph_minimum_quasikernel_exchange_obstruction
If a vertex can independently replace at least two members of a minimum quasi-kernel, then an out-neighbor of the removed members is not reached in one step from the proposed replacement set.
Statement
theorem digraph_minimum_quasikernel_exchange_obstruction {α : 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) (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 : ∀ 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) (hsize : 2 ≤ C.card) : ∃ q ∈ C, ∃ v, D.Adj q v ∧ ∀ r ∈ insert x (Q \ C), ¬ D.Adj r 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_vertex_exchangeOne vertex can replace a subset of a quasi-kernel when independence holds and its insertion preserves the first out-neighborhood of each…
The proof, explained
The proof proceeds by contradiction. If no out-neighbor of $C$ avoids being dominated in one step by the replacement set $P = \{x\} \cup (Q \setminus C)$, then $P$ satisfies the conditions of the vertex-exchange lemma, making $P$ another quasi-kernel with $|P| + |C| = |Q| + 1$. Since $|C| \ge 2$, the replacement set has cardinality $|P| \le |Q| - 1 < |Q|$, which directly contradicts the assumption that $Q$ has minimum size among all quasi-kernels.
Assume for contradiction that every out-neighbor of every vertex in $C$ is reached in one step by some vertex in $\{x\} \cup (Q \setminus C)$.
We proceed by contradiction under classical logic, assuming the negation of the theorem's existential claim. Pushing the negation through the quantifiers gives the hypothesis that for every $q \in C$ and any vertex $v$, if $D$ has a directed edge from $q$ to $v$, then some $r \in \{x\} \cup (Q \setminus C)$ also has a directed edge to $v$ (named `hkeep`).
classical by_contra hnone push Not at hnone have hkeep : ∀ q ∈ C, ∀ v, D.Adj q v → ∃ r ∈ insert x (Q \ C), D.Adj r v := by intro q hq v hqv exact hnone q hq v hqv
The replacement set $P = \{x\} \cup (Q \setminus C)$ is an independent 2-dominating set (a quasi-kernel) satisfying $|P| + |C| = |Q| + 1$.
Applying the vertex-exchange lemma `digraph_quasikernel_vertex_exchange` with the hypotheses on $x$, $Q$, and $C$, together with the coverage property `hkeep`, proves that $P$ is independent, 2-dominates the digraph, and has cardinality satisfying $|P| + |C| = |Q| + 1$.
uses
digraph_quasikernel_vertex_exchangehave h := digraph_quasikernel_vertex_exchange D Q C x hCQ hxQ hx_in hx_out hxC hkeep hind hcover dsimp only at h obtain ⟨hi,hc,hcard⟩ := h
The minimality of $Q$ contradicts the size of $P$.
Because $Q$ is assumed to have minimum cardinality among all quasi-kernels (`hmin`), any independent 2-dominating set has size at least $|Q|$, so $|Q| \le |P|$. But $|P| + |C| = |Q| + 1$ and $|C| \ge 2$ imply $|P| \le |Q| - 1 < |Q|$, an arithmetic contradiction resolved by `omega`.
have hbound := hmin (insert x (Q \ C)) hi hc omega
digraph_quasikernel_vertex_exchange- If $Q$ is a quasi-kernel (an independent 2-dominating set) in a digraph $D$, $C \subseteq Q$, and a vertex $x \notin Q$ has no in-neighbors from $Q$, has no out-neighbors in $Q \setminus C$, has edges to all vertices in $C$, and every out-neighbor of $C$ is also an out-neighbor of some vertex in $\{x\} \cup (Q \setminus C)$, then $P = \{x\} \cup (Q \setminus C)$ is also a quasi-kernel, with cardinality satisfying $|P| + |C| = |Q| + 1$.
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_minimum_quasikernel_exchange_obstruction {α : 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) (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 : ∀ 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) (hsize : 2 ≤ C.card) : ∃ q ∈ C, ∃ v, D.Adj q v ∧ ∀ r ∈ insert x (Q \ C), ¬ D.Adj r v := by classical by_contra hnone push Not at hnone have hkeep : ∀ q ∈ C, ∀ v, D.Adj q v → ∃ r ∈ insert x (Q \ C), D.Adj r v := by intro q hq v hqv exact hnone q hq v hqv have h := digraph_quasikernel_vertex_exchange D Q C x hCQ hxQ hx_in hx_out hxC hkeep hind hcover dsimp only at h obtain ⟨hi,hc,hcard⟩ := h have hbound := hmin (insert x (Q \ C)) hi hc omega