digraph_quasikernel_weighted_half_cover_support_six
For any finite loopless digraph and nonnegative integer vertex weights supported on at most six vertices, some quasi-kernel has at least half the total weight in its closed out-neighborhood.
Statement
theorem digraph_quasikernel_weighted_half_cover_support_six {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (w : α → ℕ) (hsupport : (Finset.univ.filter (fun v => w v ≠ 0)).card ≤ 6) : ∃ 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
- A small-support consequence of Lemma 14 of https://www.combinatorics.org/ojs/index.php/eljc/article/download/v32i2p53/pdf/; the finite local and weight inequalities were audited in experiment 14074.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- digraph_four_vertices_kernel_perfect_tripleEvery four-vertex induced subdigraph of a loopless digraph contains a kernel-perfect three-vertex set through any prescribed vertex.
The proof, explained
The proof reduces to the support P of vertices with non-zero weight, which by assumption has at most six vertices. When |P| ≤ 3, an elementary argument finds a subset of at most two vertices carrying at least half the weight, and since every loopless digraph on at most two vertices is kernel-perfect, this subset is covered by some quasi-kernel. When |P| ≥ 4, the four heaviest vertices are chosen greedily; by a structural theorem on loopless digraphs, this four-vertex set contains a three-vertex kernel-perfect subset containing the heaviest vertex, which is then covered by a quasi-kernel and shown by a weight-maximization bound to carry at least half the total weight.
Any set of four pairwise distinct elements has cardinality 4.
The four-element set {a, b, c, d} is expressed as iterated insertions. Since the four elements are pairwise distinct by hypothesis, each insertion adds an element not already present, so the cardinality increments by 1 at each step starting from the singleton {d} of size 1.
uses
Finset.card_insert_of_notMem,Finset.card_singletonrw [show ({a,b,c,d} : Finset α) = insert a (insert b (insert c ({d} : Finset α))) from rfl] rw [Finset.card_insert_of_notMem (by simp [h1, h2, h3]), Finset.card_insert_of_notMem (by simp [h4, h5]), Finset.card_insert_of_notMem (by simp [h6]), Finset.card_singleton]
If |P| < 3, then S = P is a subset of size at most 2 that carries at least half the total weight. automation
We case-split on whether |P| < 3 or |P| ≥ 3. In the former case, choosing S = P satisfies |S| ≤ 2 and w(P) ≤ 2 * w(P) immediately by linear arithmetic.
uses
Nat.lt_or_ge,Finset.Subset.reflrcases Nat.lt_or_ge P.card 3 with h3 | h3 · exact ⟨P, Finset.Subset.refl P, by omega, by omega⟩
If |P| = 3, removing some element other than a maximum-weight element yields a subset S of size 2 with w(P) ≤ 2 * w(S).
Since P has size 3, it is non-empty. Let x₁ be an element of maximal weight in P. The set P minus {x₁} has 2 elements, so it is non-empty; pick any y in it. Setting S = P minus {y}, we have |S| = 2. Since y ≠ x₁, x₁ remains in S, so w(x₁) ≤ w(S). The total weight splits as w(P) = w(y) + w(S), and since w(y) ≤ w(x₁) ≤ w(S), we have w(P) ≤ 2 * w(S).
uses
Finset.card_pos.mp,Finset.exists_max_image,Finset.card_erase_of_mem,Finset.mem_of_mem_erase,Finset.mem_erase.mp,Finset.erase_subset,Finset.mem_erase.mpr,Finset.single_le_sum,Nat.zero_le,Finset.add_sum_erase· have hne : P.Nonempty := Finset.card_pos.mp (by omega) obtain ⟨x1, hx1, hx1max⟩ := Finset.exists_max_image P w hne have hcard1 : (P.erase x1).card = 2 := by rw [Finset.card_erase_of_mem hx1]; omega have hne1 : (P.erase x1).Nonempty := Finset.card_pos.mp (by omega) obtain ⟨y, hy⟩ := hne1 have hyP : y ∈ P := Finset.mem_of_mem_erase hy have hyx : y ≠ x1 := (Finset.mem_erase.mp hy).1 refine ⟨P.erase y, Finset.erase_subset y P, ?_, ?_⟩ · rw [Finset.card_erase_of_mem hyP]; omega · have hx1mem : x1 ∈ P.erase y := Finset.mem_erase.mpr ⟨hyx.symm, hx1⟩ have hle : w x1 ≤ ∑ v ∈ P.erase y, w v := Finset.single_le_sum (f := w) (fun i _ => Nat.zero_le _) hx1mem have hsplit : ∑ v ∈ P, w v = w y + ∑ v ∈ P.erase y, w v := (Finset.add_sum_erase P w hyP).symm have hxy : w y ≤ w x1 := hx1max y hyP omega
For the four greedy heaviest vertices A = {x₁, x₂, x₃, x₄} in P with |P| ≤ 6, the weight outside A is at most 2 * w(x₄).
The set A has cardinality 4 and its total weight is the sum of the four individual weights. Since |P| ≤ 6 and A ⊆ P, the complement P \ A has size at most 6 - 4 = 2. By the greedy choice of x₄, every vertex in P \ A has weight at most w(x₄). Summing over P \ A yields a total weight of at most 2 * w(x₄).
uses
digraph_qkw_card_four_set,Finset.sum_insert,Finset.sum_singleton,Finset.card_sdiff,Finset.inter_eq_left.mpr,Finset.mem_sdiff,Finset.sum_le_card_nsmul,Nat.mul_le_mul_righthave hA4 : ({x1,x2,x3,x4} : Finset α).card = 4 := digraph_qkw_card_four_set x1 x2 x3 x4 h12 h13 h14 h23 h24 h34 have hsumA : ∑ v ∈ ({x1,x2,x3,x4} : Finset α), w v = w x1 + w x2 + w x3 + w x4 := by rw [show ({x1,x2,x3,x4} : Finset α) = insert x1 (insert x2 (insert x3 ({x4} : Finset α))) from rfl] rw [Finset.sum_insert (by simp [h12, h13, h14]), Finset.sum_insert (by simp [h23, h24]), Finset.sum_insert (by simp [h34]), Finset.sum_singleton] omega have hcard : (P \ ({x1,x2,x3,x4} : Finset α)).card ≤ 2 := by rw [Finset.card_sdiff, Finset.inter_eq_left.mpr hsub, hA4] omega have hbound_out : ∀ y ∈ P \ ({x1,x2,x3,x4} : Finset α), w y ≤ w x4 := by intro y hy rw [Finset.mem_sdiff] at hy obtain ⟨hyP, hyA⟩ := hy have hy1 : y ≠ x1 := by intro h; exact hyA (h ▸ (by simp : x1 ∈ ({x1,x2,x3,x4} : Finset α))) have hy2 : y ≠ x2 := by intro h; exact hyA (h ▸ (by simp : x2 ∈ ({x1,x2,x3,x4} : Finset α))) have hy3 : y ≠ x3 := by intro h; exact hyA (h ▸ (by simp : x3 ∈ ({x1,x2,x3,x4} : Finset α))) exact hx4max y hyP hy1 hy2 hy3 have hsumout : ∑ v ∈ P \ ({x1,x2,x3,x4} : Finset α), w v ≤ 2 * w x4 := by have h1 := Finset.sum_le_card_nsmul (P \ ({x1,x2,x3,x4} : Finset α)) w (w x4) hbound_out have h2 : (P \ ({x1,x2,x3,x4} : Finset α)).card * w x4 ≤ 2 * w x4 := Nat.mul_le_mul_right (w x4) hcard calc ∑ v ∈ P \ ({x1,x2,x3,x4} : Finset α), w v ≤ (P \ ({x1,x2,x3,x4} : Finset α)).card • w x4 := h1 _ = (P \ ({x1,x2,x3,x4} : Finset α)).card * w x4 := by simp _ ≤ 2 * w x4 := h2
Any 3-element subset T ⊆ A containing x₁ carries at least half the weight of P. automation
The difference A \ T contains exactly one vertex y. Since x₁ ∈ T, we have y ≠ x₁, so w(y) ≤ w(x₂). Thus w(A) = w(y) + w(T) ≤ w(x₂) + w(T), and adding the weight outside A gives w(P) ≤ w(T) + w(x₂) + 2 * w(x₄). Since w(x₂) ≤ w(x₁) and w(x₄) ≤ w(x₃), and T contains x₁ and two elements of {x₂, x₃, x₄}, linear arithmetic shows w(P) ≤ 2 * w(T).
uses
Finset.card_sdiff,Finset.inter_eq_left.mpr,Finset.card_eq_one.mp,Finset.mem_sdiff.mp,Finset.sum_sdiff,Finset.sum_singleton,Ne.symmhave hdiff1 : (({x1,x2,x3,x4} : Finset α) \ T).card = 1 := by rw [Finset.card_sdiff, Finset.inter_eq_left.mpr hTsub, hT3, hA4] obtain ⟨y, hy_eq⟩ := Finset.card_eq_one.mp hdiff1 have hyA : y ∈ ({x1,x2,x3,x4} : Finset α) := by have hh : y ∈ ({x1,x2,x3,x4} : Finset α) \ T := by rw [hy_eq]; simp exact (Finset.mem_sdiff.mp hh).1 have hyT : y ∉ T := by have hh : y ∈ ({x1,x2,x3,x4} : Finset α) \ T := by rw [hy_eq]; simp exact (Finset.mem_sdiff.mp hh).2 have hyP : y ∈ P := hsub hyA have hy1 : y ≠ x1 := by intro h; exact hyT (h ▸ hx1T) have hwy : w y ≤ w x2 := hx2max y hyP hy1 have hsumT : ∑ v ∈ ({x1,x2,x3,x4} : Finset α), w v = w y + ∑ v ∈ T, w v := by have h := Finset.sum_sdiff (f := w) hTsub rw [hy_eq, Finset.sum_singleton] at h omega have hsplit : ∑ v ∈ P, w v = ∑ v ∈ ({x1,x2,x3,x4} : Finset α), w v + ∑ v ∈ P \ ({x1,x2,x3,x4} : Finset α), w v := by have h := Finset.sum_sdiff (f := w) hsub omega have hx2le1 : w x2 ≤ w x1 := hx1max x2 (hsub (by simp)) have hx4le3 : w x4 ≤ w x3 := hx3max x4 (hsub (by simp)) (Ne.symm h14) (Ne.symm h24) omega
Any induced subgraph on at most 1 vertex in a loopless digraph has a kernel.
Let T ⊆ S with |S| ≤ 2, so |T| ≤ 2. If |T| = 0, the empty set is vacuously an independent set and out-dominates T. If |T| = 1, say T = {a}, then K = {a} is an independent set and out-dominates itself.
uses
le_trans,Finset.card_le_card,Nat.lt_or_ge,Finset.card_eq_zero.mp,Finset.empty_subset,Finset.card_eq_one.mp,Finset.mem_singleton,Finset.mem_singleton_self,Or.inlintro T hT have hTcard : T.card ≤ 2 := le_trans (Finset.card_le_card hT) hS rcases Nat.lt_or_ge T.card 2 with h2 | h2 · rcases Nat.lt_or_ge T.card 1 with h1 | h1 · have h0 : T.card = 0 := by omega have hT0 : T = ∅ := Finset.card_eq_zero.mp h0 refine ⟨∅, Finset.empty_subset _, ?_, ?_⟩ · intro u hu; simp at hu · intro v hv; rw [hT0] at hv; simp at hv · have h1' : T.card = 1 := by omega obtain ⟨a, ha⟩ := Finset.card_eq_one.mp h1' refine ⟨{a}, ?_, ?_, ?_⟩ · intro x hx; simpa [ha] using hx · intro u hu v hv huv rw [Finset.mem_singleton] at hu hv exact (huv (hu.trans hv.symm)).elim · intro v hv rw [ha, Finset.mem_singleton] at hv exact ⟨a, Finset.mem_singleton_self a, Or.inl hv.symm⟩
Any induced subgraph on 2 vertices in a loopless digraph has a kernel.
Let T = {a, b} with a ≠ b. If there is an edge from a to b, K = {a} is an independent set that covers both vertices. If there is an edge from b to a, K = {b} works symmetrically. If there is no edge between a and b, K = {a, b} is an independent set and out-dominates T. In all cases, S is kernel-perfect.
uses
Finset.card_eq_two.mp,Finset.mem_singleton,Finset.mem_insert,Finset.mem_singleton_self,Or.inl,Or.inr· have h2' : T.card = 2 := by omega obtain ⟨a, b, hab, hT2⟩ := Finset.card_eq_two.mp h2' rw [hT2] by_cases habA : D.Adj a b · refine ⟨{a}, ?_, ?_, ?_⟩ · intro x hx; rw [Finset.mem_singleton] at hx; rw [hx]; simp · intro u hu v hv huv rw [Finset.mem_singleton] at hu hv exact (huv (hu.trans hv.symm)).elim · intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with hv | hv · exact ⟨a, Finset.mem_singleton_self a, Or.inl hv.symm⟩ · refine ⟨a, Finset.mem_singleton_self a, Or.inr ?_⟩ rw [hv]; exact habA · by_cases hbaA : D.Adj b a · refine ⟨{b}, ?_, ?_, ?_⟩ · intro x hx; rw [Finset.mem_singleton] at hx; rw [hx]; simp · intro u hu v hv huv rw [Finset.mem_singleton] at hu hv exact (huv (hu.trans hv.symm)).elim · intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with hv | hv · refine ⟨b, Finset.mem_singleton_self b, Or.inr ?_⟩ rw [hv]; exact hbaA · exact ⟨b, Finset.mem_singleton_self b, Or.inl hv.symm⟩ · refine ⟨{a, b}, ?_, ?_, ?_⟩ · intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx ⊢ tauto · intro u hu v hv huv simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with hu | hu <;> rcases hv with hv | hv · exact (huv (hu.trans hv.symm)).elim · rw [hu, hv]; exact habA · rw [hu, hv]; exact hbaA · exact (huv (hu.trans hv.symm)).elim · intro v hv exact ⟨v, hv, Or.inl rfl⟩
The total weight on the digraph equals the weight on the support P = {v | w(v) ≠ 0}, which has at most 6 vertices.
We restrict the universe to the support P of positive-weight vertices. By assumption, |P| ≤ 6. Since any vertex outside P has weight 0, the sum of weights over all vertices equals the sum over P.
uses
Finset.sum_subset,Finset.subset_univ,Finset.mem_filter.mpr,Finset.mem_univclassical set P : Finset α := Finset.univ.filter (fun v => w v ≠ 0) with hP have hPcard : P.card ≤ 6 := hsupport have hsumP : (∑ v ∈ P, w v) = ∑ v ∈ Finset.univ, w v := by refine Finset.sum_subset (Finset.subset_univ P) ?_ intro x _ hx have hx' : ¬ (w x ≠ 0) := by intro h exact hx (by rw [hP]; exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩) simpa using hx'
If |P| ≤ 3, some quasi-kernel covers at least half the total weight.
When |P| ≤ 3, lemma digraph_qkw_weight_small_support yields S ⊆ P with |S| ≤ 2 such that w(P) ≤ 2 * w(S). By digraph_qkw_kp_of_card_le_two, S is kernel-perfect. By digraph_kernel_perfect_subset_quasikernel_cover, there is a quasi-kernel Q whose closed out-neighborhood covers S. Since weights are non-negative, w(S) is at most the weight in the closed out-neighborhood of Q, yielding w(V) = w(P) ≤ 2 * w(S) ≤ 2 * w(N⁺[Q]).
uses
Nat.lt_or_ge,digraph_qkw_weight_small_support,digraph_qkw_kp_of_card_le_two,digraph_kernel_perfect_subset_quasikernel_cover,Finset.mem_filter.mpr,Finset.mem_univ,Finset.sum_le_sum_of_subset_of_nonneg,Nat.zero_le,Nat.mul_le_mul_leftrcases Nat.lt_or_ge P.card 4 with hlt | hge · have hsmall : P.card ≤ 3 := by omega obtain ⟨S, hSP, hScard, hSweight⟩ := digraph_qkw_weight_small_support P w hsmall have hkp := digraph_qkw_kp_of_card_le_two D hloop S hScard obtain ⟨Q, hQind, hQcover, hQS, hQout⟩ := digraph_kernel_perfect_subset_quasikernel_cover D S hkp refine ⟨Q, hQind, hQcover, ?_⟩ have hSN : S ⊆ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v) := by intro s hs obtain ⟨q, hqQ, hq⟩ := hQS s hs exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, q, hqQ, hq⟩ have hsumN : ∑ v ∈ S, w v ≤ ∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v := Finset.sum_le_sum_of_subset_of_nonneg hSN (fun i _ _ => Nat.zero_le _) calc ∑ v ∈ Finset.univ, w v = ∑ v ∈ P, w v := hsumP.symm _ ≤ 2 * ∑ v ∈ S, w v := hSweight _ ≤ 2 * ∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v := Nat.mul_le_mul_left 2 hsumN
When |P| ≥ 4, there exist four distinct vertices x₁, x₂, x₃, x₄ in P with greedily decreasing maximal weights.
Because |P| ≥ 4, we repeatedly extract maximum-weight vertices: x₁ in P, then x₂ in P \ {x₁}, then x₃ in P \ {x₁, x₂}, and x₄ in P \ {x₁, x₂, x₃}. These four vertices are distinct by construction, so they form a 4-element subset A ⊆ P.
uses
Finset.exists_max_image,Finset.card_pos.mp,Finset.card_erase_of_mem,Finset.mem_of_mem_erase,Finset.mem_erase.mp,Ne.symm,Finset.mem_insert,Finset.mem_singleton,digraph_qkw_card_four_set· have h4 : 4 ≤ P.card := hge obtain ⟨x1, hx1P, hx1max⟩ := Finset.exists_max_image P w (Finset.card_pos.mp (by omega)) have hc1 : (P.erase x1).card = P.card - 1 := Finset.card_erase_of_mem hx1P have hne1 : (P.erase x1).Nonempty := Finset.card_pos.mp (by omega) obtain ⟨x2, hx2e, hx2max⟩ := Finset.exists_max_image (P.erase x1) w hne1 have hx2P : x2 ∈ P := Finset.mem_of_mem_erase hx2e have hx2ne : x2 ≠ x1 := (Finset.mem_erase.mp hx2e).1 have hc2 : ((P.erase x1).erase x2).card = P.card - 2 := by rw [Finset.card_erase_of_mem hx2e, hc1]; omega have hne2 : ((P.erase x1).erase x2).Nonempty := Finset.card_pos.mp (by omega) obtain ⟨x3, hx3e, hx3max⟩ := Finset.exists_max_image ((P.erase x1).erase x2) w hne2 have hx3P : x3 ∈ P := Finset.mem_of_mem_erase (Finset.mem_of_mem_erase hx3e) have hx3ne1 : x3 ≠ x1 := (Finset.mem_erase.mp (Finset.mem_of_mem_erase hx3e)).1 have hx3ne2 : x3 ≠ x2 := (Finset.mem_erase.mp hx3e).1 have hc3 : (((P.erase x1).erase x2).erase x3).card = P.card - 3 := by rw [Finset.card_erase_of_mem hx3e, hc2]; omega have hne3 : (((P.erase x1).erase x2).erase x3).Nonempty := Finset.card_pos.mp (by omega) obtain ⟨x4, hx4e, hx4max⟩ := Finset.exists_max_image (((P.erase x1).erase x2).erase x3) w hne3 have hx4e' : x4 ∈ (P.erase x1).erase x2 := (Finset.mem_erase.mp hx4e).2 have hx4ne3 : x4 ≠ x3 := (Finset.mem_erase.mp hx4e).1 have hx4ne2 : x4 ≠ x2 := (Finset.mem_erase.mp hx4e').1 have hx4e'' : x4 ∈ P.erase x1 := (Finset.mem_erase.mp hx4e').2 have hx4ne1 : x4 ≠ x1 := (Finset.mem_erase.mp hx4e'').1 have hx4P : x4 ∈ P := Finset.mem_of_mem_erase hx4e'' have h12 : x1 ≠ x2 := hx2ne.symm have h13 : x1 ≠ x3 := hx3ne1.symm have h14 : x1 ≠ x4 := hx4ne1.symm have h23 : x2 ≠ x3 := hx3ne2.symm have h24 : x2 ≠ x4 := hx4ne2.symm have h34 : x3 ≠ x4 := hx4ne3.symm have hsub : ({x1,x2,x3,x4} : Finset α) ⊆ P := by intro y hy simp only [Finset.mem_insert, Finset.mem_singleton] at hy rcases hy with rfl | rfl | rfl | rfl · exact hx1P · exact hx2P · exact hx3P · exact hx4P have hAcard : ({x1,x2,x3,x4} : Finset α).card = 4 := digraph_qkw_card_four_set x1 x2 x3 x4 h12 h13 h14 h23 h24 h34
There exists a 3-element kernel-perfect subset T ⊆ {x₁, x₂, x₃, x₄} containing x₁, and a quasi-kernel Q that out-dominates T.
By the structural lemma digraph_four_vertices_kernel_perfect_triple, any 4-vertex induced subgraph in a loopless digraph contains a 3-vertex kernel-perfect subset T containing x₁. By digraph_kernel_perfect_subset_quasikernel_cover, there is a quasi-kernel Q whose closed out-neighborhood covers T.
uses
digraph_four_vertices_kernel_perfect_triple,digraph_kernel_perfect_subset_quasikernel_coverhave hx1A : x1 ∈ ({x1,x2,x3,x4} : Finset α) := by simp obtain ⟨T, hTA, hx1T, hTcard, hTkp⟩ := digraph_four_vertices_kernel_perfect_triple D hloop ({x1,x2,x3,x4} : Finset α) hAcard x1 hx1A obtain ⟨Q, hQind, hQcover, hQT, hQout⟩ := digraph_kernel_perfect_subset_quasikernel_cover D T hTkp refine ⟨Q, hQind, hQcover, ?_⟩
The quasi-kernel Q captures at least half the total weight in its closed out-neighborhood, completing the theorem.
We verify that x₁, x₂, x₃, x₄ satisfy the maximal weight conditions of digraph_qkw_weight_four_bound, which implies w(P) ≤ 2 * w(T). Since T is contained in the closed out-neighborhood N⁺[Q] and weights are non-negative, w(T) ≤ w(N⁺[Q]). Therefore, w(V) = w(P) ≤ 2 * w(T) ≤ 2 * w(N⁺[Q]).
uses
Finset.mem_erase.mpr,digraph_qkw_weight_four_bound,Finset.mem_filter.mpr,Finset.mem_univ,Finset.sum_le_sum_of_subset_of_nonneg,Nat.zero_le,Nat.mul_le_mul_lefthave hx2maxP : ∀ y ∈ P, y ≠ x1 → w y ≤ w x2 := by intro y hyP hyne exact hx2max y (Finset.mem_erase.mpr ⟨hyne, hyP⟩) have hx3maxP : ∀ y ∈ P, y ≠ x1 → y ≠ x2 → w y ≤ w x3 := by intro y hyP hy1 hy2 exact hx3max y (Finset.mem_erase.mpr ⟨hy2, Finset.mem_erase.mpr ⟨hy1, hyP⟩⟩) have hx4maxP : ∀ y ∈ P, y ≠ x1 → y ≠ x2 → y ≠ x3 → w y ≤ w x4 := by intro y hyP hy1 hy2 hy3 exact hx4max y (Finset.mem_erase.mpr ⟨hy3, Finset.mem_erase.mpr ⟨hy2, Finset.mem_erase.mpr ⟨hy1, hyP⟩⟩⟩) have hweight := digraph_qkw_weight_four_bound P T w x1 x2 x3 x4 h12 h13 h14 h23 h24 h34 hsub hPcard hx1max hx2maxP hx3maxP hx4maxP hTA hTcard hx1T have hTN : T ⊆ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v) := by intro s hs obtain ⟨q, hqQ, hq⟩ := hQT s hs exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, q, hqQ, hq⟩ have hsumN : ∑ v ∈ T, w v ≤ ∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v := Finset.sum_le_sum_of_subset_of_nonneg hTN (fun i _ _ => Nat.zero_le _) calc ∑ v ∈ Finset.univ, w v = ∑ v ∈ P, w v := hsumP.symm _ ≤ 2 * ∑ v ∈ T, w v := hweight _ ≤ 2 * ∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v := Nat.mul_le_mul_left 2 hsumN
Finset.card_insert_of_notMem- inserting an element not already in a finite set increases its cardinality by 1
Finset.card_singleton- a singleton set has cardinality 1
Nat.lt_or_ge- for any natural numbers n and m, either n < m or n ≥ m
Finset.Subset.refl- every finite set is a subset of itself
Finset.card_pos.mp- a finite set with strictly positive cardinality is non-empty
Finset.exists_max_image- every non-empty finite set contains an element maximizing a given real- or integer-valued function
Finset.card_erase_of_mem- removing an element from a finite set decreases its cardinality by 1
Finset.mem_of_mem_erase- an element belonging to s minus {a} belongs to s
Finset.mem_erase.mp- an element belongs to s minus {a} only if it is distinct from a and belongs to s
Finset.erase_subset- removing an element from a finite set yields a subset of the original set
Finset.mem_erase.mpr- if an element is distinct from a and belongs to s, it belongs to s minus {a}
Finset.single_le_sum- for non-negative terms, a single term is at most the sum over a set containing it
Nat.zero_le- zero is at most any natural number
Finset.add_sum_erase- the sum over s equals the value at a plus the sum over s minus {a}
digraph_qkw_card_four_set- a set of four pairwise distinct elements has cardinality 4
Finset.sum_insert- the sum over {a} ∪ s equals f(a) plus the sum over s, provided a ∉ s
Finset.sum_singleton- the sum of a function over a singleton set {a} is f(a)
Finset.card_sdiff- the cardinality of t minus s equals |t| minus |s ∩ t|
Finset.inter_eq_left.mpr- if s ⊆ t, then s ∩ t = s
Finset.mem_sdiff- an element belongs to s minus t if and only if it belongs to s and not to t
Finset.sum_le_card_nsmul- if every element of s has value at most n, the sum over s is at most |s| times n
Nat.mul_le_mul_right- if n ≤ m, then n * k ≤ m * k
Finset.card_eq_one.mp- a finite set of cardinality 1 is a singleton
Finset.mem_sdiff.mp- if an element is in s minus t, it is in s and not in t
Finset.sum_sdiff- if s₁ ⊆ s₂, the sum over s₂ minus s₁ plus the sum over s₁ equals the sum over s₂
Ne.symm- if a ≠ b then b ≠ a
le_trans- if a ≤ b and b ≤ c, then a ≤ c
Finset.card_le_card- a subset has cardinality at most that of the superset
Finset.card_eq_zero.mp- a finite set of cardinality 0 is empty
Finset.empty_subset- the empty set is a subset of every set
Finset.mem_singleton- b ∈ {a} if and only if b = a
Finset.mem_singleton_self- every element belongs to its own singleton
Or.inl- from A, deduce A ∨ B
Finset.card_eq_two.mp- a finite set of cardinality 2 consists of two distinct elements
Or.inr- from B, deduce A ∨ B
Finset.mem_insert- membership in an inserted set is membership in the rest or equality with the inserted element
Finset.sum_subset- sums over a superset and a subset coincide if all elements outside the subset have value 0
Finset.subset_univ- every finite set is a subset of the universe
Finset.mem_filter.mpr- an element satisfying a predicate belongs to the filtered set
Finset.mem_univ- every element of a finite type belongs to the universal set Finset.univ
digraph_qkw_weight_small_support- any set of at most 3 vertices contains a subset of at most 2 vertices with at least half the total weight
digraph_qkw_kp_of_card_le_two- in a loopless digraph, any subset of at most 2 vertices is kernel-perfect
digraph_kernel_perfect_subset_quasikernel_cover- any kernel-perfect subset of a digraph is out-dominated by some quasi-kernel of the digraph
Finset.sum_le_sum_of_subset_of_nonneg- a sum over a subset is at most the sum over a superset when all terms are non-negative
Nat.mul_le_mul_left- if n ≤ m, then k * n ≤ k * m
digraph_four_vertices_kernel_perfect_triple- every 4-vertex induced subgraph in a loopless digraph contains a 3-vertex kernel-perfect subset containing any chosen vertex
digraph_qkw_weight_four_bound- for the four heaviest vertices x₁, x₂, x₃, x₄ in greedy order in a set of at most 6 vertices, any 3 of them containing x₁ capture at least half the total weight
- The proof relies on two structural results proved elsewhere in the development: every loopless 4-vertex induced subgraph contains a 3-vertex kernel-perfect subset containing any chosen vertex (digraph_four_vertices_kernel_perfect_triple), and every kernel-perfect subset can be out-dominated by a quasi-kernel of the whole digraph (digraph_kernel_perfect_subset_quasikernel_cover).
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.
private lemma digraph_qkw_card_four_set {α : Type} [DecidableEq α] (a b c d : α) (h1 : a ≠ b) (h2 : a ≠ c) (h3 : a ≠ d) (h4 : b ≠ c) (h5 : b ≠ d) (h6 : c ≠ d) : ({a,b,c,d} : Finset α).card = 4 := by rw [show ({a,b,c,d} : Finset α) = insert a (insert b (insert c ({d} : Finset α))) from rfl] rw [Finset.card_insert_of_notMem (by simp [h1, h2, h3]), Finset.card_insert_of_notMem (by simp [h4, h5]), Finset.card_insert_of_notMem (by simp [h6]), Finset.card_singleton]private lemma digraph_qkw_weight_small_support {α : Type} [DecidableEq α] (P : Finset α) (w : α → ℕ) (h : P.card ≤ 3) : ∃ S : Finset α, S ⊆ P ∧ S.card ≤ 2 ∧ (∑ v ∈ P, w v) ≤ 2 * (∑ v ∈ S, w v) := by rcases Nat.lt_or_ge P.card 3 with h3 | h3 · exact ⟨P, Finset.Subset.refl P, by omega, by omega⟩ · have hne : P.Nonempty := Finset.card_pos.mp (by omega) obtain ⟨x1, hx1, hx1max⟩ := Finset.exists_max_image P w hne have hcard1 : (P.erase x1).card = 2 := by rw [Finset.card_erase_of_mem hx1]; omega have hne1 : (P.erase x1).Nonempty := Finset.card_pos.mp (by omega) obtain ⟨y, hy⟩ := hne1 have hyP : y ∈ P := Finset.mem_of_mem_erase hy have hyx : y ≠ x1 := (Finset.mem_erase.mp hy).1 refine ⟨P.erase y, Finset.erase_subset y P, ?_, ?_⟩ · rw [Finset.card_erase_of_mem hyP]; omega · have hx1mem : x1 ∈ P.erase y := Finset.mem_erase.mpr ⟨hyx.symm, hx1⟩ have hle : w x1 ≤ ∑ v ∈ P.erase y, w v := Finset.single_le_sum (f := w) (fun i _ => Nat.zero_le _) hx1mem have hsplit : ∑ v ∈ P, w v = w y + ∑ v ∈ P.erase y, w v := (Finset.add_sum_erase P w hyP).symm have hxy : w y ≤ w x1 := hx1max y hyP omegaprivate lemma digraph_qkw_weight_four_bound {α : Type} [DecidableEq α] (P T : Finset α) (w : α → ℕ) (x1 x2 x3 x4 : α) (h12 : x1 ≠ x2) (h13 : x1 ≠ x3) (h14 : x1 ≠ x4) (h23 : x2 ≠ x3) (h24 : x2 ≠ x4) (h34 : x3 ≠ x4) (hsub : ({x1, x2, x3, x4} : Finset α) ⊆ P) (hP6 : P.card ≤ 6) (hx1max : ∀ y ∈ P, w y ≤ w x1) (hx2max : ∀ y ∈ P, y ≠ x1 → w y ≤ w x2) (hx3max : ∀ y ∈ P, y ≠ x1 → y ≠ x2 → w y ≤ w x3) (hx4max : ∀ y ∈ P, y ≠ x1 → y ≠ x2 → y ≠ x3 → w y ≤ w x4) (hTsub : T ⊆ ({x1, x2, x3, x4} : Finset α)) (hT3 : T.card = 3) (hx1T : x1 ∈ T) : ∑ v ∈ P, w v ≤ 2 * ∑ v ∈ T, w v := by have hA4 : ({x1,x2,x3,x4} : Finset α).card = 4 := digraph_qkw_card_four_set x1 x2 x3 x4 h12 h13 h14 h23 h24 h34 have hsumA : ∑ v ∈ ({x1,x2,x3,x4} : Finset α), w v = w x1 + w x2 + w x3 + w x4 := by rw [show ({x1,x2,x3,x4} : Finset α) = insert x1 (insert x2 (insert x3 ({x4} : Finset α))) from rfl] rw [Finset.sum_insert (by simp [h12, h13, h14]), Finset.sum_insert (by simp [h23, h24]), Finset.sum_insert (by simp [h34]), Finset.sum_singleton] omega have hcard : (P \ ({x1,x2,x3,x4} : Finset α)).card ≤ 2 := by rw [Finset.card_sdiff, Finset.inter_eq_left.mpr hsub, hA4] omega have hbound_out : ∀ y ∈ P \ ({x1,x2,x3,x4} : Finset α), w y ≤ w x4 := by intro y hy rw [Finset.mem_sdiff] at hy obtain ⟨hyP, hyA⟩ := hy have hy1 : y ≠ x1 := by intro h; exact hyA (h ▸ (by simp : x1 ∈ ({x1,x2,x3,x4} : Finset α))) have hy2 : y ≠ x2 := by intro h; exact hyA (h ▸ (by simp : x2 ∈ ({x1,x2,x3,x4} : Finset α))) have hy3 : y ≠ x3 := by intro h; exact hyA (h ▸ (by simp : x3 ∈ ({x1,x2,x3,x4} : Finset α))) exact hx4max y hyP hy1 hy2 hy3 have hsumout : ∑ v ∈ P \ ({x1,x2,x3,x4} : Finset α), w v ≤ 2 * w x4 := by have h1 := Finset.sum_le_card_nsmul (P \ ({x1,x2,x3,x4} : Finset α)) w (w x4) hbound_out have h2 : (P \ ({x1,x2,x3,x4} : Finset α)).card * w x4 ≤ 2 * w x4 := Nat.mul_le_mul_right (w x4) hcard calc ∑ v ∈ P \ ({x1,x2,x3,x4} : Finset α), w v ≤ (P \ ({x1,x2,x3,x4} : Finset α)).card • w x4 := h1 _ = (P \ ({x1,x2,x3,x4} : Finset α)).card * w x4 := by simp _ ≤ 2 * w x4 := h2 have hdiff1 : (({x1,x2,x3,x4} : Finset α) \ T).card = 1 := by rw [Finset.card_sdiff, Finset.inter_eq_left.mpr hTsub, hT3, hA4] obtain ⟨y, hy_eq⟩ := Finset.card_eq_one.mp hdiff1 have hyA : y ∈ ({x1,x2,x3,x4} : Finset α) := by have hh : y ∈ ({x1,x2,x3,x4} : Finset α) \ T := by rw [hy_eq]; simp exact (Finset.mem_sdiff.mp hh).1 have hyT : y ∉ T := by have hh : y ∈ ({x1,x2,x3,x4} : Finset α) \ T := by rw [hy_eq]; simp exact (Finset.mem_sdiff.mp hh).2 have hyP : y ∈ P := hsub hyA have hy1 : y ≠ x1 := by intro h; exact hyT (h ▸ hx1T) have hwy : w y ≤ w x2 := hx2max y hyP hy1 have hsumT : ∑ v ∈ ({x1,x2,x3,x4} : Finset α), w v = w y + ∑ v ∈ T, w v := by have h := Finset.sum_sdiff (f := w) hTsub rw [hy_eq, Finset.sum_singleton] at h omega have hsplit : ∑ v ∈ P, w v = ∑ v ∈ ({x1,x2,x3,x4} : Finset α), w v + ∑ v ∈ P \ ({x1,x2,x3,x4} : Finset α), w v := by have h := Finset.sum_sdiff (f := w) hsub omega have hx2le1 : w x2 ≤ w x1 := hx1max x2 (hsub (by simp)) have hx4le3 : w x4 ≤ w x3 := hx3max x4 (hsub (by simp)) (Ne.symm h14) (Ne.symm h24) omegaprivate lemma digraph_qkw_kp_of_card_le_two {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (S : Finset α) (hS : S.card ≤ 2) : ∀ T ⊆ S, ∃ K ⊆ T, (∀ u ∈ K, ∀ v ∈ K, u ≠ v → ¬ D.Adj u v) ∧ (∀ v ∈ T, ∃ u ∈ K, u = v ∨ D.Adj u v) := by intro T hT have hTcard : T.card ≤ 2 := le_trans (Finset.card_le_card hT) hS rcases Nat.lt_or_ge T.card 2 with h2 | h2 · rcases Nat.lt_or_ge T.card 1 with h1 | h1 · have h0 : T.card = 0 := by omega have hT0 : T = ∅ := Finset.card_eq_zero.mp h0 refine ⟨∅, Finset.empty_subset _, ?_, ?_⟩ · intro u hu; simp at hu · intro v hv; rw [hT0] at hv; simp at hv · have h1' : T.card = 1 := by omega obtain ⟨a, ha⟩ := Finset.card_eq_one.mp h1' refine ⟨{a}, ?_, ?_, ?_⟩ · intro x hx; simpa [ha] using hx · intro u hu v hv huv rw [Finset.mem_singleton] at hu hv exact (huv (hu.trans hv.symm)).elim · intro v hv rw [ha, Finset.mem_singleton] at hv exact ⟨a, Finset.mem_singleton_self a, Or.inl hv.symm⟩ · have h2' : T.card = 2 := by omega obtain ⟨a, b, hab, hT2⟩ := Finset.card_eq_two.mp h2' rw [hT2] by_cases habA : D.Adj a b · refine ⟨{a}, ?_, ?_, ?_⟩ · intro x hx; rw [Finset.mem_singleton] at hx; rw [hx]; simp · intro u hu v hv huv rw [Finset.mem_singleton] at hu hv exact (huv (hu.trans hv.symm)).elim · intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with hv | hv · exact ⟨a, Finset.mem_singleton_self a, Or.inl hv.symm⟩ · refine ⟨a, Finset.mem_singleton_self a, Or.inr ?_⟩ rw [hv]; exact habA · by_cases hbaA : D.Adj b a · refine ⟨{b}, ?_, ?_, ?_⟩ · intro x hx; rw [Finset.mem_singleton] at hx; rw [hx]; simp · intro u hu v hv huv rw [Finset.mem_singleton] at hu hv exact (huv (hu.trans hv.symm)).elim · intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with hv | hv · refine ⟨b, Finset.mem_singleton_self b, Or.inr ?_⟩ rw [hv]; exact hbaA · exact ⟨b, Finset.mem_singleton_self b, Or.inl hv.symm⟩ · refine ⟨{a, b}, ?_, ?_, ?_⟩ · intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx ⊢ tauto · intro u hu v hv huv simp only [Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with hu | hu <;> rcases hv with hv | hv · exact (huv (hu.trans hv.symm)).elim · rw [hu, hv]; exact habA · rw [hu, hv]; exact hbaA · exact (huv (hu.trans hv.symm)).elim · intro v hv exact ⟨v, hv, Or.inl rfl⟩theorem digraph_quasikernel_weighted_half_cover_support_six {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (w : α → ℕ) (hsupport : (Finset.univ.filter (fun v => w v ≠ 0)).card ≤ 6) : ∃ 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 classical set P : Finset α := Finset.univ.filter (fun v => w v ≠ 0) with hP have hPcard : P.card ≤ 6 := hsupport have hsumP : (∑ v ∈ P, w v) = ∑ v ∈ Finset.univ, w v := by refine Finset.sum_subset (Finset.subset_univ P) ?_ intro x _ hx have hx' : ¬ (w x ≠ 0) := by intro h exact hx (by rw [hP]; exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩) simpa using hx' rcases Nat.lt_or_ge P.card 4 with hlt | hge · have hsmall : P.card ≤ 3 := by omega obtain ⟨S, hSP, hScard, hSweight⟩ := digraph_qkw_weight_small_support P w hsmall have hkp := digraph_qkw_kp_of_card_le_two D hloop S hScard obtain ⟨Q, hQind, hQcover, hQS, hQout⟩ := digraph_kernel_perfect_subset_quasikernel_cover D S hkp refine ⟨Q, hQind, hQcover, ?_⟩ have hSN : S ⊆ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v) := by intro s hs obtain ⟨q, hqQ, hq⟩ := hQS s hs exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, q, hqQ, hq⟩ have hsumN : ∑ v ∈ S, w v ≤ ∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v := Finset.sum_le_sum_of_subset_of_nonneg hSN (fun i _ _ => Nat.zero_le _) calc ∑ v ∈ Finset.univ, w v = ∑ v ∈ P, w v := hsumP.symm _ ≤ 2 * ∑ v ∈ S, w v := hSweight _ ≤ 2 * ∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v := Nat.mul_le_mul_left 2 hsumN · have h4 : 4 ≤ P.card := hge obtain ⟨x1, hx1P, hx1max⟩ := Finset.exists_max_image P w (Finset.card_pos.mp (by omega)) have hc1 : (P.erase x1).card = P.card - 1 := Finset.card_erase_of_mem hx1P have hne1 : (P.erase x1).Nonempty := Finset.card_pos.mp (by omega) obtain ⟨x2, hx2e, hx2max⟩ := Finset.exists_max_image (P.erase x1) w hne1 have hx2P : x2 ∈ P := Finset.mem_of_mem_erase hx2e have hx2ne : x2 ≠ x1 := (Finset.mem_erase.mp hx2e).1 have hc2 : ((P.erase x1).erase x2).card = P.card - 2 := by rw [Finset.card_erase_of_mem hx2e, hc1]; omega have hne2 : ((P.erase x1).erase x2).Nonempty := Finset.card_pos.mp (by omega) obtain ⟨x3, hx3e, hx3max⟩ := Finset.exists_max_image ((P.erase x1).erase x2) w hne2 have hx3P : x3 ∈ P := Finset.mem_of_mem_erase (Finset.mem_of_mem_erase hx3e) have hx3ne1 : x3 ≠ x1 := (Finset.mem_erase.mp (Finset.mem_of_mem_erase hx3e)).1 have hx3ne2 : x3 ≠ x2 := (Finset.mem_erase.mp hx3e).1 have hc3 : (((P.erase x1).erase x2).erase x3).card = P.card - 3 := by rw [Finset.card_erase_of_mem hx3e, hc2]; omega have hne3 : (((P.erase x1).erase x2).erase x3).Nonempty := Finset.card_pos.mp (by omega) obtain ⟨x4, hx4e, hx4max⟩ := Finset.exists_max_image (((P.erase x1).erase x2).erase x3) w hne3 have hx4e' : x4 ∈ (P.erase x1).erase x2 := (Finset.mem_erase.mp hx4e).2 have hx4ne3 : x4 ≠ x3 := (Finset.mem_erase.mp hx4e).1 have hx4ne2 : x4 ≠ x2 := (Finset.mem_erase.mp hx4e').1 have hx4e'' : x4 ∈ P.erase x1 := (Finset.mem_erase.mp hx4e').2 have hx4ne1 : x4 ≠ x1 := (Finset.mem_erase.mp hx4e'').1 have hx4P : x4 ∈ P := Finset.mem_of_mem_erase hx4e'' have h12 : x1 ≠ x2 := hx2ne.symm have h13 : x1 ≠ x3 := hx3ne1.symm have h14 : x1 ≠ x4 := hx4ne1.symm have h23 : x2 ≠ x3 := hx3ne2.symm have h24 : x2 ≠ x4 := hx4ne2.symm have h34 : x3 ≠ x4 := hx4ne3.symm have hsub : ({x1,x2,x3,x4} : Finset α) ⊆ P := by intro y hy simp only [Finset.mem_insert, Finset.mem_singleton] at hy rcases hy with rfl | rfl | rfl | rfl · exact hx1P · exact hx2P · exact hx3P · exact hx4P have hAcard : ({x1,x2,x3,x4} : Finset α).card = 4 := digraph_qkw_card_four_set x1 x2 x3 x4 h12 h13 h14 h23 h24 h34 have hx1A : x1 ∈ ({x1,x2,x3,x4} : Finset α) := by simp obtain ⟨T, hTA, hx1T, hTcard, hTkp⟩ := digraph_four_vertices_kernel_perfect_triple D hloop ({x1,x2,x3,x4} : Finset α) hAcard x1 hx1A obtain ⟨Q, hQind, hQcover, hQT, hQout⟩ := digraph_kernel_perfect_subset_quasikernel_cover D T hTkp refine ⟨Q, hQind, hQcover, ?_⟩ have hx2maxP : ∀ y ∈ P, y ≠ x1 → w y ≤ w x2 := by intro y hyP hyne exact hx2max y (Finset.mem_erase.mpr ⟨hyne, hyP⟩) have hx3maxP : ∀ y ∈ P, y ≠ x1 → y ≠ x2 → w y ≤ w x3 := by intro y hyP hy1 hy2 exact hx3max y (Finset.mem_erase.mpr ⟨hy2, Finset.mem_erase.mpr ⟨hy1, hyP⟩⟩) have hx4maxP : ∀ y ∈ P, y ≠ x1 → y ≠ x2 → y ≠ x3 → w y ≤ w x4 := by intro y hyP hy1 hy2 hy3 exact hx4max y (Finset.mem_erase.mpr ⟨hy3, Finset.mem_erase.mpr ⟨hy2, Finset.mem_erase.mpr ⟨hy1, hyP⟩⟩⟩) have hweight := digraph_qkw_weight_four_bound P T w x1 x2 x3 x4 h12 h13 h14 h23 h24 h34 hsub hPcard hx1max hx2maxP hx3maxP hx4maxP hTA hTcard hx1T have hTN : T ⊆ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v) := by intro s hs obtain ⟨q, hqQ, hq⟩ := hQT s hs exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, q, hqQ, hq⟩ have hsumN : ∑ v ∈ T, w v ≤ ∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v := Finset.sum_le_sum_of_subset_of_nonneg hTN (fun i _ _ => Nat.zero_le _) calc ∑ v ∈ Finset.univ, w v = ∑ v ∈ P, w v := hsumP.symm _ ≤ 2 * ∑ v ∈ T, w v := hweight _ ≤ 2 * ∑ v ∈ Finset.univ.filter (fun v => ∃ q ∈ Q, q = v ∨ D.Adj q v), w v := Nat.mul_le_mul_left 2 hsumN