AFTD Auto-Formalizing Theoretical Domains

digraph_two_kernel_perfect_sets_weighted_half_cover

theoremverified

If nonnegative integer vertex weights are supported on the union of two kernel-perfect sets of a finite digraph, some quasi-kernel has at least half the total weight in its closed out-neighborhood.

Statement

theorem digraph_two_kernel_perfect_sets_weighted_half_cover
    {α : Type} [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj] (w : α → ℕ) (A B : Finset α)
    (hsupport : ∀ v, w v ≠ 0 → v ∈ A ∨ v ∈ B)
    (hperfect : ∀ S ∈ ({A,B} : Finset (Finset α)),
      ∀ T : Finset α, T ⊆ S → ∃ K : Finset α, K ⊆ T ∧
        (∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) ∧
        (∀ v ∈ T, ∃ u ∈ K, u = v ∨ D.Adj u v)) :
    ∃ Q : Finset α,
      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧
      (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ z, D.Adj u z ∧ D.Adj z v) ∧
      (∑ v ∈ Finset.univ, w v) ≤
        2 * (∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v)
Source
Immediate weighted consequence of Lemma 14 of https://www.combinatorics.org/ojs/index.php/eljc/article/download/v32i2p53/pdf/, with arcs reversed.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

Because the vertex weight function w is supported on A ∪ B, the total weight is bounded by the sum of weights of A and B. By the pigeonhole principle, at least one of A or B carries at least half of the total weight. Applying a theorem on kernel-perfect subsets (digraph_kernel_perfect_subset_quasikernel_cover) to that heavier set yields a quasi-kernel Q whose closed out-neighborhood covers it entirely. Consequently, the closed out-neighborhood of Q contains at least as much weight as the heavier set, and therefore at least half the total weight.

  1. The total weight of all vertices is at most the sum of the weights on A and B: ∑ v, w v ≤ (∑ v ∈ A, w v) + (∑ v ∈ B, w v).

    Since the weight function w is supported on A ∪ B, any vertex outside A ∪ B has weight zero (Finset.mem_union.2). Thus, the total sum equals the sum over A ∪ B (Finset.sum_subset, Finset.subset_univ). By inclusion-exclusion (Finset.sum_union_inter), the sum over A ∪ B plus the sum over A ∩ B equals the sum over A plus the sum over B. Since weights are nonnegative, omitting the intersection term preserves the inequality (Nat.le_add_right).

    lines 14–21

    uses Finset.sum_subset, Finset.subset_univ, Finset.mem_union.2, Finset.sum_union_inter, Nat.le_add_right

      have h_union : ∑ v ∈ Finset.univ, w v ≤ (∑ v ∈ A, w v) + (∑ v ∈ B, w v) := by
        have h1 : ∑ v ∈ A ∪ B, w v = ∑ v, w v := by
          apply Finset.sum_subset (Finset.subset_univ _)
          intro x _ hx
          by_contra hc
          exact hx (Finset.mem_union.2 (hsupport x hc))
        rw [← h1, ← Finset.sum_union_inter]
        exact Nat.le_add_right _ _
  2. At least one of A or B contains at least half the total weight, reducing the proof to two cases: ∑ v, w v ≤ 2 * ∑ v ∈ A, w v or ∑ v, w v ≤ 2 * ∑ v ∈ B, w v.

    Since the total weight is bounded by the sum of weights on A and B, linear integer arithmetic (omega) implies that either 2 * ∑_{v ∈ A} w v or 2 * ∑_{v ∈ B} w v is at least the total weight. The proof then splits into these two cases (rcases).

    lines 22–25

      have h_cases : (∑ v ∈ Finset.univ, w v) ≤ 2 * (∑ v ∈ A, w v) ∨
                     (∑ v ∈ Finset.univ, w v) ≤ 2 * (∑ v ∈ B, w v) := by
        omega
      rcases h_cases with hA | hB
  3. In the case where A carries at least half the total weight, there is a quasi-kernel Q covering A, reducing the goal to showing the weight inequality.

    Because A ∈ {A, B}, the hypothesis hperfect ensures that A is kernel-perfect. Applying digraph_kernel_perfect_subset_quasikernel_cover yields a quasi-kernel Q of D—an independent set where every vertex is reachable in at most two steps—such that every vertex in A lies in the closed out-neighborhood of Q. Choosing Q as the witness (refine) satisfies the first two conditions of the theorem, leaving only the weight bound to show.

    lines 26–28

    uses digraph_kernel_perfect_subset_quasikernel_cover

      · have hA_perf := hperfect A (by simp)
        obtain ⟨Q, hQ1, hQ2, hQ3, -⟩ := digraph_kernel_perfect_subset_quasikernel_cover D A hA_perf
        refine ⟨Q, hQ1, hQ2, ?_⟩
  4. The closed out-neighborhood of Q contains at least half the total weight, concluding the case where A carries at least half the weight.

    Since Q covers A, every vertex of A is in the closed out-neighborhood of Q, meaning A ⊆ {v | ∃ q ∈ Q, q = v ∨ D.Adj q v} (Finset.mem_filter, Finset.mem_univ). Because weights are nonnegative, the sum of weights over this neighborhood is at least the sum over A (Finset.sum_le_sum_of_subset). Combining this with the case hypothesis that 2 * ∑_{v ∈ A} w v ≥ ∑ v, w v, linear arithmetic (omega) confirms the desired weight inequality.

    lines 29–34

    uses Finset.mem_filter, Finset.mem_univ, Finset.sum_le_sum_of_subset

        have hsub : A ⊆ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v) := by
          intro s hs
          rw [Finset.mem_filter]
          exact ⟨Finset.mem_univ s, hQ3 s hs⟩
        have h_le := Finset.sum_le_sum_of_subset (f := w) hsub
        omega
  5. In the case where B carries at least half the total weight, there is a quasi-kernel Q covering B, reducing the goal to showing the weight inequality.

    Symmetrically, B ∈ {A, B} is kernel-perfect by hperfect. Applying digraph_kernel_perfect_subset_quasikernel_cover yields a quasi-kernel Q whose closed out-neighborhood covers B. Selecting Q as the witness (refine) leaves only the weight bound to show.

    lines 35–37

    uses digraph_kernel_perfect_subset_quasikernel_cover

      · have hB_perf := hperfect B (by simp)
        obtain ⟨Q, hQ1, hQ2, hQ3, -⟩ := digraph_kernel_perfect_subset_quasikernel_cover D B hB_perf
        refine ⟨Q, hQ1, hQ2, ?_⟩
  6. The closed out-neighborhood of Q contains at least half the total weight, concluding the case where B carries at least half the weight and completing the proof.

    As in the first case, B is a subset of the closed out-neighborhood of Q (Finset.mem_filter, Finset.mem_univ), so the neighborhood contains at least the weight of B (Finset.sum_le_sum_of_subset). Since B carries at least half the total weight, linear arithmetic (omega) completes the proof.

    lines 38–43

    uses Finset.mem_filter, Finset.mem_univ, Finset.sum_le_sum_of_subset

        have hsub : B ⊆ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v) := by
          intro s hs
          rw [Finset.mem_filter]
          exact ⟨Finset.mem_univ s, hQ3 s hs⟩
        have h_le := Finset.sum_le_sum_of_subset (f := w) hsub
        omega
