AFTD Auto-Formalizing Theoretical Domains

digraph_second_layer_quasikernel_exchange

theoremverified

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

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.

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

    lines 14–16

      classical
      dsimp only
      constructor
  2. 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).

    lines 17–23

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

    lines 24–32

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

    lines 33–41

    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⟩)⟩
  5. 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.

    lines 42–43

    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

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