AFTD Auto-Formalizing Theoretical Domains

digraph_second_layer_exchange_cardinality

theoremverified

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

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

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

    lines 15–20

    uses Finset.disjoint_left.mpr, Finset.disjoint_left.mp, Finset.mem_filter.mp

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

    lines 21–23

    uses digraph_second_layer_quasikernel_exchange

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

    lines 24–25

    uses Finset.card_union_of_disjoint

      have hbound := hmin (R ∪ K) h.1 h.2
      rw [Finset.card_union_of_disjoint hdisj] at hbound
  4. 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.

    lines 26–27

    uses Finset.card_filter_add_card_filter_not

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

    line 28

      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

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