AFTD Auto-Formalizing Theoretical Domains

digraph_minimum_quasikernel_exchange_obstruction

theoremverified

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

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.

  1. 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`).

    lines 16–21

      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
  2. 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$.

    lines 22–24

    uses digraph_quasikernel_vertex_exchange

      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
  3. 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`.

    lines 25–26

      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

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
See it in the graphDiscuss this resultChallenge it