AFTD Auto-Formalizing Theoretical Domains

simple_graph_maximum_independent_set_weighted_overlap_of_clique_four

theoremverified

In a finite graph with no clique of size five, every nonnegative vertex weighting admits a maximum independent set whose weighted overlap score is at least three halves of the total weight, counting a vertex in the independent set with score three and any other vertex by its number of neighbors in the set.

Statement

theorem simple_graph_maximum_independent_set_weighted_overlap_of_clique_four
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (w : V → ℝ) (hw : ∀ v, 0 ≤ w v)
    (hclique : ∀ C : Finset V, G.IsClique C → C.card ≤ 4) :
    ∃ S : Finset V, G.IsIndepSet S ∧
      (∀ T : Finset V, G.IsIndepSet T → T.card ≤ S.card) ∧
      3 * (∑ v : V, w v) ≤
        6 * (∑ v ∈ S, w v) +
          2 * ∑ v ∈ (Finset.univ \ S), w v * ((S.filter (G.Adj v)).card : ℝ)
Source
Elementary maximum-independent-set exchange in the triangle packing-cover campaign; related graph background: https://arxiv.org/abs/2609.13831.
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof selects a maximum-cardinality independent set S that, among all maximum independent sets, maximizes the total weight ∑_{v ∈ S} w(v). On the complement B = V \ S, every vertex has at least one neighbor in S, and the subset P ⊆ B of vertices with exactly one neighbor in S partitions into fibers around their unique neighbors in S. For each s ∈ S, any v ∈ P adjacent to s satisfies w(v) ≤ w(s) by weight-maximality under vertex swap, and {s} ∪ (P ∩ N(s)) forms a clique, bounding the fiber size by 3 since G has no 5-clique. Bounding 3 - 2|S ∩ N(v)| by 1 on P and by 0 on B \ P then leads directly to the desired inequality.

  1. There exists an independent set S ⊆ V of maximum cardinality that, among all maximum-cardinality independent sets, maximizes the total weight ∑_{v ∈ S} w(v).

    The family of all independent sets in G is finite and nonempty (since the empty set is independent). We first select an independent set S₀ of maximum cardinality using `Finset.exists_max_image`. Then, from the subfamily of independent sets with cardinality equal to |S₀|, we select S to maximize the total weight ∑_{v ∈ S} w(v). By construction, S is an independent set of maximum cardinality, and any other maximum-cardinality independent set has weight at most that of S.

    lines 10–38

    uses Finset.exists_max_image, Finset.mem_filter, Finset.mem_univ, true_and

      classical
      obtain ⟨S, hS_indep, hS_maxcard, hS_maxweight⟩ :
          ∃ S : Finset V, G.IsIndepSet S ∧
            (∀ T : Finset V, G.IsIndepSet T → T.card ≤ S.card) ∧
            (∀ T : Finset V, G.IsIndepSet T → T.card = S.card →
              ∑ v ∈ T, w v ≤ ∑ v ∈ S, w v) := by
        let Fam : Finset (Finset V) := Finset.univ.filter (fun T => G.IsIndepSet T)
        have hne : Fam.Nonempty := ⟨∅, by simp [Fam]⟩
        obtain ⟨S0, hS0fam, hS0max⟩ := Finset.exists_max_image Fam (fun T => T.card) hne
        have hS0_indep : G.IsIndepSet S0 := by
          have h := hS0fam; simp only [Fam, Finset.mem_filter, Finset.mem_univ, true_and] at h; exact h
        let Fam2 : Finset (Finset V) := Fam.filter (fun T => T.card = S0.card)
        have hne2 : Fam2.Nonempty := ⟨S0, by simp [Fam2, hS0fam]⟩
        obtain ⟨S, hSfam2, hSmax⟩ := Finset.exists_max_image Fam2 (fun T => ∑ v ∈ T, w v) hne2
        have hSfam : S ∈ Fam := (Finset.mem_filter.mp hSfam2).1
        have hScard : S.card = S0.card := (Finset.mem_filter.mp hSfam2).2
        have hS_indep : G.IsIndepSet S := by
          have h := hSfam; simp only [Fam, Finset.mem_filter, Finset.mem_univ, true_and] at h; exact h
        refine ⟨S, hS_indep, ?_, ?_⟩
        · intro T hT
          have hTFam : T ∈ Fam := by simp [Fam, hT]
          have hle := hS0max T hTFam
          omega
        · intro T hT hTc
          have hTfam : T ∈ Fam := by simp [Fam, hT]
          have hTcard : T.card = S0.card := by omega
          have hTfam2 : T ∈ Fam2 := by simp [Fam2, hTfam, hTcard]
          exact hSmax T hTfam2
      refine ⟨S, hS_indep, hS_maxcard, ?_⟩
  2. Defining B = V \ S, every vertex in B is disjoint from S, and replacing a vertex s ∈ A in an independent set A by v yields an independent set provided v has no edges to A \ {s}.

    We define B = V \ S. To verify the replacement property `indep_ins`, let A be an independent set and consider A' = (A \ {s}) ∪ {v}. Any two distinct vertices in A' are non-adjacent: if both lie in A \ {s}, they are non-adjacent because A is independent; if one is v and the other is b ∈ A \ {s}, they are non-adjacent by the hypothesis on v. Hence A' is an independent set.

    lines 39–56

    uses SimpleGraph.IsIndepSet, Set.Pairwise, Finset.mem_coe, Finset.mem_insert, Finset.mem_erase, Finset.mem_sdiff.mp

      set B : Finset V := Finset.univ \ S with hB
      have hB_notS : ∀ v ∈ B, v ∉ S := by
        intro v hv
        rw [hB] at hv
        exact (Finset.mem_sdiff.mp hv).2
      have indep_ins : ∀ (A : Finset V) (s v : V), G.IsIndepSet A →
          (∀ a ∈ A, a ≠ s → ¬ G.Adj v a) → G.IsIndepSet ((insert v (A.erase s) : Finset V) : Set V) := by
        intro A s v hA hv
        rw [SimpleGraph.IsIndepSet, Set.Pairwise] at hA ⊢
        intro a ha b hb hab
        simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_erase] at ha hb
        rcases ha with hav | ⟨ha_ne, haA⟩
        · rcases hb with hbv | ⟨hb_ne, hbA⟩
          · rw [hav, hbv] at hab ⊢; exact absurd rfl hab
          · rw [hav]; exact hv b hbA hb_ne
        · rcases hb with hbv | ⟨hb_ne, hbA⟩
          · rw [hbv]; intro h; exact hv a haA ha_ne ((G.adj_comm a v).mp h)
          · exact hA haA hbA hab
  3. Every vertex in B has at least one neighbor in S.

    Suppose for contradiction that some vertex v ∈ B has no neighbors in S. Then by `indep_ins` (erasing an element not in S), S ∪ {v} would be an independent set. Since v ∉ S, |S ∪ {v}| = |S| + 1, contradicting the fact that S is an independent set of maximum cardinality.

    lines 57–73

    uses Finset.notMem_empty, Finset.erase_eq_of_notMem, Finset.card_insert_of_notMem

      have hB_pos : ∀ v ∈ B, 1 ≤ (S.filter (G.Adj v)).card := by
        intro v hv
        by_contra h
        have hcard0 : (S.filter (G.Adj v)).card = 0 := by omega
        have hvS := hB_notS v hv
        have hno : ∀ a ∈ S, ¬ G.Adj v a := by
          intro a ha hadj
          have hmem : a ∈ S.filter (G.Adj v) := Finset.mem_filter.mpr ⟨ha, hadj⟩
          rw [Finset.card_eq_zero.mp hcard0] at hmem
          exact Finset.notMem_empty a hmem
        have hins : G.IsIndepSet ((insert v (S.erase v) : Finset V) : Set V) := by
          exact indep_ins S v v hS_indep (fun a ha _ => hno a ha)
        rw [Finset.erase_eq_of_notMem hvS] at hins
        have hc : (insert v S).card = S.card + 1 := Finset.card_insert_of_notMem hvS
        have hle := hS_maxcard (insert v S) hins
        rw [hc] at hle
        omega
  4. If a vertex v ∈ B has exactly one neighbor in S, then any neighbor of v in S is unique.

    If s ∈ S is a neighbor of v and there were another neighbor a ∈ S with a ≠ s, the pair {a, s} would be a two-element subset of S ∩ N(v), contradicting the assumption that |S ∩ N(v)| = 1.

    lines 74–86

    uses Finset.mem_insert, Finset.card_le_card, Finset.card_pair

      have priv_uniq : ∀ (v s : V), v ∈ B → (S.filter (G.Adj v)).card = 1 → s ∈ S → G.Adj v s →
          ∀ a ∈ S, G.Adj v a → a = s := by
        intro v s hvB hcard hsS hadj a haS hadja
        by_contra hne
        have hsub : ({a, s} : Finset V) ⊆ S.filter (G.Adj v) := by
          intro x hx
          simp only [Finset.mem_insert, Finset.mem_singleton] at hx
          rcases hx with rfl | rfl
          · exact Finset.mem_filter.mpr ⟨haS, hadja⟩
          · exact Finset.mem_filter.mpr ⟨hsS, hadj⟩
        have hle := Finset.card_le_card hsub
        rw [Finset.card_pair hne, hcard] at hle
        omega
  5. Let P ⊆ B be the set of vertices with exactly one neighbor in S. The total weight of P equals the sum over all s ∈ S of the total weight of vertices in P adjacent to s.

    We define P = {v ∈ B : |S ∩ N(v)| = 1}. For each v ∈ P, there is exactly one s ∈ S adjacent to v. Rewriting the inner sum with an if-then-else condition and exchanging the order of summation expresses ∑_{v ∈ P} w(v) as the double sum ∑_{s ∈ S} ∑_{v ∈ P, v ∼ s} w(v).

    lines 87–103

    uses Finset.filter_subset, Finset.mem_filter.mp, Finset.sum_filter, Finset.sum_comm, Finset.sum_congr, Finset.sum_const

      set P : Finset V := B.filter (fun v => (S.filter (G.Adj v)).card = 1) with hP
      have hPsub : P ⊆ B := by rw [hP]; exact Finset.filter_subset _ _
      have hPprop : ∀ v ∈ P, (S.filter (G.Adj v)).card = 1 := by
        intro v hv
        rw [hP] at hv
        exact (Finset.mem_filter.mp hv).2
      have hPfiber : ∑ v ∈ P, w v = ∑ s ∈ S, ∑ v ∈ P.filter (fun v => G.Adj v s), w v := by
        have h1 : ∀ s : V, (∑ v ∈ P.filter (fun v => G.Adj v s), w v)
            = ∑ v ∈ P, (if G.Adj v s then w v else 0) := by
          intro s; rw [Finset.sum_filter]
        simp_rw [h1]
        rw [Finset.sum_comm]
        refine Finset.sum_congr rfl ?_
        intro v hv
        rw [← Finset.sum_filter]
        rw [Finset.sum_const, hPprop v hv]
        simp
  6. For every s ∈ S and every v ∈ P adjacent to s, the weight of v is at most the weight of s.

    Since v ∈ P is adjacent only to s in S, replacing s with v yields a new independent set T = (S \ {s}) ∪ {v} of size |S|. Because S maximizes total weight among all independent sets of maximum cardinality, ∑_{x ∈ T} w(x) ≤ ∑_{x ∈ S} w(x). Since the two sums differ only by replacing w(s) with w(v), this simplifies to w(v) ≤ w(s).

    lines 104–126

    uses Finset.mem_filter, Finset.card_insert_of_notMem, Finset.card_erase_of_mem, Finset.sum_insert, Finset.sum_erase_add

      have hfiber_weight : ∀ s ∈ S, ∀ v ∈ P.filter (fun v => G.Adj v s), w v ≤ w s := by
        intro s hs v hv
        simp only [Finset.mem_filter] at hv
        obtain ⟨hvP, hvs⟩ := hv
        have hvB : v ∈ B := hPsub hvP
        have hcard : (S.filter (G.Adj v)).card = 1 := hPprop v hvP
        have hvS : v ∉ S := hB_notS v hvB
        have hins : G.IsIndepSet ((insert v (S.erase s) : Finset V) : Set V) := by
          apply indep_ins S s v hS_indep
          intro a ha hane hadj
          exact hane (priv_uniq v s hvB hcard hs hvs a ha hadj)
        have hcardT : (insert v (S.erase s) : Finset V).card = S.card := by
          rw [Finset.card_insert_of_notMem (by simp [Finset.mem_erase, hvS]),
              Finset.card_erase_of_mem hs]
          have : 0 < S.card := Finset.card_pos.mpr ⟨s, hs⟩
          omega
        have hle := hS_maxweight (insert v (S.erase s)) hins hcardT
        have hsum : ∑ x ∈ (insert v (S.erase s) : Finset V), w x = w v + (∑ x ∈ S, w x - w s) := by
          rw [Finset.sum_insert (by simp [Finset.mem_erase, hvS])]
          have h := Finset.sum_erase_add (s := S) (f := w) hs
          linarith
        rw [hsum] at hle
        linarith
  7. For each s ∈ S, at most 3 vertices in P are adjacent to s.

    Consider C = {s} ∪ {v ∈ P : v ∼ s}. We claim C is a clique. By definition, s is adjacent to each v ∈ P in C. Furthermore, if two distinct vertices a, b ∈ P adjacent to s were non-adjacent, then (S \ {s}) ∪ {a, b} would be an independent set of size |S| + 1, contradicting the maximality of |S|. Thus C is indeed a clique. Since G contains no clique of size 5, |C| ≤ 4. Since s ∉ B ⊇ P, |C| = 1 + |{v ∈ P : v ∼ s}|, which forces |{v ∈ P : v ∼ s}| ≤ 3.

    lines 127–180

    uses Finset.mem_filter, SimpleGraph.IsClique, Set.Pairwise, Finset.mem_coe, Finset.mem_insert, Finset.card_insert_of_notMem, Finset.card_erase_of_mem

      have hfiber_card : ∀ s ∈ S, (P.filter (fun v => G.Adj v s)).card ≤ 3 := by
        intro s hs
        have hsnot : s ∉ P.filter (fun v => G.Adj v s) := by
          simp only [Finset.mem_filter]
          rintro ⟨hps, hadj⟩
          exact hB_notS s (hPsub hps) hs
        have hcl : G.IsClique ((insert s (P.filter (fun v => G.Adj v s)) : Finset V) : Set V) := by
          rw [SimpleGraph.IsClique, Set.Pairwise]
          intro a ha b hb hab
          simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_filter] at ha hb
          rcases ha with hav | ⟨haP, haAdj⟩
          · rcases hb with hbv | ⟨hbP, hbAdj⟩
            · rw [hav, hbv] at hab ⊢; exact absurd rfl hab
            · rw [hav]; exact (G.adj_comm b s).mp hbAdj
          · rcases hb with hbv | ⟨hbP, hbAdj⟩
            · rw [hbv]; exact haAdj
            · by_contra hnab
              exfalso
              have haB : a ∈ B := hPsub haP
              have hbB : b ∈ B := hPsub hbP
              have hca : (S.filter (G.Adj a)).card = 1 := hPprop a haP
              have hcb : (S.filter (G.Adj b)).card = 1 := hPprop b hbP
              have haS : a ∉ S := hB_notS a haB
              have hbS : b ∉ S := hB_notS b hbB
              have hA1 : G.IsIndepSet ((insert a (S.erase s) : Finset V) : Set V) := by
                apply indep_ins S s a hS_indep
                intro x hx hxne hadj
                exact hxne (priv_uniq a s haB hca hs haAdj x hx hadj)
              have hb_not : b ∉ (insert a (S.erase s) : Finset V) := by
                simp only [Finset.mem_insert, Finset.mem_erase]
                rintro (hba | ⟨hne, hbS'⟩)
                · exact hab hba.symm
                · exact hbS hbS'
              have hT : G.IsIndepSet ((insert b (insert a (S.erase s)) : Finset V) : Set V) := by
                rw [← Finset.erase_eq_of_notMem hb_not]
                apply indep_ins (insert a (S.erase s)) b b hA1
                intro x hx hxne hadj
                simp only [Finset.mem_insert, Finset.mem_erase] at hx
                rcases hx with hxa | ⟨hxs, hxS⟩
                · rw [hxa] at hadj
                  exact hnab ((G.adj_comm b a).mp hadj)
                · exact hxs (priv_uniq b s hbB hcb hs hbAdj x hxS hadj)
              have hcardT : (insert b (insert a (S.erase s)) : Finset V).card = S.card + 1 := by
                rw [Finset.card_insert_of_notMem hb_not]
                rw [Finset.card_insert_of_notMem (by simp [Finset.mem_erase, haS])]
                rw [Finset.card_erase_of_mem hs]
                have : 0 < S.card := Finset.card_pos.mpr ⟨s, hs⟩
                omega
              have hle := hS_maxcard (insert b (insert a (S.erase s))) hT
              rw [hcardT] at hle
              omega
        have h4 := hclique _ hcl
        rw [Finset.card_insert_of_notMem hsnot] at h4
        omega
  8. The total vertex weight splits into the sum over S and the sum over B, and the weighted expression over B expands linearly.

    Because V = S ∪ B is a disjoint union, ∑_{v ∈ V} w(v) = ∑_{v ∈ S} w(v) + ∑_{v ∈ B} w(v). Expanding w(v)(3 - 2|S ∩ N(v)|) and distributing the summation over B yields 3 ∑_{v ∈ B} w(v) - 2 ∑_{v ∈ B} w(v)|S ∩ N(v)|.

    lines 181–190

    uses Finset.sum_sdiff, Finset.subset_univ, Finset.sum_congr, Finset.sum_sub_distrib, Finset.mul_sum

      have hWsplit : ∑ v : V, w v = ∑ v ∈ S, w v + ∑ v ∈ B, w v := by
        have h := Finset.sum_sdiff (f := w) (Finset.subset_univ S)
        rw [hB]
        linarith [h]
      have hsub : ∑ v ∈ B, (w v * (3 - 2 * ((S.filter (G.Adj v)).card : ℝ)))
          = 3 * (∑ v ∈ B, w v) - 2 * ∑ v ∈ B, w v * ((S.filter (G.Adj v)).card : ℝ) := by
        have heq : ∀ v ∈ B, w v * (3 - 2 * ((S.filter (G.Adj v)).card : ℝ))
            = 3 * w v - 2 * (w v * ((S.filter (G.Adj v)).card : ℝ)) := by
          intro v _; ring
        rw [Finset.sum_congr rfl heq, Finset.sum_sub_distrib, Finset.mul_sum, Finset.mul_sum]
  9. The weighted expression over B is bounded above by the total weight of P.

    For each v ∈ B, if |S ∩ N(v)| = 1, then v ∈ P and 3 - 2|S ∩ N(v)| = 1, contributing w(v). If |S ∩ N(v)| ≥ 2, then 3 - 2|S ∩ N(v)| ≤ -1 ≤ 0; since w(v) ≥ 0, this term is nonpositive. Summing over all v ∈ B gives ∑_{v ∈ B} w(v)(3 - 2|S ∩ N(v)|) ≤ ∑_{v ∈ P} w(v).

    lines 191–202

    uses Finset.sum_filter, Finset.sum_le_sum, if_pos, if_neg, mul_nonpos_of_nonneg_of_nonpos

      have hC : ∑ v ∈ B, (w v * (3 - 2 * ((S.filter (G.Adj v)).card : ℝ))) ≤ ∑ v ∈ P, w v := by
        rw [hP, Finset.sum_filter]
        apply Finset.sum_le_sum
        intro v hv
        by_cases hc : (S.filter (G.Adj v)).card = 1
        · rw [if_pos hc, hc]; norm_num
        · rw [if_neg hc]
          have hge : 2 ≤ (S.filter (G.Adj v)).card := by have := hB_pos v hv; omega
          have hcoef : 3 - 2 * ((S.filter (G.Adj v)).card : ℝ) ≤ 0 := by
            have : (2:ℝ) ≤ ((S.filter (G.Adj v)).card : ℝ) := by exact_mod_cast hge
            linarith
          exact mul_nonpos_of_nonneg_of_nonpos (hw v) hcoef
  10. The total weight of P is at most three times the total weight of S.

    From the fiber decomposition, ∑_{v ∈ P} w(v) = ∑_{s ∈ S} ∑_{v ∈ P, v ∼ s} w(v). For each s ∈ S, every neighbor v ∈ P satisfies w(v) ≤ w(s), so the inner sum is at most |{v ∈ P : v ∼ s}| · w(s). Since |{v ∈ P : v ∼ s}| ≤ 3 and w(s) ≥ 0, each inner sum is at most 3 w(s). Summing over all s ∈ S yields ∑_{v ∈ P} w(v) ≤ 3 ∑_{s ∈ S} w(s).

    lines 203–215

    uses Finset.mul_sum, Finset.sum_le_sum, Finset.sum_const, nsmul_eq_mul, mul_le_mul_of_nonneg_right

      have hD : ∑ v ∈ P, w v ≤ 3 * ∑ s ∈ S, w s := by
        rw [hPfiber, Finset.mul_sum]
        apply Finset.sum_le_sum
        intro s hs
        calc ∑ v ∈ P.filter (fun v => G.Adj v s), w v
            ≤ ∑ v ∈ P.filter (fun v => G.Adj v s), w s := by
              apply Finset.sum_le_sum
              intro v hv; exact hfiber_weight s hs v hv
          _ = (P.filter (fun v => G.Adj v s)).card • w s := Finset.sum_const _
          _ = ((P.filter (fun v => G.Adj v s)).card : ℝ) * w s := by rw [nsmul_eq_mul]
          _ ≤ 3 * w s := by
              apply mul_le_mul_of_nonneg_right _ (hw s)
              exact_mod_cast hfiber_card s hs
  11. The main weighted overlap inequality holds for S.

    Combining the bounds from the previous two steps yields 3 ∑_{v ∈ B} w(v) - 2 ∑_{v ∈ B} w(v)|S ∩ N(v)| ≤ 3 ∑_{s ∈ S} w(s). Adding 3 ∑_{v ∈ S} w(v) to both sides and using the split ∑_{v ∈ V} w(v) = ∑_{v ∈ S} w(v) + ∑_{v ∈ B} w(v) yields 3 ∑_{v ∈ V} w(v) ≤ 6 ∑_{v ∈ S} w(v) + 2 ∑_{v ∈ B} w(v)|S ∩ N(v)|.

    lines 216–221

      have hmain : 3 * (∑ v ∈ B, w v) - 2 * ∑ v ∈ B, w v * ((S.filter (G.Adj v)).card : ℝ)
          ≤ 3 * ∑ s ∈ S, w s := by
        rw [← hsub]
        linarith [hC, hD]
      rw [hWsplit]
      linarith [hmain]
Finset.exists_max_image
In any nonempty finite set, there exists an element that attains the maximum value under a given linearly-ordered function.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the filtering condition.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
true_and
The logical conjunction of True and a proposition p is equivalent to p.
SimpleGraph.IsIndepSet
A set of vertices is independent if no two distinct vertices in the set are adjacent.
Set.Pairwise
A set satisfies a pairwise relation if the relation holds between every pair of distinct elements in the set.
Finset.mem_coe
An element belongs to a finset coerced to a set if and only if it belongs to the finset.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_erase
An element belongs to s.erase b if and only if it is not equal to b and belongs to s.
Finset.mem_sdiff.mp
If an element belongs to the difference s \ t, then it belongs to s and does not belong to t.
Finset.notMem_empty
No element belongs to the empty finset.
Finset.erase_eq_of_notMem
Erasing an element that is not in a finset leaves the finset unchanged.
Finset.card_insert_of_notMem
Inserting an element that is not in a finset increases its cardinality by 1.
Finset.card_le_card
If a finset is a subset of another, its cardinality is at most that of the other.
Finset.card_pair
A finset containing two distinct elements has cardinality 2.
Finset.filter_subset
Filtering a finset by any predicate produces a subset of the original finset.
Finset.mem_filter.mp
If an element belongs to a filtered finset, then it belongs to the original finset and satisfies the predicate.
Finset.sum_filter
The sum of a function over a filtered finset equals the sum over the entire finset of the term guarded by an if-then-else condition.
Finset.sum_comm
The order of summation in a finite double sum can be interchanged.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their terms are equal on all elements.
Finset.sum_const
The sum of a constant value over a finset equals the cardinality of the finset multiplied by that constant.
Finset.card_erase_of_mem
Erasing an element that belongs to a finset decreases its cardinality by 1.
Finset.sum_insert
The sum of a function over insert a s, where a ∉ s, equals f(a) plus the sum over s.
Finset.sum_erase_add
For an element a ∈ s, the sum over s.erase a plus f(a) equals the sum over s.
SimpleGraph.IsClique
A set of vertices is a clique if every pair of distinct vertices in the set is adjacent.
Finset.sum_sdiff
For a subset s₁ ⊆ s₂, the sum over s₂ \ s₁ plus the sum over s₁ equals the sum over s₂.
Finset.subset_univ
Every finset of a finite type is a subset of the universal finset.
Finset.sum_sub_distrib
The sum of differences distributes into the difference of the sums.
Finset.mul_sum
Multiplication by a constant distributes over a finite sum.
Finset.sum_le_sum
If each term of one sum is at most the corresponding term of another sum over the same finset, the first sum is at most the second.
if_pos
An if-then-else expression evaluates to the then-branch when the condition is true.
if_neg
An if-then-else expression evaluates to the else-branch when the condition is false.
mul_nonpos_of_nonneg_of_nonpos
The product of a nonnegative number and a nonpositive number is nonpositive.
nsmul_eq_mul
Natural number scalar multiplication is equivalent to multiplication by the real cast of the natural number.
mul_le_mul_of_nonneg_right
Multiplying both sides of an inequality by a nonnegative number preserves the inequality.

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 simple_graph_maximum_independent_set_weighted_overlap_of_clique_four    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (w : V → ℝ) (hw : ∀ v, 0 ≤ w v)    (hclique : ∀ C : Finset V, G.IsClique C → C.card ≤ 4) :    ∃ S : Finset V, G.IsIndepSet S ∧      (∀ T : Finset V, G.IsIndepSet T → T.card ≤ S.card) ∧      3 * (∑ v : V, w v) ≤        6 * (∑ v ∈ S, w v) +          2 * ∑ v ∈ (Finset.univ \ S), w v * ((S.filter (G.Adj v)).card : ℝ) := by  classical  obtain ⟨S, hS_indep, hS_maxcard, hS_maxweight⟩ :      ∃ S : Finset V, G.IsIndepSet S ∧        (∀ T : Finset V, G.IsIndepSet T → T.card ≤ S.card) ∧        (∀ T : Finset V, G.IsIndepSet T → T.card = S.card →          ∑ v ∈ T, w v ≤ ∑ v ∈ S, w v) := by    let Fam : Finset (Finset V) := Finset.univ.filter (fun T => G.IsIndepSet T)    have hne : Fam.Nonempty := ⟨∅, by simp [Fam]⟩    obtain ⟨S0, hS0fam, hS0max⟩ := Finset.exists_max_image Fam (fun T => T.card) hne    have hS0_indep : G.IsIndepSet S0 := by      have h := hS0fam; simp only [Fam, Finset.mem_filter, Finset.mem_univ, true_and] at h; exact h    let Fam2 : Finset (Finset V) := Fam.filter (fun T => T.card = S0.card)    have hne2 : Fam2.Nonempty := ⟨S0, by simp [Fam2, hS0fam]⟩    obtain ⟨S, hSfam2, hSmax⟩ := Finset.exists_max_image Fam2 (fun T => ∑ v ∈ T, w v) hne2    have hSfam : S ∈ Fam := (Finset.mem_filter.mp hSfam2).1    have hScard : S.card = S0.card := (Finset.mem_filter.mp hSfam2).2    have hS_indep : G.IsIndepSet S := by      have h := hSfam; simp only [Fam, Finset.mem_filter, Finset.mem_univ, true_and] at h; exact h    refine ⟨S, hS_indep, ?_, ?_⟩    · intro T hT      have hTFam : T ∈ Fam := by simp [Fam, hT]      have hle := hS0max T hTFam      omega    · intro T hT hTc      have hTfam : T ∈ Fam := by simp [Fam, hT]      have hTcard : T.card = S0.card := by omega      have hTfam2 : T ∈ Fam2 := by simp [Fam2, hTfam, hTcard]      exact hSmax T hTfam2  refine ⟨S, hS_indep, hS_maxcard, ?_⟩  set B : Finset V := Finset.univ \ S with hB  have hB_notS : ∀ v ∈ B, v ∉ S := by    intro v hv    rw [hB] at hv    exact (Finset.mem_sdiff.mp hv).2  have indep_ins : ∀ (A : Finset V) (s v : V), G.IsIndepSet A →      (∀ a ∈ A, a ≠ s → ¬ G.Adj v a) → G.IsIndepSet ((insert v (A.erase s) : Finset V) : Set V) := by    intro A s v hA hv    rw [SimpleGraph.IsIndepSet, Set.Pairwise] at hA ⊢    intro a ha b hb hab    simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_erase] at ha hb    rcases ha with hav | ⟨ha_ne, haA⟩    · rcases hb with hbv | ⟨hb_ne, hbA⟩      · rw [hav, hbv] at hab ⊢; exact absurd rfl hab      · rw [hav]; exact hv b hbA hb_ne    · rcases hb with hbv | ⟨hb_ne, hbA⟩      · rw [hbv]; intro h; exact hv a haA ha_ne ((G.adj_comm a v).mp h)      · exact hA haA hbA hab  have hB_pos : ∀ v ∈ B, 1 ≤ (S.filter (G.Adj v)).card := by    intro v hv    by_contra h    have hcard0 : (S.filter (G.Adj v)).card = 0 := by omega    have hvS := hB_notS v hv    have hno : ∀ a ∈ S, ¬ G.Adj v a := by      intro a ha hadj      have hmem : a ∈ S.filter (G.Adj v) := Finset.mem_filter.mpr ⟨ha, hadj⟩      rw [Finset.card_eq_zero.mp hcard0] at hmem      exact Finset.notMem_empty a hmem    have hins : G.IsIndepSet ((insert v (S.erase v) : Finset V) : Set V) := by      exact indep_ins S v v hS_indep (fun a ha _ => hno a ha)    rw [Finset.erase_eq_of_notMem hvS] at hins    have hc : (insert v S).card = S.card + 1 := Finset.card_insert_of_notMem hvS    have hle := hS_maxcard (insert v S) hins    rw [hc] at hle    omega  have priv_uniq : ∀ (v s : V), v ∈ B → (S.filter (G.Adj v)).card = 1 → s ∈ S → G.Adj v s →      ∀ a ∈ S, G.Adj v a → a = s := by    intro v s hvB hcard hsS hadj a haS hadja    by_contra hne    have hsub : ({a, s} : Finset V) ⊆ S.filter (G.Adj v) := by      intro x hx      simp only [Finset.mem_insert, Finset.mem_singleton] at hx      rcases hx with rfl | rfl      · exact Finset.mem_filter.mpr ⟨haS, hadja⟩      · exact Finset.mem_filter.mpr ⟨hsS, hadj⟩    have hle := Finset.card_le_card hsub    rw [Finset.card_pair hne, hcard] at hle    omega  set P : Finset V := B.filter (fun v => (S.filter (G.Adj v)).card = 1) with hP  have hPsub : P ⊆ B := by rw [hP]; exact Finset.filter_subset _ _  have hPprop : ∀ v ∈ P, (S.filter (G.Adj v)).card = 1 := by    intro v hv    rw [hP] at hv    exact (Finset.mem_filter.mp hv).2  have hPfiber : ∑ v ∈ P, w v = ∑ s ∈ S, ∑ v ∈ P.filter (fun v => G.Adj v s), w v := by    have h1 : ∀ s : V, (∑ v ∈ P.filter (fun v => G.Adj v s), w v)        = ∑ v ∈ P, (if G.Adj v s then w v else 0) := by      intro s; rw [Finset.sum_filter]    simp_rw [h1]    rw [Finset.sum_comm]    refine Finset.sum_congr rfl ?_    intro v hv    rw [← Finset.sum_filter]    rw [Finset.sum_const, hPprop v hv]    simp  have hfiber_weight : ∀ s ∈ S, ∀ v ∈ P.filter (fun v => G.Adj v s), w v ≤ w s := by    intro s hs v hv    simp only [Finset.mem_filter] at hv    obtain ⟨hvP, hvs⟩ := hv    have hvB : v ∈ B := hPsub hvP    have hcard : (S.filter (G.Adj v)).card = 1 := hPprop v hvP    have hvS : v ∉ S := hB_notS v hvB    have hins : G.IsIndepSet ((insert v (S.erase s) : Finset V) : Set V) := by      apply indep_ins S s v hS_indep      intro a ha hane hadj      exact hane (priv_uniq v s hvB hcard hs hvs a ha hadj)    have hcardT : (insert v (S.erase s) : Finset V).card = S.card := by      rw [Finset.card_insert_of_notMem (by simp [Finset.mem_erase, hvS]),          Finset.card_erase_of_mem hs]      have : 0 < S.card := Finset.card_pos.mpr ⟨s, hs⟩      omega    have hle := hS_maxweight (insert v (S.erase s)) hins hcardT    have hsum : ∑ x ∈ (insert v (S.erase s) : Finset V), w x = w v + (∑ x ∈ S, w x - w s) := by      rw [Finset.sum_insert (by simp [Finset.mem_erase, hvS])]      have h := Finset.sum_erase_add (s := S) (f := w) hs      linarith    rw [hsum] at hle    linarith  have hfiber_card : ∀ s ∈ S, (P.filter (fun v => G.Adj v s)).card ≤ 3 := by    intro s hs    have hsnot : s ∉ P.filter (fun v => G.Adj v s) := by      simp only [Finset.mem_filter]      rintro ⟨hps, hadj⟩      exact hB_notS s (hPsub hps) hs    have hcl : G.IsClique ((insert s (P.filter (fun v => G.Adj v s)) : Finset V) : Set V) := by      rw [SimpleGraph.IsClique, Set.Pairwise]      intro a ha b hb hab      simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_filter] at ha hb      rcases ha with hav | ⟨haP, haAdj⟩      · rcases hb with hbv | ⟨hbP, hbAdj⟩        · rw [hav, hbv] at hab ⊢; exact absurd rfl hab        · rw [hav]; exact (G.adj_comm b s).mp hbAdj      · rcases hb with hbv | ⟨hbP, hbAdj⟩        · rw [hbv]; exact haAdj        · by_contra hnab          exfalso          have haB : a ∈ B := hPsub haP          have hbB : b ∈ B := hPsub hbP          have hca : (S.filter (G.Adj a)).card = 1 := hPprop a haP          have hcb : (S.filter (G.Adj b)).card = 1 := hPprop b hbP          have haS : a ∉ S := hB_notS a haB          have hbS : b ∉ S := hB_notS b hbB          have hA1 : G.IsIndepSet ((insert a (S.erase s) : Finset V) : Set V) := by            apply indep_ins S s a hS_indep            intro x hx hxne hadj            exact hxne (priv_uniq a s haB hca hs haAdj x hx hadj)          have hb_not : b ∉ (insert a (S.erase s) : Finset V) := by            simp only [Finset.mem_insert, Finset.mem_erase]            rintro (hba | ⟨hne, hbS'⟩)            · exact hab hba.symm            · exact hbS hbS'          have hT : G.IsIndepSet ((insert b (insert a (S.erase s)) : Finset V) : Set V) := by            rw [← Finset.erase_eq_of_notMem hb_not]            apply indep_ins (insert a (S.erase s)) b b hA1            intro x hx hxne hadj            simp only [Finset.mem_insert, Finset.mem_erase] at hx            rcases hx with hxa | ⟨hxs, hxS⟩            · rw [hxa] at hadj              exact hnab ((G.adj_comm b a).mp hadj)            · exact hxs (priv_uniq b s hbB hcb hs hbAdj x hxS hadj)          have hcardT : (insert b (insert a (S.erase s)) : Finset V).card = S.card + 1 := by            rw [Finset.card_insert_of_notMem hb_not]            rw [Finset.card_insert_of_notMem (by simp [Finset.mem_erase, haS])]            rw [Finset.card_erase_of_mem hs]            have : 0 < S.card := Finset.card_pos.mpr ⟨s, hs⟩            omega          have hle := hS_maxcard (insert b (insert a (S.erase s))) hT          rw [hcardT] at hle          omega    have h4 := hclique _ hcl    rw [Finset.card_insert_of_notMem hsnot] at h4    omega  have hWsplit : ∑ v : V, w v = ∑ v ∈ S, w v + ∑ v ∈ B, w v := by    have h := Finset.sum_sdiff (f := w) (Finset.subset_univ S)    rw [hB]    linarith [h]  have hsub : ∑ v ∈ B, (w v * (3 - 2 * ((S.filter (G.Adj v)).card : ℝ)))      = 3 * (∑ v ∈ B, w v) - 2 * ∑ v ∈ B, w v * ((S.filter (G.Adj v)).card : ℝ) := by    have heq : ∀ v ∈ B, w v * (3 - 2 * ((S.filter (G.Adj v)).card : ℝ))        = 3 * w v - 2 * (w v * ((S.filter (G.Adj v)).card : ℝ)) := by      intro v _; ring    rw [Finset.sum_congr rfl heq, Finset.sum_sub_distrib, Finset.mul_sum, Finset.mul_sum]  have hC : ∑ v ∈ B, (w v * (3 - 2 * ((S.filter (G.Adj v)).card : ℝ))) ≤ ∑ v ∈ P, w v := by    rw [hP, Finset.sum_filter]    apply Finset.sum_le_sum    intro v hv    by_cases hc : (S.filter (G.Adj v)).card = 1    · rw [if_pos hc, hc]; norm_num    · rw [if_neg hc]      have hge : 2 ≤ (S.filter (G.Adj v)).card := by have := hB_pos v hv; omega      have hcoef : 3 - 2 * ((S.filter (G.Adj v)).card : ℝ) ≤ 0 := by        have : (2:ℝ) ≤ ((S.filter (G.Adj v)).card : ℝ) := by exact_mod_cast hge        linarith      exact mul_nonpos_of_nonneg_of_nonpos (hw v) hcoef  have hD : ∑ v ∈ P, w v ≤ 3 * ∑ s ∈ S, w s := by    rw [hPfiber, Finset.mul_sum]    apply Finset.sum_le_sum    intro s hs    calc ∑ v ∈ P.filter (fun v => G.Adj v s), w v        ≤ ∑ v ∈ P.filter (fun v => G.Adj v s), w s := by          apply Finset.sum_le_sum          intro v hv; exact hfiber_weight s hs v hv      _ = (P.filter (fun v => G.Adj v s)).card • w s := Finset.sum_const _      _ = ((P.filter (fun v => G.Adj v s)).card : ℝ) * w s := by rw [nsmul_eq_mul]      _ ≤ 3 * w s := by          apply mul_le_mul_of_nonneg_right _ (hw s)          exact_mod_cast hfiber_card s hs  have hmain : 3 * (∑ v ∈ B, w v) - 2 * ∑ v ∈ B, w v * ((S.filter (G.Adj v)).card : ℝ)      ≤ 3 * ∑ s ∈ S, w s := by    rw [← hsub]    linarith [hC, hD]  rw [hWsplit]  linarith [hmain]
See it in the graphDiscuss this resultChallenge it