AFTD Auto-Formalizing Theoretical Domains

digraph_quasikernel_weighted_half_cover_support_six

theoremverified

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

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.

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

    lines 4–7

    uses Finset.card_insert_of_notMem, Finset.card_singleton

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

    lines 12–13

    uses Nat.lt_or_ge, Finset.Subset.refl

      rcases Nat.lt_or_ge P.card 3 with h3 | h3
      · exact ⟨P, Finset.Subset.refl P, by omega, by omega⟩
  3. 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).

    lines 14–29

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

    lines 46–72

    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_right

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

    lines 73–94

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

      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)
      omega
  6. 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.

    lines 102–120

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

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

    lines 121–160

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

    lines 172–181

    uses Finset.sum_subset, Finset.subset_univ, Finset.mem_filter.mpr, Finset.mem_univ

      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'
  9. 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]).

    lines 182–197

    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_left

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

    lines 198–237

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

    lines 238–242

    uses digraph_four_vertices_kernel_perfect_triple, digraph_kernel_perfect_subset_quasikernel_cover

        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, ?_⟩
  12. 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]).

    lines 243–263

    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_left

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

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

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