digraph_two_kernel_perfect_sets_weighted_half_cover
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
- digraph_kernel_perfect_subset_quasikernel_coverLet D be a finite directed graph, allowing loops. Call a vertex set independent when there is no arc between any two distinct vertices in…
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.
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).
uses
Finset.sum_subset,Finset.subset_univ,Finset.mem_union.2,Finset.sum_union_inter,Nat.le_add_righthave 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 _ _
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).
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
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.
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, ?_⟩
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.
uses
Finset.mem_filter,Finset.mem_univ,Finset.sum_le_sum_of_subsethave 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
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.
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, ?_⟩
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.
uses
Finset.mem_filter,Finset.mem_univ,Finset.sum_le_sum_of_subsethave 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.
- The Lean proof handles the cases for A and B by duplicating the argument, whereas an informal proof would assume without loss of generality that A has at least half the total weight.
- The arithmetic deductions (lines 24, 34, and 43) are handled automatically by the `omega` tactic for Presburger arithmetic.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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