simple_graph_maximum_independent_set_weighted_overlap_of_clique_four
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.
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.
uses
Finset.exists_max_image,Finset.mem_filter,Finset.mem_univ,true_andclassical 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, ?_⟩
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.
uses
SimpleGraph.IsIndepSet,Set.Pairwise,Finset.mem_coe,Finset.mem_insert,Finset.mem_erase,Finset.mem_sdiff.mpset 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
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.
uses
Finset.notMem_empty,Finset.erase_eq_of_notMem,Finset.card_insert_of_notMemhave 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
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.
uses
Finset.mem_insert,Finset.card_le_card,Finset.card_pairhave 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
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).
uses
Finset.filter_subset,Finset.mem_filter.mp,Finset.sum_filter,Finset.sum_comm,Finset.sum_congr,Finset.sum_constset 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
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).
uses
Finset.mem_filter,Finset.card_insert_of_notMem,Finset.card_erase_of_mem,Finset.sum_insert,Finset.sum_erase_addhave 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
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.
uses
Finset.mem_filter,SimpleGraph.IsClique,Set.Pairwise,Finset.mem_coe,Finset.mem_insert,Finset.card_insert_of_notMem,Finset.card_erase_of_memhave 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
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)|.
uses
Finset.sum_sdiff,Finset.subset_univ,Finset.sum_congr,Finset.sum_sub_distrib,Finset.mul_sumhave 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]
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).
uses
Finset.sum_filter,Finset.sum_le_sum,if_pos,if_neg,mul_nonpos_of_nonneg_of_nonposhave 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
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).
uses
Finset.mul_sum,Finset.sum_le_sum,Finset.sum_const,nsmul_eq_mul,mul_le_mul_of_nonneg_righthave 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
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)|.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem 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]