simple_graph_triangle_free_weighted_low_neighborhood
In any finite triangle-free graph with nonnegative integer vertex weights, if some vertex has positive weight then some positive-weight vertex has at most half of the total weight in its neighborhood.
Statement
theorem simple_graph_triangle_free_weighted_low_neighborhood {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] (w : α → ℕ) (htri : G.CliqueFree 3) (hw : ∃ x, 0 < w x) : ∃ x, 0 < w x ∧ 2 * (∑ y ∈ G.neighborFinset x, w y) ≤ ∑ y, w y
- Source
- Weighted-neighborhood argument used in the Ramsey upper-bound proof, https://arxiv.org/abs/2401.00392, Proposition 2.1.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_ramsey_three_ten_nonregular_edge_bound_conditionalLet G be a triangle-free graph on 40 vertices of maximum degree at most 9. Suppose that, for every vertex v, the number of edges outside…
The proof, explained
The proof proceeds by contradiction: suppose every vertex with positive weight has a neighborhood whose weight strictly exceeds half of the total weight. Starting from an assumed positive-weight vertex x, its neighborhood must also have positive weight, so it contains an adjacent neighbor y with positive weight. Because the graph is triangle-free, the neighborhoods of the adjacent vertices x and y are disjoint, so the sum of their neighborhood weights cannot exceed the total graph weight. However, summing the contradiction hypotheses for x and y implies that the sum of their neighborhood weights strictly exceeds the total weight, reaching a contradiction.
Assume for contradiction that every positive-weight vertex has neighborhood weight strictly exceeding half the total weight, and fix a positive-weight vertex x.
We proceed by contradiction (`by_contra!`). Supposing the theorem is false, every vertex v with w(v) > 0 satisfies ∑ y, w y < 2 * ∑ y ∈ N(v), w y. The hypothesis hw supplies a vertex x with w(x) > 0, and specializing the contradiction assumption to x gives that the total weight is strictly less than twice the neighborhood weight of x.
classical by_contra! h obtain ⟨x, hx⟩ := hw have hlarge : (∑ y, w y) < 2 * (∑ y ∈ G.neighborFinset x, w y) := h x hx
The vertex x has an adjacent neighbor y with positive weight w(y) > 0.
Since the total weight is a natural number strictly less than twice the neighborhood weight of x, that neighborhood weight must be strictly positive (`omega`). By `Finset.sum_pos_iff.mp`, a sum of nonnegative integers is positive only if at least one term is positive, yielding a neighbor y in N(x) with w(y) > 0. By `G.mem_neighborFinset`, membership in the neighborhood finset means x and y are adjacent in G.
uses
Finset.sum_pos_iff.mp,G.mem_neighborFinsethave hpos : 0 < ∑ y ∈ G.neighborFinset x, w y := by omega obtain ⟨y, hy, hwy⟩ := Finset.sum_pos_iff.mp hpos have hxy : G.Adj x y := (G.mem_neighborFinset x y).mp hy
The neighborhoods N(x) and N(y) are disjoint.
To establish disjointness via `Finset.disjoint_left.mpr`, suppose toward a contradiction that some vertex z belongs to both N(x) and N(y). Then z is adjacent to both x and y (by `G.mem_neighborFinset`). In a triangle-free graph, the neighborhood of x is an independent set (`G.isIndepSet_neighborSet_of_triangleFree`). But y and z are distinct neighbors of x (distinct because they are adjacent, by `G.ne_of_adj`), so they cannot be adjacent, contradicting their adjacency.
uses
Finset.disjoint_left.mpr,G.mem_neighborFinset,G.isIndepSet_neighborSet_of_triangleFree,G.ne_of_adjhave hdis : Disjoint (G.neighborFinset x) (G.neighborFinset y) := by apply Finset.disjoint_left.mpr intro z hzx hzy have hxz : G.Adj x z := (G.mem_neighborFinset x z).mp hzx have hyz : G.Adj y z := (G.mem_neighborFinset y z).mp hzy exact (G.isIndepSet_neighborSet_of_triangleFree htri x) hxy hxz (G.ne_of_adj hyz) hyz
The sum of the neighborhood weights of x and y is at most the total weight of the graph.
Because N(x) and N(y) are disjoint, the sum of their individual weights equals the sum over their union (`Finset.sum_union`). Since their union is a subset of the entire vertex set (`Finset.subset_univ`), its weight is bounded by the total sum of weights across all vertices (`Finset.sum_le_sum_of_subset`).
uses
Finset.sum_union,Finset.sum_le_sum_of_subset,Finset.subset_univhave hbound : (∑ z ∈ G.neighborFinset x, w z) + (∑ z ∈ G.neighborFinset y, w z) ≤ ∑ z, w z := by rw [← Finset.sum_union hdis] exact Finset.sum_le_sum_of_subset (Finset.subset_univ _)
The contradiction hypotheses for x and y contradict the upper bound on their neighborhood weights.
Since w(y) > 0, the contradiction assumption also applies to y, yielding that the total weight is strictly less than twice the neighborhood weight of y. Adding this to the corresponding inequality for x implies that twice the total weight is strictly less than twice the sum of the two neighborhood weights, contradicting the fact that the sum of the two neighborhood weights is at most the total weight. The linear arithmetic solver `omega` detects this contradiction and closes the proof.
have hylarge : (∑ z, w z) < 2 * (∑ z ∈ G.neighborFinset y, w z) := h y hwy omega
Finset.sum_pos_iff.mp- A finite sum of nonnegative values is strictly positive only if some term in the sum is strictly positive.
G.mem_neighborFinset- A vertex belongs to the neighborhood finset of another vertex if and only if they are adjacent in the graph.
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first set belongs to the second set.
G.isIndepSet_neighborSet_of_triangleFree- In a triangle-free graph, the neighborhood of any vertex forms an independent set.
G.ne_of_adj- Two adjacent vertices in a simple graph are distinct.
Finset.sum_union- The sum of a function over the union of two disjoint finite sets is the sum of the sums over each set.
Finset.sum_le_sum_of_subset- The sum of nonnegative values over a subset is at most the sum over the superset.
Finset.subset_univ- Any finite set of elements of a finite type is a subset of the universal finset.
- The strict positivity of the neighborhood weight of x is deduced by `omega` directly from the inequality ∑ y, w y < 2 * ∑ y ∈ N(x), w y: since natural numbers are nonnegative, twice the neighborhood weight must exceed 0, so the neighborhood weight cannot be 0.
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_triangle_free_weighted_low_neighborhood {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] (w : α → ℕ) (htri : G.CliqueFree 3) (hw : ∃ x, 0 < w x) : ∃ x, 0 < w x ∧ 2 * (∑ y ∈ G.neighborFinset x, w y) ≤ ∑ y, w y := by classical by_contra! h obtain ⟨x, hx⟩ := hw have hlarge : (∑ y, w y) < 2 * (∑ y ∈ G.neighborFinset x, w y) := h x hx have hpos : 0 < ∑ y ∈ G.neighborFinset x, w y := by omega obtain ⟨y, hy, hwy⟩ := Finset.sum_pos_iff.mp hpos have hxy : G.Adj x y := (G.mem_neighborFinset x y).mp hy have hdis : Disjoint (G.neighborFinset x) (G.neighborFinset y) := by apply Finset.disjoint_left.mpr intro z hzx hzy have hxz : G.Adj x z := (G.mem_neighborFinset x z).mp hzx have hyz : G.Adj y z := (G.mem_neighborFinset y z).mp hzy exact (G.isIndepSet_neighborSet_of_triangleFree htri x) hxy hxz (G.ne_of_adj hyz) hyz have hbound : (∑ z ∈ G.neighborFinset x, w z) + (∑ z ∈ G.neighborFinset y, w z) ≤ ∑ z, w z := by rw [← Finset.sum_union hdis] exact Finset.sum_le_sum_of_subset (Finset.subset_univ _) have hylarge : (∑ z, w z) < 2 * (∑ z ∈ G.neighborFinset y, w z) := h y hwy omega