Finset.mem_union.2
If an element belongs to either of two sets, it belongs to their union.
Finset.sum_subset
If a subset contains all elements where a function is nonzero, the sum over the subset equals the sum over the superset.
Finset.subset_univ
Every finite set of elements of a type is a subset of the universal set.
Finset.sum_union_inter
For any two finite sets, the sum over their union plus the sum over their intersection equals the sum of the sums over each set.
Nat.le_add_right
For any natural numbers n and k, n ≤ n + k.
digraph_kernel_perfect_subset_quasikernel_cover
In a finite digraph, every kernel-perfect subset is covered by the closed out-neighborhood of some quasi-kernel.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal set.
Finset.sum_le_sum_of_subset
For nonnegative terms, the sum over a subset is at most the sum over the superset.

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_two_kernel_perfect_sets_weighted_half_cover    {α : Type} [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj] (w : α → ℕ) (A B : Finset α)    (hsupport : ∀ v, w v ≠ 0 → v ∈ A ∨ v ∈ B)    (hperfect : ∀ S ∈ ({A,B} : Finset (Finset α)),      ∀ T : Finset α, T ⊆ S → ∃ K : Finset α, K ⊆ T ∧        (∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) ∧        (∀ v ∈ T, ∃ u ∈ K, u = v ∨ D.Adj u v)) :    ∃ Q : Finset α,      (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) ∧      (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ z, D.Adj u z ∧ D.Adj z v) ∧      (∑ v ∈ Finset.univ, w v) ≤        2 * (∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v) := by  have h_union : ∑ v ∈ Finset.univ, w v ≤ (∑ v ∈ A, w v) + (∑ v ∈ B, w v) := by    have h1 : ∑ v ∈ A ∪ B, w v = ∑ v, w v := by      apply Finset.sum_subset (Finset.subset_univ _)      intro x _ hx      by_contra hc      exact hx (Finset.mem_union.2 (hsupport x hc))    rw [← h1, ← Finset.sum_union_inter]    exact Nat.le_add_right _ _  have h_cases : (∑ v ∈ Finset.univ, w v) ≤ 2 * (∑ v ∈ A, w v) ∨                 (∑ v ∈ Finset.univ, w v) ≤ 2 * (∑ v ∈ B, w v) := by    omega  rcases h_cases with hA | hB  · have hA_perf := hperfect A (by simp)    obtain ⟨Q, hQ1, hQ2, hQ3, -⟩ := digraph_kernel_perfect_subset_quasikernel_cover D A hA_perf    refine ⟨Q, hQ1, hQ2, ?_⟩    have hsub : A ⊆ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v) := by      intro s hs      rw [Finset.mem_filter]      exact ⟨Finset.mem_univ s, hQ3 s hs⟩    have h_le := Finset.sum_le_sum_of_subset (f := w) hsub    omega  · have hB_perf := hperfect B (by simp)    obtain ⟨Q, hQ1, hQ2, hQ3, -⟩ := digraph_kernel_perfect_subset_quasikernel_cover D B hB_perf    refine ⟨Q, hQ1, hQ2, ?_⟩    have hsub : B ⊆ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v) := by      intro s hs      rw [Finset.mem_filter]      exact ⟨Finset.mem_univ s, hQ3 s hs⟩    have h_le := Finset.sum_le_sum_of_subset (f := w) hsub    omega
See it in the graphDiscuss this resultChallenge it