AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_vertex_exchange

theoremverified

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

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.

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

    lines 15–18

    uses Finset.mem_sdiff.mp

      classical
      dsimp only
      have hxR : x ∉ Q \ C := fun h => hxQ (Finset.mem_sdiff.mp h).1
      constructor
  2. 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.

    lines 19–24

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

    lines 25–27

    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
  4. 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.

    lines 28–30

      constructor
      · intro v
        obtain ⟨u,hu,hd⟩ := hcover v
  5. 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.

    lines 31–39

    uses Finset.mem_insert_self, Finset.mem_sdiff.mpr, Finset.mem_insert_of_mem

        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⟩
  6. |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.

    lines 40–42

    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

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